数据库索引B树和列表

Question

任何人都可以解释为什么数据库倾向于使用B树索引而不是有序元素的链表。

我的想法是这样的：在B +树（大多数数据库使用）上，无叶节点是指向其他节点的指针集合。每个集合（节点）都是一个有序列表。所有数据指针所在的叶节点是数据指针簇的链表。

非叶节点仅用于查找目标数据指针所在的正确叶节点。因此，由于叶节点就像一个链表，为什么不去掉树元素，只是拥有链表。元数据可以提供每个叶节点簇的最小值和最大值，因此应用程序可以读取元数据并找到数据指针所在的正确叶。

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

这个结构是否可行。

Answer 1

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

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

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

所以，当我们在寻找一个特定的记录时，我们如何知道它在哪个簇上。我们执行二进制搜索来查找正在讨论的集群[O（log n）]。

但是，要进行二分搜索，我们需要知道每个集群中值的范围，因此我们需要元数据来表示每个集群的最小值和最大值以及该集群的位置。这很棒。除了每个群集可以包含100个索引，并且我们的元数据也保存在一个群集中（为了提高速度），那么我们的元数据只能指向100个群集。

如果我们想要超过100个群集会发生什么情况。我们必须有两个元数据索引，每个索引指向100个集群（10000条记录）。那还不够。让我们添加另一个元数据集群，现在我们可以访问1 000 000条记录。那么，我们如何知道为了找到我们的目标数据集群，我们需要查询三个元数据集群中的哪一个。我们可以搜索另一个，但不会扩展。因此，我添加了另一个元元数据群集来指示我应该查询哪三个元数据群集来查找目标数据群集。现在我有一棵树！

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

唷！

Answer 2

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

它们通常以堆结构实现。

这有两个主要优点：

• 他们很容易管理（你只需要为每一个元素的指针）

• 如果结合使用，就可以解决这个问题的索引的顺序访问。

相反，如果你使用一个有序列表，通过键值，您将拥有四通八达的交通网络（二进制搜索），但每次编辑，删除时遇到问题，插入一个新元素：你必须INFACT保持你的执行操作后排序，使算法更加复杂和耗时。

B +树是更好的结构中，具有你陈述的所有属性，和其它的优点：

• 可以使组搜索（由键值的间隔）与单个搜索的相同的成本：由于元件在叶子结果自动排序感谢插入算法，这是不可能的链接列表，因为它需要在列表上的许多线性搜索。

• 成本是包含元素数量的对数，特别是因为这些结构保持平衡，访问成本不取决于您正在查找的特殊值（非常有用）。

• 这些结构在更新，插入或删除操作中非常有效。

Answer 3

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

总结最重要的部分，相对于特定的问题：

- 摘自“叶节点“

索引的主要目的是提供索引数据的有序 表示。但是， 不可能按顺序存储数据，因为插入语句需要 移动下列条目以腾出空间给新的数据。但移动 的大量数据非常耗时，所以插入 语句会很慢。问题的解决方案是建立一个与内存中的物理顺序无关的逻辑顺序 。

- 从“B-树”：

叶节点被存储在任意的顺序-位置上 索引根据 磁盘不对应于逻辑位置索引顺序。它就像一个电话号码簿，带有混乱的页面。如果 您搜索“Smith”，但在第一个 位置的“Robinson”中打开它，但决不允许Smith回到更远的位置。 数据库需要第二个结构来快速找到 混洗页面中的条目：一个平衡搜索树 - 简而言之：B树。