26｜B+ Tree：PostgreSQL 的索引是如何建立的？

Feb 22, 2022

26｜B+ Tree：PostgreSQL 的索引是如何建立的？-业务开发算法50讲-极客时间



下载APP





关闭

渠道合作

推荐作者

26｜B+ Tree：PostgreSQL 的索引是如何建立的？

黄清昊 · 业务开发算法50讲

课程介绍



讲述：黄清昊

时长15:08大小13.83M



你好，我是微扰君。
过去几讲我们学习了一些经典的分布式算法，主要涉及多个节点之间的协作方式，在现在的业务场景下，它们更多被封装在各种中间件或者类库中，直接供我们使用，不过背后的很多思想还是很值得好好学习体悟的。
从今天开始，我们将更加贴近日常业务开发，剖析常用中间件里用到的、单机上的一些算法，帮助自己更好地分析和优化系统性能。比如在使用数据库的时候，如果我们不清楚底层索引的原理，写出来的查询语句可能性能会很差，甚至不见得能正确建立索引；再比如有时候我们希望不引入额外的网关组件，直接在业务代码里实现一个简单的限流模块，如何设计更合适……
类似场景还有很多，话不多说，今天我们一起来了解这些中间件的秘密。
数据库我们先从数据库聊起。数据库，应该是我们广大程序员日常开发中必不可少的组件了，作为数据持久化的基石，在互联网应用中，大部分的业务数据都以结构化的方式存储在数据库中，而数据库为我们提供了良好的数据查询、管理、持久化、事务的能力。
在数据库场景下，我们存储的都是大量的数据，显然没有办法一次性把所有的数据全部加载到内存中，用内存高效的数据结构或者算法进行搜索。那数据库是如何快速查询数据的呢？比如：
select * from student where id = 5130309492
如果我们逐一遍历数据库的每个记录逐个对比，也就是常说的“全表扫描”，查找速度肯定很慢。如何提高查找指定 ID 记录的速度呢？
通常为了提高查找速度，我们都会设计一种特殊的数据结构，在内存中如此，在磁盘中也不例外。我们需要设计一种适合磁盘场景的数据结构，对业务数据进行某种有序性的维护，在磁盘读写次数不多的情况下，结合内存，就能快速找到需要查询的记录在磁盘中所在的位置。这就是我们常说的“索引”。
那索引一般是用什么样的数据结构实现的呢？
其实在之前学习 Kafka的时候，我们学过线性稀疏的索引，适用于 append only 的存储模式，利用有序性带来的二分搜索，帮助我们加速查找指定 offset 的日志内容，你可以再回顾一下理解索引背后用空间换时间的思想。
但是 kafka 的索引，在数据库的场景下并不好用，因为数据库中，我们随时可能需要删除或者修改某个字段的值，如果要保持索引的线性有序性的要求，就要不断调整索引文件的前后顺序，在磁盘上，这个代价是非常高的。
所以，为了能适配需要随机修改插入的数据库场景，我们的索引结构不能是线性的了。
树状索引如果你熟悉第一章的内容，估计很快就会想到红黑树这样的结构。
在内存中，红黑树任意字段的查询可以做到 logN 的复杂度，而且相比于二分搜索所需具备的有序性，在红黑树上做元素的调整和增删效率要高得多。我们之前也提到了，对于百万量级的存储场景，红黑树也只需要 20 层这个数量级的高度就可以容纳全部元素。查询效率当然是很有保证的。
那可不可以在数据库的索引中采用红黑树呢？
因为在数据库中，不同于内存的场景，磁盘读写比内存慢的多，所以相比于查询的计算成本，IO 成本可能要显著的多。
数据库里存储的数据比较多，如果我们采用二叉树来存储的话，层数必然不会很少，且层和层之间的数据在物理上基本上是不连续的，即使前几层的元素可以被预加载至内存中，我们仍然可能需要在树上进行 10 余次的跳转查询，也就对应着 10 余次的磁盘 IO，这是不可接受的。
有没有什么办法利用磁盘读写的特性，既可以保持树状结构的灵活性，又同时降低查询的 IO 次数呢？这就是 B+ 树的用武之地了，核心就是通过引入更多的分叉，在节点同样数量级的范围内，显著地降低树状索引的层数。
B- 树 B+ 树B+ 树是传统关系型数据库索引的标配，在 MySQL、PostgreSQL 等主流 DBMS 中，B+ 树都是索引的底层实现。
B+ 树是由 B- 树演化而来，这里的 B 一般被解读为 balance，也就是平衡树，和之前介绍的 2-3 树差不多，B- 树、B+ 树每个节点也包含多个键和多条链。
我们先看 B- 树，这个数据结构就是为大量数据的存储和快速访问而设计的。B- 树的每个节点都包含若干个键和若干个指针域，指针域就用于指向存储的数据本身。m 阶 B- 树的主要约束还包括：
所有叶子结点处于同一高度；
除了根结点和叶子结点之外，每个节点最少包含 m/2 个键；
每个节点最多包含 m-1 个键和 m 条链，如果某个节点有 k-1 个键，则对应 k 条链；
每个节点内部的键有序排列，每个链指向的节点中的键，都在链左右节点的确定范围之间；
根节点在不为叶子节点的时候至少有两个子节点。
下图就是一个典型 3 阶 B- 树的例子，可以看出，2-3 树是一种特殊的 B- 树。
在数据库场景下，毫无疑问，我们会把建立索引的字段作为 key，每个 key 后面也会跟上对应记录的指针。
为什么磁盘上的 B- 树会比对应的二叉平衡树快很多呢？主要就是利用了磁盘访问的局部性原理。
之前讲 LRU 的时候也提到了相关概念，计算机在读取磁盘的时候，往往是以页为单位读取的，读取某一页中的部分内容和读取该中的全部内容，所花费的代价其实是一样的。如果我们把 B- 树的每个节点中存储的大小设成一个页的大小，利用磁盘预读的能力，就可以做到仅通过一次 IO 就将整个节点的全部内容加载到内存中。
一个页的大小通常是 4K～16K，能包含的键数可以高达几千条。以 InnoDB 通常采用的 16K 大小的页为例，如果我们的索引字段和指针域大小为 8B，B- 树上的每个节点能包含的键数高达 2048 个，这就意味着用 4 层的高度，就可以存储接近 10 亿级别的记录，在索引字段大小更大的时候，我们通常也只需要 5 层以内，就可以构造大部分表的索引。
这就是多叉的 B 树的主要优点了，利用磁盘的预读能力和树状结构，我们通过 3～5 次磁盘 IO 就可以在 10 亿级的数据表中进行快速检索了。
检索过程的伪代码如下：
基本上和 2-3 树或者普通二叉树的检索思路是一致的：从根节点出发进行遍历，如果在某个节点中查到了目标键，直接返回；如果查到的目标值在两个键之间，就进入两键之间的链所指向的节点进行下一层的查找。
因为每个节点中的键是有序存储的，当我们加载到内存中后，通常也会直接采用二分搜索，整个搜索过程仍然是 logN 这样非常低的复杂度。所以主要耗时还是花费在 IO 中。
B+ 树通常数据库中采用的索引结构都是 B+ 树，B+ 树和 B- 树的区别主要在于树节点的组织形式，包括两点：
B+ 树的所有的叶子节点之间会通过双向指针串联在一起，构成一个双向链表；
B+ 树的中间节点不会存储数据指针，而只有叶子节点才会存储，中间节点只用于存储到叶子节点的路由信息。
这个图就是一个典型的 3 阶 B+ 树了。可以看到，红色的非叶子节点和绿色的叶子结点的键会有一定的重合，这就是因为非叶子结点不再存储实际的数据信息，所以叶子结点实际上需要存储整张表的信息，但因为树状结构的特性，两者的层数预期仍然都是 logN。
同时，因为非叶子节点中不再需要存储数据本身相关的信息，每个节点能存储的键的数量也会有所增加，所以 B- 树和 B+ 树的层数期望是差不多的，在大部分业务场景下，3～5 次的 IO 查询就可以让我们查询到任意目标值。
那为什么要引入这样额外的指针和约束呢？主要原因在于在数据库中我们经常需要范围查询，比如这样的查询语句，查询所有年龄小于 20 的学生：
select * from students where age < 20
因为 B+ 树的特性，叶子节点之间也一定是有序排列的，我们只需要找到比 20 小的第一个元素，借助双向链表，我们从链表头遍历到这个元素，就能快速获得所有比 20 小的元素。这样高效的范围查询能力是 B- 树所没有的。
当然了，如果能让叶子结点的指向数据，能在磁盘上连续存储，当然可以获得更好的查询能力，不过这件事情非常困难，似乎没有什么太好的办法。
好有了 B+ 树这样的结构，我们已经可以做到快速查询了，但是数据库中的元素是会被时刻修改的，如何在增删改操作中维持 B+ 树的性质呢？我们一起来看一下。
插入操作为了方便演示和讨论，我们用比较简单的 3 阶 B+ 树来讲解，和 2-3 树的过程非常相似我们重点看如何通过节点的合并和分裂操作，应对树结构的变化。
假设我们的树一开始只有 1、2 两个键，此时键的数量没有超过单节点能容纳的范围，我们用一个叶子结点就可以表示。
接下来要加入一个 3 节点，和 2-3 树一样，我们就需要对原来的叶子节点做分裂操作，因为 3 阶 B+ 树，每个节点最多能承载的元素就是 2 个。现在多出来一个键，我们就需要把节点中键的中位数取出来，提高到上一层，然后分成左右两个部分，每个部分都包括 m/2 个节点。
这里，对于 3 阶 B+ 树而言，左子节点就分到一个键，右子节点则分到两个键。叶子节点间，我们同样需要用双链表的方式进行串联。
我们尝试继续添加键，现在添加键 4 到树里，首先要做的就是进行前面提到的 B 树的查询，我们会查询到最右侧的叶子结点，从而试图将键 4 放入 (2,3) 构成的节点中，但同样由于每个节点最多存放 2 个键，所以我们需要把 3 提高到上一层，把原来的节点拆成 2 和 (3,4) 两个节点。
后面的添加就是类似的过程，如果继续添加键 5，同样会先放入 (3,4) 节点中，把 4 提高到根节点，而根节点也已经“满载”了，所以会把中间值 3 提到更上一层，此时我们就得到了一个三层的树。
整个分裂节点的过程自底向上递归进行，可以注意到所有叶子节点的高度其实是始终不变的。
删除操作删除操作看起来要稍微复杂一点，不能简单理解成插入过程的逆过程。我们用刚才构造出的树来演示几种不同的删除操作。
首先我们尝试删除键 2。因为存储 2 的节点本身只存储了一个键，如果删去，2 节点所存储的键数量不满足约束条件了，这个时候我们有两种选择：
一种是如果本身左侧的兄弟节点存储有多余的键，比如存储了 2 个键，我们就可以很简单地直接借用一个键；
另一种则需要让父节点下移，并合并子节点。
在这个例子中，左侧存放 key1 的节点也只有一个键，所以不满足可以借用的情况，我们只能考虑让父节点 3 下沉，和 4 节点合并。
这样我们就可以重新得到一颗平衡的 B+ 树了。每次让父节点下沉，也可能重新破坏父节点的约束条件，我们同样要递归地找左侧兄弟节点借用键或者考虑让更上层的父亲节点下沉，直到整颗树满足约束为止。
第二种我们继续在这棵树上删除键 5，这个情况比较简单，可以直接删除键 5，并不会破坏原来的约束。
在数据库中数据有插入或者删除的时候，我们就可以及时地调整索引内部的结构了。当然可以想见这其中会有很多并发的问题，比较复杂，通常需要加锁解决，也是研究的热点之一，这次就不展开讨论了。
总结今天我们一起学习了非常经典的索引实现方式，利用空间换时间的思路，通过为数据表建立额外的有序索引结构，做到大大加速查询的效果。
由于数据库需要经常对数据进行增删改，我们的索引数据结构要能高效地变动，而且数据库本身海量的数据也意味着，索引结构不会只存在内存中，需要在二级存储中存储。相比于传统的二叉搜索树，通过 B+ 树，我们可以让整个树状结构变得更加矮胖，而磁盘的预读特性每次都可以加载一整个节点中全部的键，到内存进行二分查找，这样我们只需要通过 3～5 次的磁盘 IO 就可以查询加了索引的字段，非常高效。
B+ 树，相比于 B- 树的主要特点就是，只在叶子结点存储数据，而且叶子节点间用首尾相连的指针串联成双向链表，可以获得良好的范围查询的效果，背后的本质就是索引和数据的分离，这同样是非常值得好好体会的一种思想。
思考题我们说平衡树的约束之一是每个节点的键不能少于 m/2 也不能多于 m，这里 m/2 是怎么来的呢？ 不知道你有没有深入思考过，如果能回答清楚这个问题，我想你对 B+ 树索引的分裂策略就理解地很深刻了。
欢迎你在评论区留下你的思考，如果觉得有帮助的话，也欢迎你把这篇文章转给你身边的好朋友，一起学习。下节课见。

