database - 在有序数字列表中查找数字记录的算法

Question

我有一个不完整的有序数字列表。我想用尽可能少的步骤找到一个特定的数字。

这个算法有什么改进吗，我假设你可以毫无困难地计算集合大小——每次添加新项目时它都会被存储和更新。

你的目标是让你的光标在值 x 上

第一个数字(最小)是 s，最后一个数字(最大)是 g。

1. 取集合的中点m1:计算为x < m1,
2. 如果是那么 s <= x < m1
3. 如果没有则 m1 < x <= g
4. 如果 m1 = x 那么你就完成了。

不断重复直到找到 x。每次迭代基本上将集合分成两部分，直到你命中 x。

目的是从一个非常大的表中检索一个数字 id，然后找到关联的其他记录。

我认为这是可用的最简单的索引类型，有改进吗？

Answer 1

如果您想使用有序的数据结构，二分查找在渐近意义上是最优的。但是，如果您使用辅助树，并且注意局部性，则可以在时间性能方面获得较大的常数因子。

具体来说，如果您从磁盘访问数据，那么磁盘访问时间将决定一切。在这种情况下，您希望减少需要从磁盘随机访问的不同数据 block 的数量。这就是 B 树、B+ 树和类似树所做的:它们以树的形式存储数据，并确保节点具有较大的扇出，以便它们可以限制深度，因此不需要做太多许多随机搜索。

如果访问内存中的数据，你可以通过关注缓存行来做类似的事情； Judy trees就是其中一个例子。

如果您要进行精确匹配，则可以在常数时间内进行散列运算——无论您的数字是否有序。不过，散列法在时间和空间上可能会有很大的开销，而且有序方法通常具有竞争力，因此您确实需要根据具体情况做出决定。