在半连续列表的二分搜索上使用二分搜索树是否有现实世界的理由？

Question

我正在观看关于算法的大学讲座，似乎其中许多课程几乎完全依赖某种特定类型的二叉搜索树来进行查询/数据库/搜索任务。

我不明白这种对Binary Search Trees 的痴迷。似乎在绝大多数情况下，在静态数据的情况下，BSP 可以用排序数组替换，如果插入动态发生，则可以用排序的桶列表替换，然后可以对它们进行二分搜索。

通过这种方法，你会得到相同的算法复杂性（至少查询）为BST，方式更好的高速缓存一致性，这样少的内存碎片（取决于你是用什么语言少GC allocs），并有可能要简单得多写。

基本问题是 BSP 完全没有内存——他们的重点完全是 O(n) 复杂性，他们忽略了内存碎片和缓存一致性的非常真实的性能考虑......我错过了什么吗？

Answer 1

二叉搜索树（BST）并不完全等同于所提出的数据结构。当动态插入和删除排序值时，它们的渐近复杂度更好（假设它们正确平衡）。例如，当您动态构建 top-k 值的索引时：

while end_of_stream(stream):
    value <- stream.pop_value()
    tree.insert(value)
    tree.remove_max()

由于线性时间插入，排序数组在这种情况下效率不高。桶列表的复杂性渐近并不比普通列表好，并且还受到线性时间搜索的影响。人们可以注意到，在这种情况下可以使用堆，事实上，这里使用堆可能更好，尽管它们并不总是可以互换的。

话虽这么说，你是对的：BST 很慢，会导致大量缓存未命中和碎片等。因此，它们通常被更紧凑的变体（如B 树）所取代。B 树使用排序数组索引来减少节点跳转量并使数据结构更加紧凑。它们可以与一些 4 字节指针优化混合，使它们更加紧凑。B 树之于 BST 就像存储桶链表之于普通链表一样。B 树非常适合为存储在慢速存储设备上的大型数据集（由于大小）构建动态数据库索引：它们使应用程序能够使用很少的存储设备查找来获取与键关联的值（这在速度上非常慢）以硬盘驱动器为例）。现实世界用例的另一个例子是区间树。

请注意，可以使用压缩方法减少内存碎片。对于 BST/B 树，可以像在堆中一样对根节点重新排序。然而，压缩并不总是容易应用，尤其是在 C/C++ 等带有指针的本机语言上，尽管存在一些非常聪明的方法来做到这一点。

请记住，B 树仅适用于大型数据集（尤其是那些不适合缓存的数据集）。对于相对较小的数组，仅使用普通数组甚至排序数组通常是一个非常好的解决方案。