数据库索引：B-树和列表

Question

数据库索引：B-树和列表

4

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

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

非叶节点只是用来找到正确的叶节点，从而找到目标数据指针所在的位置。因此，由于叶节点就像一个链表，为什么不直接去掉树元素，只保留链表呢？可以提供元数据，给出每个叶节点群的最小值和最大值，这样应用程序就可以读取元数据并找到正确的叶子，从而找到数据指针所在的位置。

需要明确的是，对于随机访问的有序列表，最有效的搜索算法是二分查找，其性能为O(log n)，与B树相同。使用链表而不是树的好处是它们不需要平衡。

这种结构可行吗？

- Adam Davies

3个回答

5

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

总结一下，关于你特别提出的问题：

-- 来自“叶节点”

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

-- 来自“B-Tree”:

索引叶节点按任意顺序存储，磁盘上的位置不对应于索引顺序的逻辑位置。就像一个打乱顺序的电话簿。如果你在第一个位置打开它，并搜索“Smith”，却从“Robinson”开始看，那么并不能保证Smith在更靠后的位置。数据库需要第二个结构来快速查找打乱顺序的页码：一个平衡的搜索树——简称B树。

- Markus Winand

感谢您的回复。然而，在B+树中，叶节点是按排序顺序存储的。正因为如此（对于范围搜索非常有用），大多数数据库使用B+树而不是B树（Oracle、DB2等）。此外，在链表中插入、删除等操作非常快，因为您不必移动数据，只需重新指向指针即可。http://en.wikipedia.org/wiki/B%2Btree#Implementation - Adam Davies

1

@Adam Davies 存储在逻辑排序，但不是物理上在磁盘上排序。就像一个打乱了页面的电话簿一样。每个页面都有指向逻辑上前面和后面页面的指针。你不能通过翻页来获取逻辑上的下一页。 - Markus Winand

1

@Adam，你不能在逻辑上排序的链表上以log(n)的时间进行二分查找，因为你的访问时间是线性的。只有在物理上排序的列表中，你才能以log(n)的时间进行二分查找，因为你的访问时间是常数级的。希望这样能澄清问题。 - bpgergo

@Markus，对于你的解释点赞。 - bpgergo

索引=逻辑顺序。物理顺序是磁盘上的数据。因此，打个比方。拿一副扑克牌，洗牌，把它们散布在地板上。第一个在左边是编号1，下一个是编号2...直到52（数据库ID）。然后拿52张空白卡片，在上面写上你的排序方式（红桃A、红桃2...任何你喜欢的排序方式）。通过棉线将每张卡片连接到地板上的真实卡片上。你已经创建了一个逻辑索引排序，与物理位置相关联。要查找任何一张卡片，请在索引卡上进行二进制搜索，并拉动棉线，你就得到了真正的卡片。 - Adam Davies

只是为了更加清晰，而不是使用线程，在相应的索引卡上只需写入数据库ID。因此，您在索引卡上决定的排序映射到真实卡上的DB_ID。如果想要不同的顺序，例如所有红色卡片按相反顺序排列，则只需创建另一组索引卡。 - Adam Davies

2

链表通常不是按键值排序，而是按插入时刻排序：插入在列表末尾进行，每个新条目都包含指向列表前一条目的指针。它们通常实现为堆结构。

这有两个主要优点： - 它们非常容易管理（您只需要为每个元素提供指针）。 - 如果与索引结合使用，则可以克服顺序访问的问题。

如果您使用按键值排序的有序列表，则将具有访问便利性（二进制搜索），但每次编辑、删除或插入新元素时都会遇到问题：您必须在执行操作后保持列表有序，使算法更加复杂和耗时。

B+树是更好的数据结构，具有您所述的所有属性以及其他优点： - 您可以通过同一搜索的成本进行分组搜索（按键值间隔）：由于叶中的元素由于插入算法自动排序，因此无法在链表中实现，因为这将需要对列表进行许多线性搜索。 - 成本随包含元素数量的对数而变化，并且特别是由于这些结构保持平衡，访问成本不取决于您寻找的特定值（非常有用）。 - 这些结构在更新、插入或删除操作方面非常高效。

- Matteo

从链表中删除元素很容易 - 你只需要将前一个元素的指针指向要删除的元素之后的元素。如果你想添加元素，只需执行以下操作：A->C 变为 A->B->C，所以你只需将 B 指向 C，然后将 A 指向 B。就像我说的，树中的叶节点只是一个链表。在链表中进行分组搜索比在树中要简单得多。所以，我仍然看不出树结构的好处。 - Adam Davies

1

这很容易，但你需要保持链表有序，这就是问题所在。为了在执行每个操作时保持顺序，你必须先找到确切的位置，这将因元素而异，并且通常随着元素数量的增加而具有线性成本。在树中，成本将随插入的元素数量呈对数级增长，并且对于每个元素都是相同的，这要归功于B+树的平衡属性。 - Matteo

不是真的。在排序列表中找到精确位置的时间复杂度为O(log n)。树搜索是二分搜索的一种形式。此外，树的每个层级上的节点都是索引指针列表。 - Adam Davies

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adam Davies · Accepted Answer

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

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

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

那么，当我们寻找特定记录时，我们如何知道它位于哪个簇上呢？我们执行二分查找来找到需要的簇 [O(log n)]。

然而，要进行二分查找，我们需要知道每个簇的值范围在哪里，因此我们需要元数据来表示每个簇的最小值和最大值以及该簇的位置。这很好。但是，如果每个簇最多可以包含 100 个索引，并且我们的元数据也保存在单个簇中（为了提高速度），那么我们的元数据只能指向 100 个簇。

如果我们需要更多的簇会怎么样？我们必须有两个元数据索引，每个索引指向 100 个簇（10,000 条记录）。好吧，那还不够。让我们再添加一个元数据簇，现在我们可以访问 1,000,000 条记录。那么我们如何知道我们需要查询哪一个三个元数据簇才能找到目标数据簇？我们可以先查询一个再查询另一个，但这并不具有可扩展性。所以我添加了另一个元元数据簇来指示我应该查询哪个三个元数据簇才能找到目标数据簇。现在我有了一棵树！

这就是为什么数据库使用树的原因。不是为了速度，而是因为索引的大小和需要索引引用其他索引。上面描述的是 B+ 树——子节点包含对其他子节点或叶子节点的引用，而叶子节点包含对磁盘上数据的引用。

终于完了！