B-树索引

您可能知道数据库索引是提高数据库性能的一种方式。但令人惊讶的是，很少有人理解不同类型的索引，它们是如何工作的，以及如何为特定的性能问题选择合适的索引——或者说索引是否真的有帮助。本文可能有助于您入门。它将重点介绍B树索引，这是Oracle和SQL Server数据库中最常用的索引类型。术语“分支块”和“叶块”仅限于Oracle数据库，因为这些是我目前最感兴趣的。

为什么需要数据库索引？

简而言之，索引可以帮助我们的数据库快速查找行。

没有索引，数据库在每次需要查找一行或一组行时都必须执行全表扫描。全表扫描是指数据库逐行检查表，查找所需行或行。在大型表中，这可能会很慢。索引提供了数据库可以用来更快地找到所需内容的快捷方式。

一个类比是图书馆。想象一下，如果图书馆里的书没有特定的顺序，找到一本特定的书需要多长时间。您必须一本一本地检查，直到找到您想要的。幸运的是，图书馆的组织方式提供了查找线索。书籍通常按类型和作者排序。大多数图书馆都有电脑终端，您可以使用它们访问目录。您输入书名或作者，目录会告诉您确切的书籍位置。这样，目录就像数据库索引。

索引的键是应用索引的列或列组。当且仅当其键包含查询谓词（即WHERE子句）中使用的一个或多个列时，索引才能加速查询。在图书馆里，如果您只知道书名，那么只按作者姓氏排序的书籍对您来说没有帮助。

B-树索引

B树索引是一种特殊的数据库索引，它以特定的方式帮助数据库定位记录。B树代表“平衡树”¹（而不是我曾经以为的“二叉树”）。B树索引根据键值（记住键是您感兴趣的列或列）对行进行排序，并将此有序列表划分为范围。这些范围以树状结构组织，根节点定义了一系列广泛的范围，下面每个级别定义了逐渐变窄的范围。

再次考虑我们的图书馆示例，想象一下图书馆里的书是完全按照作者的姓氏排列的。现在假设您要查找一本名为Osman的书。

进入图书馆后，您会发现一楼的书籍作者姓氏是A-G，二楼是H-N，三楼是O-U，四楼是V-Z。所以您直接去三楼查找Osman的书。在三楼，您看到一个标牌描述了这一层的书籍排列方式。有一个书架是O-R，另一个书架是S-U，所以您走向O-R书架。在这个书架上，每个字母都有一个架子，所以您找到了O架，这里的书是按字母顺序排列的，这样您就可以快速找到Osman的书了。

现在让我们考虑等效的数据库搜索。想象一下，图书馆里的所有书籍都包含在一个Books数据库表中，并在author_surname列上有一个B树索引。要查找Osman的书，您可能会执行以下查询

SELECT * FROM Books WHERE author_surname = ‘Osman’ 

首先，数据库会检查B树索引的根节点，它可能定义了四个范围，对应于我们在图书馆的四个楼层（A-G、H-N、O-U、V-Z）。然后它会进入树中下一层的节点，代表O-U范围，对应于我们图书馆的三楼。在这个节点内会有进一步的范围（O-R、S-U），对应于三楼的书架，依此类推。

B树中的每个节点都称为块。除了最后一层之外，树中每一层的块都称为分支块，最后一层的块称为叶块。分支块中的条目包含一个范围和一个指向树中下一层块的指针。叶块中的每个条目代表一行，包含一个键值（例如，“Osman”）和一个rowid，数据库使用该rowid来获取相关行中包含的所有其他数据。

遍历叶节点

除了上下遍历B树之外，数据库还可以横向遍历叶节点。这在处理包含索引列的ORDER BY子句的查询时很有用。考虑以下查询

SELECT * FROM Books ORDER BY author_surname 

有了B树索引，数据库可以简单地从树的第一个叶节点开始，按顺序横向遍历所有叶节点，以获取请求的有序集合。没有这个索引，按姓氏对行进行排序显然会是一个更复杂、更慢的操作。

当执行返回基于谓词的行范围的查询时，从一个叶节点遍历到另一个叶节点也很有用。例如，考虑以下查询

SELECT * FROM Books WHERE author_surname > ‘O’

使用B树索引，数据库将从根节点向下遍历树，直到找到包含作者姓氏以“O”开头的行的叶节点，然后只需向右遍历所有剩余的叶节点即可获取“P”、“Q”等作者的书籍。

结束语

您可以配置B树索引的多种方式来满足您的特定需求。在Oracle中，您可能需要研究索引组织的表、反向键索引、降序索引和B树集群索引。此外，您可能还想考虑位图索引，它是B树索引的替代方案。这些主题可能在未来的博客文章中介绍，但希望本文能为您提供B树索引的快速入门。

¹事实上，关于B在B树中代表什么存在一些争论。我的“平衡”定义来自Oracle文档。

这篇B树索引文章最初发布在The Proactive Programmer上。