SQL テーブルから順序なしマップの欠損値を埋める効率的な方法 (SQL/C++)

Question

＃＃＃＃＃＃質問＃＃＃ 現在、一意の識別子 (

id) とそれに関連付けられたデータ セットを SQL テーブルから順序なしマップに読み取るシステムがあります。これらのデータセットは id 1 で始まりましたが、データセットの追加と削除には約 10 ミリ秒かかりました。すべてのデータセットが常に RAM にロードされるわけではないことに注意してください。 プログラムが開始されると、データベースから SELECT MAX(id)

を読み取り、追加されたデータセットの

id# として使用されるカウンター変数に 1 を追加します ## 。削除されたデータセットの id はどこにも使用されなくなりました。これにより、必然的に id シーケンスにギャップが生じ、いつかオーバーフローすることになります。 id 値の最小ギャップを埋める効率的な方法を探しています。部分的にのみロードされた SQL テーブルとプログラム メモリにも一貫性があります。メモリ内のデータが SQL テーブルに保存されるまでに数分かかる場合もあれば、すぐに保存される場合もあります。

＃＃＃＃＃＃アイデア＃＃＃ 私が思いついた解決策の 1 つは、実行時に作成された各データセットに対して負荷の高いクエリを実行して、SQL テーブル内の最小のギャップを見つけ、この

id が順序付けされていないマップ内の値として存在するかどうかを確認し、再度確認することでした。無料の id

に対する無限のクエリを避けるために、カウンターの変数をバックアップとして使用します。これは、数量が 1

id の場合に完全に機能します。その後、SQL では空き状態のままですが、メモリが再度保存されるまで順序なしマップでフェッチされます。 また、無料 ID のリストをベクターにクエリし、ベクターが空になるまでそれらを新しいデータセットの ids として使用し、その後 (または頻繁に) より多くの ID に対して新しいクエリを実行するというブレインストーミングも行いました。しかし、1 で始まる id 列があるかどうかに関係なく、テーブル内の X 個のギャップを見つけるクエリを思いつきません。

SQL を使用してカウンターを実行するときに「ギャップ」を見つける方法を見つけました。 、しかし、一番上の答えには2つの問題があります。どうやら、ギャップが1つだけ見つかるようですが、私にはたくさんのギャップが必要で、

moとmi##の使用法が理解できません。 # 。

userdata

というテーブルがあり、このテーブルには id 列と dataset 列 (どちらも 32 ビットの符号付き INT) が含まれているとします。

id

列内の一連のギャップを見つけるにはどうすればよいですか?たとえば、テーブル内の id が 1,6,7,9 の場合、クエリは 2,3,4,5,8 を返すようにします。 考えられる解決策へのヒントもいただければ幸いです。

Answer 1

10 ミリ秒ごとにデータベースが変更される場合、1 秒あたり 100 件の変更が行われることになります。署名付き int は、約 2,147,483,648 個の値、または 21,474,846 秒、つまり約 8 か月を保持できます。それ以降は新たにIDを取得することはできなくなります。

最初の解決策は、int の代わりに 64bit 型を使用することです。これにより、約 13,600 年 (署名された 64b の場合) が得られ、これで十分だと思われます :)

---

他の解決策は、考えられるすべての ID を含むベクトルを用意することです。ベクトルストレージ bool(ID 使用/未使用)。新しい ID の要求は、ベクトルを未使用としてマークされた最初の位置に移動することによって行われます。
このベクトルは大量の RAM を使用しますが、必要な RAM が少ない bool 専用の std::vector のバージョンがあります。

---

3 番目の解決策 は、削除された (再利用可能な) ID のリンクされたリスト (おそらく二重リンク) を保存することです。

新しい ID が要求されると、リストはそのヘッダー、またはリストが空の場合はテーブルのサイズを提供します。
データセットが削除されると、その ID がリストに正しく挿入されるため、リストは常に並べ替えられます。
ID が再利用されると、リストから削除されます。
テーブルの最後のレコードを削除すると、リストの最後のノードも不要になるため削除される可能性があります (ケース ID > テーブル サイズ)。このため、最後のノードをすぐに削除できるように、二重リンク リストを使用することをお勧めします。

そのため、リストはノード上で「new」と「delete」を素早く使用し、また (デュアル リンクの場合) 頻繁に上下に実行して新しいノードを挿入します。
これは少し遅いですが、リストが大きすぎず、必要な時間がそれほど長くないことを願っています。

また、このリストには、必要なギャップの配列が示されていることに注意してください。