数据库索引B树和列表

Question

有人能解释为什么数据库倾向于使用b-tree索引而不是有序元素的链表吗？

我的想法是:在B+树(大多数数据库使用)上，非叶节点是指向其他节点的指针的集合。每个集合(节点)都是一个有序列表。叶节点是所有数据指针所在的位置，是数据指针群集的链表。

非叶节点只是用来查找您的目标数据指针所在的正确叶节点。既然叶子节点就像一个链表，那么为什么不干脆去掉树元素，只使用链表呢？可以提供元数据，它给出了每个叶节点集群的最小值和最大值，因此应用程序可以只读取元数据并找到数据指针所在的正确叶。

要清楚的是，搜索随机访问的有序列表的最有效算法是二进制搜索，其性能为O(log )，与b-树相同。使用链表而不是树的好处是它们不需要平衡。

这种结构可行吗。

Answer 1

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

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

这些集群中的每个集群都可以包含一组索引，这些索引可以指向其他集群或磁盘上的数据。因此，如果我们有一个链表索引，那么索引的每个元素将由包含在单个集群中的索引集合组成(比方说100)。

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

然而，要进行二进制搜索，我们需要知道每个集群中的值范围在哪里，因此我们需要元数据来说明每个集群的最小和最大值以及该集群的位置。这太棒了。除非每个集群可以包含100个索引，并且我们的元数据也保存在一个集群上(为了提高速度)，那么我们的元数据只能指向100个集群。

如果我们想要超过100个集群，会发生什么呢？我们必须有两个元数据索引，每个索引指向100个集群(10000条记录)。好吧，这还不够。让我们添加另一个元数据集群，我们现在可以访问1,000,000条记录。那么，我们如何知道需要查询三个元数据集群中的哪一个才能找到目标数据集群呢？我们可以先搜索一个，然后再搜索另一个，但这不是可伸缩的。因此，我添加了另一个元数据集群，以指示我应该查询三个元数据集群中的哪一个来查找目标数据集群。现在我有一棵树了！

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

呼！

Answer 2

我想我在我的SQL索引教程的第1章：http://use-the-index-luke.com/sql/anatomy中回答了这个问题。

关于你的特定问题，总结一下最重要的部分：

--摘自“叶子节点”

索引的主要目的是提供索引数据的有序表示。但是，不可能按顺序存储数据，因为insert语句需要移动以下条目才能为新条目腾出空间。但是移动大量数据非常耗时，因此insert语句将非常慢。问题的解决方案是建立一个独立于内存中的物理顺序的逻辑顺序。

--摘自“B树”：

索引叶节点以任意顺序存储-磁盘上的位置与根据索引顺序的逻辑位置不对应。它就像一本页码混乱的电话簿。如果您在中搜索“Smith”，但首先在“Robinson”处打开它，则决不会认为Smith出现在更早的位置。数据库需要第二个结构，以便在混乱的页面中快速找到条目:一个平衡的搜索树-简而言之: B-Tree.

Answer 3

链表通常不是按键值排序的，而是按插入时刻排序的:插入是在列表的末尾完成的，每个新条目都包含一个指向列表前一条目的指针。

它们通常以堆结构的形式实现。

这有两个主要的好处：

• 它们非常易于管理(您只需要为每个元素指定一个指针)
• 如果与索引结合使用，则可以克服顺序访问的问题。

如果你使用的是按键值排序的列表，你将很容易访问(二进制搜索)，但每次你编辑、删除、插入新元素时都会遇到问题:你必须在执行操作后保持列表的顺序，这使得算法更加复杂和耗时。

B+树是更好的结构，具有您所说的所有属性和其他优点：

• 您可以使用与单个搜索相同的成本进行组搜索(按键值的间隔)：由于叶结构中的元素由于插入算法而自动排序，这在链表中是不可能的，因为它需要对列表进行多次线性搜索。
• 成本与包含的元素数量成对数，特别是因为这些结构保持平衡访问成本与您要查找的具体值无关(very
• structures在更新、插入或删除操作中非常有效。