從 SQL 表 (SQL/C++) 填入無序映射中缺失值的有效方法

Question

問題 目前有一個系統可以將唯一識別碼（id）及其附加資料集從 SQL 表讀取到無序映射中。這些資料集過去以 id 1 開頭，但資料集的新增和刪除大約需要 10 毫秒。請注意，並非所有資料集始終都會載入到 RAM 中。

程式啟動時，它會從資料庫中讀取 SELECT MAX(id) ，並繼續向計數器變數添加1，該變數將用作任何新增的資料集的id 。已刪除資料集的 ids 不再在任何地方使用。這不可避免地會導致 id 序列出現間隙，並且有一天會溢出。

我正在尋找一種高效能的方法來填補 id 值的最低差距。同時與僅部分載入的 SQL 表和程式記憶體保持一致。記憶體中的資料可能需要幾分鐘或立即才能儲存到SQL表中。

想法 我想出的一個解決方案是在運行時對每個創建的資料集進行昂貴的查詢，以找到SQL 表中的最小間隙，檢查此id 是否作為無序映射中的值存在，然後再次使用來自計數器變數作為備份，以避免無休止地查詢免費的id。這完全適用於 1 id 的數量。然後它在 SQL 中仍然是空閒的，但在無序映射中被獲取，直到再次節省記憶體。

我還集思廣益，將免費ID 列表查詢到向量中，並將它們用作新資料集的id ，直到向量為空，然後（或經常）對更多ID 進行新查詢。但我想不出一個查詢來查找表中 X 數量的間隙，該表可能有也可能沒有以 1 開頭的 id 列。

我遇到過如何在使用 SQL 運行計數器時找到“間隙”？ ，但我對最佳答案有兩個問題：顯然，它只找到一個間隙，而我需要很多間隙，而且我無法理解它使用的 mo 和 mi 。

假設我有一個名為 userdata 的表，其中包含 id 和 dataset 列，都是 32 位元帶符號 INT。如何在 id 列中找到一系列間隙？例如，當表中的 ids 為 1,6,7,9 時，我希望查詢傳回 2,3,4,5,8。

任何指向可能解決方案的方法的指標也將受到讚賞。

Answer 1

如果每 10 毫秒就有一個資料庫更改，那麼每秒就有 100 次更改。一個有符號的int可以容納大約2,147,483,648個值，或21,474,846秒，大約是8個月。此後，不可能有可用的新 ID。

第一個解決方案是使用 64bit 類型而不是 int。這給了你大約 13,600 年（對於有符號的 64b），這似乎足夠了:)

---

其他解是擁有一個包含所有可能 ID 的向量。向量儲存 bool（ID 已使用/未使用）。請求新的 ID 是透過將向量移動到標記為未使用的第一個位置來完成的。
該向量使用大量 RAM，儘管 std::vector 有一個專門用於 bool 的版本，需要較少的 RAM。

---

第三種解決方案是處理儲存已刪除（讀取：可重複使用）ID 的連結清單（可能是雙連結）。

當要求新的 ID 時，清單會提供其頭部，如果清單為空，則提供表格的大小。
刪除資料集時，其 ID 會正確插入到清單中，因此清單始終是排序的。
當 ID 被重複使用時，它將從清單中刪除。
刪除表中的最後一筆記錄也可能會刪除清單中的最後一個節點，因為它們是無用的（案例 ID > 表大小）。這就是為什麼我建議使用雙鍊錶，以便快速刪除最後的節點。

因此，該列表在其節點上快速使用“new”和“delete”，並且還頻繁地上下運行（對於雙連結）以插入新節點。
這有點慢，但我希望清單不要太大，然後所需的時間也不錯。

另請注意，此清單為您提供了所需的間隙陣列。