如果你有一个b+树作为索引，那么这看起来很像一个有序链表。但是有序链表似乎有一些优点，例如不必导航树结构，也不必在节点满时重建节点，以及在树不平衡时不必重建树。
谁能回答为什么要使用 b 树而不是有序链表？
最佳答案
经过一些研究和阅读论文后，我找到了答案。
为了应对百万条记录这样的海量数据，索引不得不组织成簇。簇是磁盘上连续的一组扇区，可以快速读入内存。这些通常大约 4096 字节长。
如果我们组织我们的索引，使每个集群都包含一个有序的索引列表，这些索引指向磁盘上的数据(数据集群)，我们就可以拥有一个有序的列表索引。
那么，如果我们要查找特定记录，我们如何知道它在哪个集群上？我们执行二进制搜索以找到有问题的集群 [O(log n)]。
但是，要进行二分查找，我们需要知道每个数据簇中值的范围，因此我们需要元数据来说明每个簇的最小值和最大值以及该簇的位置。这很棒。除非每个数据集群包含 100 个索引，而我们的元数据集群也包含 100 个索引，那么我们只能访问 100 个数据集群。这相当于 10 000 条记录 (100 X 100)。
这还不够。让我们添加另一个元数据集群，我们现在可以访问 1 000 000 条记录。那么我们如何知道我们需要查询三个元数据集群中的哪一个才能找到我们的目标数据集群。我们可以一个接一个地搜索它们，但这并不能扩展，平均来说是 O(n/2)。所以我添加了另一个元数据集群来指示我应该查询三个元数据集群中的哪一个来找到目标数据集群。现在我有一棵树了!
这就是数据库使用树的原因。这不是速度，而是索引的大小以及索引引用其他索引的需要。我上面描述的是 B+Tree——子节点包含对其他子节点或叶节点的引用，叶节点包含对磁盘上数据的引用。
呸!
关于database - 有序链表与 B 树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8384338/