24丨索引的原理：我们为什么用B+树来做索引？

Aug 5, 2019

24丨索引的原理：我们为什么用B+树来做索引？-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

24丨索引的原理：我们为什么用B+树来做索引？

2019-08-05 陈旸来自北京

《SQL必知必会》

课程介绍



讲述：陈旸

时长11:07大小10.19M



上节课我讲到了索引的作用，是否需要建立索引，以及建立什么样的索引，需要我们根据实际情况进行选择。我之前说过，索引其实就是一种数据结构，那么今天我们就来看下，索引的数据结构究竟是怎样的？对索引底层的数据结构有了更深入的了解后，就会更了解索引的使用原则。
今天的文章内容主要包括下面几个部分：
为什么索引要存放到硬盘上？如何评价索引的数据结构设计的好坏？
使用平衡二叉树作为索引的数据结构有哪些不足？
B 树和 B+ 树的结构是怎样的？为什么我们常用 B+ 树作为索引的数据结构？
如何评价索引的数据结构设计好坏数据库服务器有两种存储介质，分别为硬盘和内存。内存属于临时存储，容量有限，而且当发生意外时（比如断电或者发生故障重启）会造成数据丢失；硬盘相当于永久存储介质，这也是为什么我们需要把数据保存到硬盘上。
虽然内存的读取速度很快，但我们还是需要将索引存放到硬盘上，这样的话，当我们在硬盘上进行查询时，也就产生了硬盘的 I/O 操作。相比于内存的存取来说，硬盘的 I/O 存取消耗的时间要高很多。我们通过索引来查找某行数据的时候，需要计算产生的磁盘 I/O 次数，当磁盘 I/O 次数越多，所消耗的时间也就越大。如果我们能让索引的数据结构尽量减少硬盘的 I/O 操作，所消耗的时间也就越小。
二叉树的局限性二分查找法是一种高效的数据检索方式，时间复杂度为 O(log2n)，是不是采用二叉树就适合作为索引的数据结构呢？
我们先来看下最基础的二叉搜索树（Binary Search Tree），搜索某个节点和插入节点的规则一样，我们假设搜索插入的数值为 key：
如果 key 大于根节点，则在右子树中进行查找；
如果 key 小于根节点，则在左子树中进行查找；
如果 key 等于根节点，也就是找到了这个节点，返回根节点即可。
举个例子，我们对数列（34，22，89，5，23，77，91）创造出来的二分查找树如下图所示：
但是存在特殊的情况，就是有时候二叉树的深度非常大。比如我们给出的数据顺序是 (5, 22, 23, 34, 77, 89, 91)，创造出来的二分搜索树如下图所示：
你能看出来第一个树的深度是 3，也就是说最多只需 3 次比较，就可以找到节点，而第二个树的深度是 7，最多需要 7 次比较才能找到节点。
第二棵树也属于二分查找树，但是性能上已经退化成了一条链表，查找数据的时间复杂度变成了 O(n)。为了解决这个问题，人们提出了平衡二叉搜索树（AVL 树），它在二分搜索树的基础上增加了约束，每个节点的左子树和右子树的高度差不能超过 1，也就是说节点的左子树和右子树仍然为平衡二叉树。
这里说一下，常见的平衡二叉树有很多种，包括了平衡二叉搜索树、红黑树、数堆、伸展树。平衡二叉搜索树是最早提出来的自平衡二叉搜索树，当我们提到平衡二叉树时一般指的就是平衡二叉搜索树。事实上，第一棵树就属于平衡二叉搜索树，搜索时间复杂度就是 O(log2n)。
我刚才提到过，数据查询的时间主要依赖于磁盘 I/O 的次数，如果我们采用二叉树的形式，即使通过平衡二叉搜索树进行了改进，树的深度也是 O(log2n)，当 n 比较大时，深度也是比较高的，比如下图的情况：
每访问一次节点就需要进行一次磁盘 I/O 操作，对于上面的树来说，我们需要进行 5 次 I/O 操作。虽然平衡二叉树比较的效率高，但是树的深度也同样高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。
针对同样的数据，如果我们把二叉树改成 M 叉树（M>2）呢？当 M=3 时，同样的 31 个节点可以由下面的三叉树来进行存储：
你能看到此时树的高度降低了，当数据量 N 大的时候，以及树的分叉数 M 大的时候，M 叉树的高度会远小于二叉树的高度。
什么是 B 树如果用二叉树作为索引的实现结构，会让树变得很高，增加硬盘的 I/O 次数，影响数据查询的时间。因此一个节点就不能只有 2 个子节点，而应该允许有 M 个子节点 (M>2)。
B 树的出现就是为了解决这个问题，B 树的英文是 Balance Tree，也就是平衡的多路搜索树，它的高度远小于平衡二叉树的高度。在文件系统和数据库系统中的索引结构经常采用 B 树来实现。
B 树的结构如下图所示：
B 树作为平衡的多路搜索树，它的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶。同时你能看到，每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了 x 个关键字，那么指针数就是 x+1。对于一个 100 阶的 B 树来说，如果有 3 层的话最多可以存储约 100 万的索引数据。对于大量的索引数据来说，采用 B 树的结构是非常适合的，因为树的高度要远小于二叉树的高度。
一个 M 阶的 B 树（M>2）有以下的特性：
根节点的儿子数的范围是[2,M]。
每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为[ceil(M/2), M]。
叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为[ceil(M/2), M]。
假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key[i]<Key[i+1]。此时 k-1 个关键字相当于划分了 k 个范围，也就是对应着 k 个指针，即为：P[1], P[2], …, P[k]，其中 P[1]指向关键字小于 Key[1]的子树，P[i]指向关键字属于 (Key[i-1], Key[i]) 的子树，P[k]指向关键字大于 Key[k-1]的子树。
所有叶子节点位于同一层。
上面那张图所表示的 B 树就是一棵 3 阶的 B 树。我们可以看下磁盘块 2，里面的关键字为（8，12），它有 3 个孩子 (3，5)，(9，10) 和 (13，15)，你能看到 (3，5) 小于 8，(9，10) 在 8 和 12 之间，而 (13，15) 大于 12，刚好符合刚才我们给出的特征。
然后我们来看下如何用 B 树进行查找。假设我们想要查找的关键字是 9，那么步骤可以分为以下几步：
我们与根节点的关键字 (17，35）进行比较，9 小于 17 那么得到指针 P1；
按照指针 P1 找到磁盘块 2，关键字为（8，12），因为 9 在 8 和 12 之间，所以我们得到指针 P2；
按照指针 P2 找到磁盘块 6，关键字为（9，10），然后我们找到了关键字 9。
你能看出来在 B 树的搜索过程中，我们比较的次数并不少，但如果把数据读取出来然后在内存中进行比较，这个时间就是可以忽略不计的。而读取磁盘块本身需要进行 I/O 操作，消耗的时间比在内存中进行比较所需要的时间要多，是数据查找用时的重要因素，B 树相比于平衡二叉树来说磁盘 I/O 操作要少，在数据查询中比平衡二叉树效率要高。
什么是 B+ 树B+ 树基于 B 树做出了改进，主流的 DBMS 都支持 B+ 树的索引方式，比如 MySQL。B+ 树和 B 树的差异在于以下几点：
有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数 +1。
非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。
非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中，非叶子节点既保存索引，也保存数据记录。
所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。
下图就是一棵 B+ 树，阶数为 3，根节点中的关键字 1、18、35 分别是子节点（1，8，14），（18，24，31）和（35，41，53）中的最小值。每一层父节点的关键字都会出现在下一层的子节点的关键字中，因此在叶子节点中包括了所有的关键字信息，并且每一个叶子节点都有一个指向下一个节点的指针，这样就形成了一个链表。
比如，我们想要查找关键字 16，B+ 树会自顶向下逐层进行查找：
与根节点的关键字 (1，18，35) 进行比较，16 在 1 和 18 之间，得到指针 P1（指向磁盘块 2）
找到磁盘块 2，关键字为（1，8，14），因为 16 大于 14，所以得到指针 P3（指向磁盘块 7）
找到磁盘块 7，关键字为（14，16，17），然后我们找到了关键字 16，所以可以找到关键字 16 所对应的数据。
整个过程一共进行了 3 次 I/O 操作，看起来 B+ 树和 B 树的查询过程差不多，但是 B+ 树和 B 树有个根本的差异在于，B+ 树的中间节点并不直接存储数据。这样的好处都有什么呢？
首先，B+ 树查询效率更稳定。因为 B+ 树每次只有访问到叶子节点才能找到对应的数据，而在 B 树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字，而有时需要访问到叶子节点才能找到关键字。
其次，B+ 树的查询效率更高，这是因为通常 B+ 树比 B 树更矮胖（阶数更大，深度更低），查询所需要的磁盘 I/O 也会更少。同样的磁盘页大小，B+ 树可以存储更多的节点关键字。
不仅是对单个关键字的查询上，在查询范围上，B+ 树的效率也比 B 树高。这是因为所有关键字都出现在 B+ 树的叶子节点中，并通过有序链表进行了链接。而在 B 树中则需要通过中序遍历才能完成查询范围的查找，效率要低很多。
总结磁盘的 I/O 操作次数对索引的使用效率至关重要。虽然传统的二叉树数据结构查找数据的效率高，但很容易增加磁盘 I/O 操作的次数，影响索引使用的效率。因此在构造索引的时候，我们更倾向于采用“矮胖”的数据结构。
B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树，B+ 树在查询性能上更稳定，在磁盘页大小相同的情况下，树的构造更加矮胖，所需要进行的磁盘 I/O 次数更少，更适合进行关键字的范围查询。
今天我们对索引的底层数据结构进行了学习，你能说下为什么数据库索引采用 B+ 树，而不是平衡二叉搜索树吗？另外，B+ 树和 B 树在构造和查询性能上有什么差异呢？
欢迎你在评论区写下你的思考，也欢迎把这篇文章分享给你的朋友或者同事，一起来交流。

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

生成海报并分享

赞 21

提建议

23丨索引的概览：用还是不用索引，这是一个问题

25丨Hash索引的底层原理是什么？

 写留言

精选留言(43)

Goal
2019-08-05
一、数据库索引，为什么不适用用二叉树： 1. 平衡二叉树必须满足（所有节点的左右子树高度差不超过1）。执行插入还是删除操作，只要不满足上述条件，就要通过旋转来保持平衡，而旋转是非常耗时的，所以AVL树适合用于查找多的情况。 2. 二叉树的数据结构，会导致“深度”，比较深，这种“瘦高”的特性，加大了平均查询的磁盘IO次数，随着数据量的增多，查询效率也会受到影响；二、B+ 树和 B 树在构造和查询性能上有什么差异呢？ B+ 树的中间节点并不直接存储数据。 1. B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。 2. B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。 3、由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。
展开
作者回复: 很好的总结，大家都可以看下
共 4 条评论
95
Geek_6cfaa7
2019-08-05
有点疑惑，b+虽然每次都查到叶节点，看着很规律，但是b树有可能用更少的io就能访问到，不是按理来说更效率吗？这个有点不明白
共 17 条评论
20
Monday
2019-08-08
B树和B+树的区别： 1、B树非叶子结点存储数据；B+树非叶子结点不存储数据只存索引。 2、B树叶子结点没有使用双向链表串连；B+树叶子结点使用双向链表进行串连，为了支持区间查询。
作者回复: 对的
共 3 条评论
13
ack
2019-08-05
1.为什么数据库索引采用 B+ 树，而不是平衡二叉搜索树？数据库索引存储在磁盘上，平衡二叉树虽然查找效率高，但“高瘦”，进行的IO次数比平衡二叉搜索树多。 2.B+ 树和 B 树在构造和查询性能上差异？（1）B树的每个节点含有卫星数据，而B+树中间节点含有指向卫星数据的指针，叶子节点才存有卫星数据。这样一来每次进行B+树查询都需要查询到叶子节点，性能更稳定，而且B+树节点只存储指向卫星数据的指针，这样一个磁盘页能存储更多节点。（2）B+树范围查询更有优势，因为叶子节点直接串联成一条链表（3）B+树单一结点比起B树存储更多元素，IO更少
展开
作者回复: 整理的很好
共 3 条评论
12
mickey
2019-08-05
请问，文中的B树图，元素“68”是在“65”到“85”之间，为什么属于第一棵子树呢？
作者回复: 赞mickey同学很仔细，我fix下
共 8 条评论
9
吃饭饭
2019-08-05
【对于一个 100 阶的 B 树来说，如果有 3 层的话最多可以存储约 100 万的索引数据】是怎么计算出 100 万的，按照前面的描述指数是关键字的个数+1 没弄明白，求解答？
作者回复: 可以参考下蜗牛的解答：B树中， 100*100*100 + 100*100 +100 近似值 100w，因为主要的数据还是在叶子节点；
共 5 条评论
7
吴小智
2019-08-21
B+ 树中间节点只保存索引，不保存数据，所以一个节点能放更多的索引，同样的索引树，相比于 B 树，B + 树的深度会更少。
作者回复: 对的同样B+树在做数据检索的时候会更稳定
6
未来的胡先森
2019-08-14
为什么选用「 B+ 树」而不是「平衡二叉树」呢？老师在文章中已经给出了答案，「平衡二叉树」只有两个分支，而「 B+ 树」的分支大于等于 2，根据等比数列的公式可以得出，「 B+ 树」的层数只会小于「平衡二叉树」，层数越少，在查询时所需要的 I/O 操作（硬盘访问）就少，相对来说查询速度就快了，同时也提高了系统资源的利用率。「 B+ 树」和「 B 树」在构造和查询性能上的差别？老师在文章中也提到了，构造方面：最明显的莫过于「 B+ 树」非叶子结点并不存储数据，且所有数据节点串联（就是链表了），「 B 树」子结点带数据，且「兄弟结点」之间无串联。查询性能差异：我觉得很直观的体现在范围查询时，「 B+ 树」我们只需要知道范围的边界节点，然后遍历即可，而「 B 树」可能就需要一个个查找了。假设查询 [0,n-1] n 个数，「 B+ 树」的时间复杂度可以粗略看做 2logn+n (2logn : 两个范围边界值的查找)，而「 B 树」可能就是 nlogn ，范围越大，查询性能差异越明显。
展开
作者回复: 总结整理的不错大家都可以看下
3
夜路破晓
2019-08-05
记得刚接触编程的时候，很不习惯计数要从0开始，后来用围栏法勉强不会搞错计数顺序了，还是一直不解为什么要这样设计。今天看老师讲解b树和b＋树，有个类似发现，b树就好像很多人习惯了的从1开始计数，或者举例说要把一段绳子截成三段，你只需截2次即可； b ＋树就好比用围栏隔出若干空间，比如隔出两块空间需要三个围栏板，脑海里联想下公测的蹲坑隔间就能理解了。按我的理解b＋树之所以显示优于b树，可能跟前后两端的数据空间有关，这跟将数据序列设计成从0开始计数而非从1开始是出于同样的考量。
展开
作者回复: 多谢夜路破晓同学分享
4
许童童
2019-08-05
老师讲得好，深入浅出。
作者回复: 谢谢
4
王加武
2019-12-22
首先感谢前面认真学习数据结构的自己，这下不就用到了！所以学习这一节的时候就感觉非常爽！ 1、数据库索引为什么采用B+树而不采用平衡二叉搜索树？数据库的索引是存储在磁盘上的，每次查询都需要涉及I/O操作，I/O操作的次数越多，那么查询所化的时间就越长，性能也就越低，所以引入了平衡二叉搜索树来存储数据，本来平衡二叉搜索树的查询效率是非常高的，但是当数据量很大的时候，平衡二叉搜索树的高度就会很高，每次进行查询的时候也就需要经历很多的节点，自然也就增加了I/O操作的次数，严重的降低了性能，要是你查询的数据刚好在根节点那还好，都是一样的，但是这种情况的概率只有1%，属于极端情况(自己脑补)......所以在此引入了B+树这个数据结构（B树老师已经说得很清楚了，我就不说了），降低了树的高度，减少了I/O操作的次数，提高了查询的效率！ 2、B和B+树在构造上有什么差异吗？ B+树的查询效率更稳定的，因为每次都必须查询到叶子节点才能找到最终的数据，而B树查询的数据也许在叶节点上，也许在叶子节点上，这样就会造成查询的效率不稳定！ B+树的查询效率更高，因为B+树更矮更胖（肉多，哈哈），所以B+树的高度越小，查询时产生的I/O次数也就更少，性能自然就高！
展开
作者回复: 很好的总结，数据结构在算法中会经常用到
3
雪飞鸿
2019-09-18
网上还看到B-tree是和B tree一个意思吗？
作者回复: 是的都是B树的意思
共 2 条评论
3
JustDoDT
2019-08-05
这节厉害了，得多看几遍，慢慢消化。
作者回复: 感谢，B+树索引对于理解MySQL的索引机制来说确实比较重要
共 2 条评论
3
hlz-123
2019-08-05
老师的这节课，让我知道以前对数据库的索引理解有误，但我还是想问一下老师，以前，我认为数据库的数据是在存储在硬盘一些存储块中，索引是一个单独文件，另外存储，索引文件只包含关键字和指向数据地址的链接，查询时可以一次性或若干次将索引文件全部读入到缓存进行比较，不用在硬盘中去多次读，避免访问硬盘浪费时间，为什么不能这样呢？
作者回复: 下面asdf100同学的回答可以参考下
共 2 条评论
2
脱缰的野马__
2020-05-17
老师您好，我看老师在讲程序访问平衡二叉树时，就以文中例子来说，严格意义来说不一定每次访问节点都需要进行一次磁盘i/o吧？系统去磁盘或者去内存加载数据的时候都会根据局部性原理的空间局部性加载目标数据以及附近的数据
1
梁
2019-11-19
为什么使用B+而不是B？稳定压倒一切！
作者回复: 对的稳定是其中之一，综合效率也会更高
2
爱思考的仙人球
2019-10-20
B+树查询效率更稳定，磁盘I/O次数更少
作者回复: 对的
共 2 条评论
2
雪飞鸿
2019-10-11
文中所说的关键字怎么理解？
作者回复: 关键字实际上就是我们的索引键值，当我们按照索引进行数据查询的时候，就是对关键字进行的查找
2
极客时间
2019-10-08
还是没有弄清叶子节点和非叶子节点！？
作者回复: 一棵树，叶子节点就是最底层的叶子。
共 2 条评论
1
airmy丶
2019-09-19
B+树为什么将叶子节点构成一个链表的形式，应该是方便范围查找，就像老师举的例子，如果不是等值查找16 而是查找大于16小于30的情况，因为叶子节点之间已经构成链表的形式，即使数据不再同一个磁盘块，也可以通过链表偏移指针获取到数据而不用重新遍历B+树增大磁盘IO。
1