B+树在数据库索引中的重要性和应用价值是本文的重点。文章首先介绍了数据库索引的作用，以及线性稀疏的索引和红黑树在内存中的应用。随后详细介绍了B-树和B+树的结构和特点，以及B+树相对于B-树的优势，包括利用磁盘预读能力和树状结构降低查询的IO次数。文章还给出了B+树的检索过程伪代码，强调了其在大数据表中进行快速检索的优势。此外，文章还讨论了B+树的插入和删除操作，以及B+树在数据库中的高效变动和存储特性。总的来说，B+树通过空间换时间的思路，为数据表建立有序索引结构，加速查询效果，特别适用于数据库中需要频繁增删改数据的场景。文章内容深入浅出，对于读者理解数据库索引和优化系统性能具有一定的参考意义。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

2022-02-22

赞 3

提建议

25｜一致性哈希：如何在集群上合理分配流量？

27｜LSM Tree：LevelDB的索引是如何建立的？

 写留言

全部留言(3)

最新
精选

麋鹿在泛舟
2022-03-06
不能少于m/2实际上是和约束"不能多余m"对称的，当一个叶子节点索引个数为m个，触发了m阶B+树的分裂操作，而分裂后的两个叶子节点元素的个数应该是m/2个： * 如叶子节点最少数量比m/2还大，那么就返回分裂和合并了。 * 如叶子节点最少的数量比m/2小很多，那么会大幅度降低合并的效率，导致很多少元素叶子节点。
作者回复: 写得很好哦～
4
那时刻
2022-02-22
我觉得m/2类似于二分查找里的采用二分而不是三分，更快的达到均衡。另外一个观点是从信息论角度来看，二分的墒最大。
Paul Shan
2022-02-22
个人觉得这里每个节点包含的键值至少m/2,m/3,2*m/3对于查询的量级没有影响，都是lg n，m/2实现最简单，所以被选择。m/3的实现除了实现复杂还会增加层数，也就是io访问次数，最先被排除。2*m/3能够让某些情况下层数比m/2会少一些，但是意义不大，因为选择m本身已经降低了层数，选择合适的m，层数的问题已经解决，没有必要再在因子增加新的选择，2*m/3选择会让树的调整次数增加，实现复杂度增加。请问老师实际情况是不是这样?
展开

