从 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”，并且还频繁地上下运行（对于双链接）以插入新节点。
这有点慢，但我希望列表不要太大，然后所需的时间也不错。

另请注意，此列表为您提供了所需的间隙数组。