有序链表与B树

Question

如果您将b +树作为索引，那么这似乎与有序链接列表非常相似。但是，有序链表似乎具有一些优点，例如，不必导航树结构，也不必在节点装满时重建节点，并且不必在无平衡时重建树。

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

Answer 1

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

为了处理大量数据，例如数百万条记录，索引必须被组织成集群。簇是磁盘上的一组连续扇区，可以快速读入内存。这些通常长约 4096 字节。

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

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

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

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

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

呼！