谁能解释一下为什么数据库倾向于使用b-tree索引而不是有序元素的链表?
我的想法是这样的:在B+树(大多数数据库使用)上，非叶节点是指向其他节点的指针的集合。每个集合(节点)是一个有序列表。叶子节点是所有数据指针所在的位置，它是数据指针簇的链表。
非叶节点仅用于查找目标数据指针所在的正确叶节点。既然叶节点就像链表，那为什么不直接去掉树元素，直接得到链表呢?元数据可以给出每个叶子节点簇的最小值和最大值，因此应用程序可以直接读取元数据并找到数据指针所在的正确叶子。
要明确的是，搜索随机访问有序列表的最有效算法是二叉搜索，其性能为O(log n)，与b树相同。使用链表而不是树的好处是它们不需要平衡。
这个结构可行吗?
为了处理大量的数据，如数以百万计的记录，索引必须组织成集群。集群是磁盘上连续的一组扇区，可以快速地读入内存。这些通常约为4096字节长。
每一个集群都可以包含一堆索引，这些索引可以指向磁盘上的其他集群或数据。因此，如果我们有一个链表索引，则索引的每个元素将由单个集群(例如100个)中包含的索引集合组成。
所以，当我们寻找一条特定的记录时，我们如何知道它在哪个集群上。我们执行二分搜索来找到问题中的聚类[O(log n)]。
然而，要进行二叉搜索，我们需要知道每个簇的值范围在哪里，所以我们需要元数据来表示每个簇的最小值和最大值以及该簇的位置。这太棒了。除非每个集群可以包含100个索引，并且我们的元数据也保存在单个集群上(为了速度)，那么我们的元数据只能指向100个集群。
如果我们想要超过100个集群会发生什么?我们必须有两个元数据索引，每个索引指向100个集群(10000条记录)。这还不够。让我们添加另一个元数据集群，现在我们可以访问1,000,000条记录。那么，为了找到目标数据簇，我们如何知道需要查询三个元数据簇中的哪一个呢?我们可以先搜索一个，然后再搜索另一个，但这不能扩展。因此，我添加了另一个元数据集群，以指示我应该查询三个元数据集群中的哪一个来查找目标数据集群。现在我有一棵树了!
这就是数据库使用树的原因。不是速度而是索引的大小以及索引引用其他索引的需求。我上面描述的是一个B+树——子节点包含对其他子节点或叶节点的引用，而叶节点包含对磁盘上数据的引用。
唷!
我想我已经在我的SQL索引教程的第一章回答了这个问题:http://use-the-index-luke.com/sql/anatomy
总结最重要的部分，关于你的特定问题:
——选自《The Leaf Nodes》
索引的主要目的是提供一个有序的索引数据的表示形式。然而，这是不可能的因为插入语句需要按顺序存储数据移动以下条目为新条目腾出空间。但移动大量的数据是非常耗时的，所以要插入语句会很慢。这个问题的解决办法是建立一个与内存中的物理顺序无关的逻辑顺序。
——选自《The B-Tree》:
索引叶节点以任意顺序存储——在磁盘与逻辑位置不对应索引顺序。它就像一个打乱了页面的电话簿。如果你搜索"史密斯"，但打开它在"罗宾逊"在第一尽管如此，我们绝不能肯定史密斯比我们更靠后。数据库需要第二种结构来快速查找条目打乱页面:一个平衡的搜索树——简而言之:b树。
链表通常不是按键值排序，而是按插入时刻排序:插入在列表末尾完成，每个新条目都包含一个指向列表前一条目的指针。
它们通常被实现为堆结构。
这有两个主要的好处:
-
它们很容易管理(你只需要一个指针为每个元素)
-
如果与索引结合使用，可以克服顺序访问的问题。
如果使用按键值排序的列表，可以方便地访问(二进制搜索)，但每次编辑、删除、插入新元素时都会遇到问题:在执行操作后，实际上必须保持列表的顺序，使算法更加复杂和耗时。
B+树是更好的结构，具有你所说的所有属性和其他优点:
-
您可以使用与单个搜索相同的成本进行组搜索(按键值的间隔):由于插入算法，叶子中的元素会自动排序，这在链表中是不可能的，因为它需要对列表进行许多线性搜索。
-
成本与所包含的元素数量成对数关系，特别是因为这些结构保持平衡，访问成本不依赖于您正在寻找的特定值(非常有用)。
-
这些结构在更新、插入或删除操作中非常有效。