有序链表与B-树

Question

如果您使用b+树作为索引，那么这看起来非常类似于有序链表。但有序链表似乎有一些优点，例如不必导航树结构，也不必在节点已满时重新构建节点，以及在未平衡时不必重新构建树。

谁能回答使用b树而不是有序链表的原因是什么？

Answer 1

经过一些研究和论文阅读，我找到了答案。

为了处理数百万条记录之类的大量数据，必须将索引组织到集群中。簇是磁盘上一组连续的扇区，可以快速读取到内存中。它们通常约为4096字节长。

如果我们组织我们的索引，使得每个集群都包含指向磁盘(数据集群)上的数据的索引的有序列表，我们就可以有一个有序列表索引。

那么，如果我们正在寻找一个特定的记录，我们如何知道它在哪个集群上呢？我们执行二进制搜索来找到问题O(log )中的集群。

然而，要进行二进制搜索，我们需要知道每个数据集群中的值的范围，因此我们需要元数据来说明每个集群的最小和最大值以及该集群所在的位置。这太棒了。除非每个数据集群包含100个索引，而我们的元数据集群也包含100个索引，那么我们只能访问100个数据集群。这相当于10000条记录(100X100)。

好吧，这还不够。让我们添加另一个元数据集群，我们现在可以访问1,000,000条记录。那么，我们如何知道需要查询三个元数据集群中的哪一个才能找到目标数据集群呢？我们可以一个接一个地搜索它们，但这不是可伸缩性的，平均为O(n/2)。因此，我添加了另一个元数据集群，以指示我应该查询三个元数据集群中的哪一个来查找目标数据集群。现在我有一棵树了！

这就是数据库使用树的原因。这不是速度的问题，而是索引的大小以及让索引引用其他索引的需要。我在上面描述的是一个B+Tree --子节点包含对其他子节点或叶节点的引用，叶节点包含对磁盘上数据的引用。

呼！

Answer 2

在特征上有很多不同，但我强调搜索时间。

当搜索在b+树中是对数O( N)时间时，在链表中是log O(N)时间，即使它是排序的。

来源：http://en.wikipedia.org/wiki/Linked_list，http://en.wikipedia.org/wiki/B%2B_tree

Answer 3

在二叉搜索树中，O(log )搜索时间是平均情况。在最坏的情况下，当树完全不平衡并且类似于链表时，搜索需要O(n)时间。