这就是你要的 B+ 树？
共 6938字，需浏览 14分钟
·
2021-10-11 12:31
索引可以说是每个工程师的必备技能点，明白索引的原理对于写出高质量的 SQL 至关重要，今天我们就从 0 到 1 来理解下索引的原理，相信大家看完不光对索引还会对 MySQL 中 InnoDB 存储引擎的最小存储单位「页」会有更深刻的认识
从实际需求出发
假设有如下用户表:
CREATE TABLE `user` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`name` int(11) DEFAULT NULL COMMENT '姓名',
`age` tinyint(3) unsigned DEFAULT NULL COMMENT '年龄',
`height` int(11) DEFAULT NULL COMMENT '身高',
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='用户表';
可以看到存储引擎使用的是 InnoDB，我们先来看针对此表而言工作中比较常用的 SQL 语句都有哪此，毕竟技术是要为业务需求服务的，
1. select * from user where id = xxx
2. select * from user order by id asc/desc
3. select * from user where age = xxx
4. select age from user where age = xxx
5. select age from user order by age asc/desc
既然要查询那我们首先插入一些数据吧，毕竟没有数据何来查询
insert into user ('name', 'age', 'height') values ('张三', 20, 170);
insert into user ('name', 'age', 'height') values ('李四', 21, 171);
insert into user ('name', 'age', 'height') values ('王五', 22, 172);
insert into user ('name', 'age', 'height') values ('赵六', 23, 173);
insert into user ('name', 'age', 'height') values ('钱七', 24, 174);
插入后表中的数据如下：
不知你有没发现我们在插入的时候并没有指定 id 值，但 InnoDB 为每条记录默认添加了一个 id 值，而且这个 id 值是递增的，每插入一条记录，id 递增 1，id 为什么要递增呢，主要是为了查询方便，每条记录按 id 由小到大的顺序用链表连接起来，这样每次查找 id = xxx 的值就从 id = 1 开始依次往后查找即可
现在假设我们要执行以下 SQL 语句，MySQL 会怎么查询呢
select * from user where id = 3
页
如前所述，首先从 id 最小的记录也就是 id = 1 读起，每次读一条记录，将其 id 值与要查询的值比较，连续读三次记录于是找到了记录 3，注意这个读的操作，是首先需要把存储在磁盘的记录读取到内存然后再比较 id 的，从磁盘读到内存算一次 IO，也就是说此过程中产生了三次 IO，如果只是几条记录还好，但如果要比较的条数多的话对性能是非常严重的挑战，如果我要查询为 id = 100 的记录那岂不是要产生 100 次 IO？既然瓶颈在 IO，那该怎么改进呢，很简单，我们现在的设计一次 IO 只能读一条记录，那改为一次 IO 能读取 100 条甚至更多不就只产生一次 IO 了吗，这背后的思想就是程序局部性原理：当用到了某项数据时，很可能会用到与之相邻的数据，所以干脆把相依的数据一起加载进去（你从 id = 1 开始读，那很可能用到 id = 1 紧随其后的元素，于是干脆把 id = 1 ~ id = 100 的记录都加载进去）
当然一次 IO 的读取记录也并不是多多益善，总不能为了一条查询记录而把很多无关的数据都加载到内存吧，那会造成资源的极大浪费，于是我们采用了一个比较折中的方案，我们规定一次 IO 读取 16 K 的数据，假设为 100 条数据好了，这样如果我们要查询 id = 100 的记录，只产生了一次 IO 读（id=1~id=100 的记录），比起原来的 100 次 IO 提升了 100 倍的性能
我们把这 16KB 的记录组合称为一个页
页目录
一次 IO 会读取一个页，然后再在内存里查找页里的记录，在内存里查找确实比磁盘快多了，但我们仍不满意，因为如果要查找 id = 100 的记录，要先从 id = 1 的记录比较起，然后是id=2，…，id=100，需要比较 100 次，能否更快一点？
可以参照二分查找，先查找 id = (1+100)/2 = 50，由于 50 < 100，接着在 50~100 的记录中查，然后再在 75~100 中查，这样经过 7 次就可找到 id = 100 次的记录，比起原来的 100 次比较又提升了不少性能。但现在问题来了，第一次要找到 id = 50 的记录又得从 id = 1 开始遍历 50 次才能找到，能否一下就定位到 id=50 的记录呢，如果不能，哪怕第一次从 id = 30 或 40 开始查找也行啊
有什么数据结构能满足这种需求呢，还记得跳表不，每隔 n 个元素抽出一个组成一级索引，每隔 2*n 个元素组成二级索引。。。
如图示，以建立一级索引为例，我们在查找的时候先在一级索引查找，在一级索引里定位到了再到链表里查找，比如我们要找 7 这个数字，如果不用跳表直接在链表里查，需要比较 7 次，而如果用了跳表我们先在一级索引查找，发现只要比较 3 次，减少了四次，所以我们可以利用跳表的思想来减少查询次数，具体操作如下，每 4 个元素为一组组成一个槽（slot），槽只记录本组元素最大的那条记录以及记录本组有几条记录
现在假设我们想要定位 id = 9 的那条记录，该怎么做呢，很简单：首先定位记录在哪个槽，然后遍历此槽中的元素
定位在哪个槽，首先取最小槽和最大槽对应的 id（分别为 4， 12），先通过二分查找取它们的中间值为 (4+12)/2 = 8，8 小于 9，且槽 2 的最大 id 为 12，所以可知 id = 9 的记录在槽 2 里
遍历槽 2 中的元素，现在问题来了，我们知道每条记录都构成了一个单链表，而每个槽指向的是此分组中的最大 id 值，该怎么从此槽的第一个元素开始遍历呢，很简单，从槽 1 开始遍历不就行了，因为它指向元素的下一个元素即为槽 2 的起始元素，遍历后发现槽 2 的 第一个元素即为我们找到的 id 为 9 的元素
可以看到通过这种方式在页内很快把我们的元素定位出来了，MySQL 规定每个槽中的元素在 1~8 条，所以只要定位了在哪个槽，剩下的比较就不是什么问题了，当然一个页装的记录终究是有限的，如果页满了，就要要开辟另外的页来装记录了，页与页之间通过链表连接起来，但注意看下图，为啥要用双向链表连接起来呢，别忘了最开头我们列出的 「order by id asc 」和「order by id desc 」这两个查询条件，也就是说记录需要同时支持正序与逆序查找，这就是为什么要使用双向链表的原因
B+ 树的诞生
现在问题来了，如果有很多页，该怎么定位元素呢，如果元素刚好在前几个页还好，大不了遍历前几个页也很快，但如果要查 id = 100w 这样的元素一页页遍历的话就要遍历 1w 页（假设每页 100 条记录），那显然是不可接受的，如何改进呢，其实之前建的页内目录已经给了我们启发，既然在页内我们可以通过为记录建页目录的形式来先定位元素在哪个槽然后再找，那针对多页，能否先定位元素在哪个页呢，也就是说我们可以为页也建立一个目录，这个目录里的每一条记录都对应着页及页中的最小记录，当然这个目录也是以页的形式存在的，为了便于区分 ，我们把针对页生成的目录对应的页称为目录页，而之前存储完整记录的页称为数据页
画外音：目录页与数据页一样，内部也是有槽的，上文为了方便展示，没有画出，目录页和数据除了记录数据不一样，其他结构都是一致的
现在如果要查找 id = xxx 的记录就很简单了，只要先到目录页中定位它的起始页然后再依次查找即可，由于不管是目录页还是数据页里面都有槽，所以无论是定位目录页的页码还是定位数据页中的记录都是非常快的。
当然了，随着页的增多，目录页存放的记录也越来越多，目录页也终归会满的，那就再建一个目录页吧，于是现在问题来了，怎么定位要找的 id 是在哪个目录页呢，再次制定针对目录页的目录页不就行了，如下
看到上面这个结构你想到了什么？没错，这就是一颗 B+ 树！到此相信你已经明白了 B+ 树的演进之路，也明白了它的原理，可以看到这颗 B+ 树有三层，我们把最顶层的目录页称为根节点，最下层的存储完整记录的页称为叶子节点，
现在我们再来看一下如何查找 id = 55 的记录，首先会加载根节点，发现应该在页码 30 的页中去找，于是加载页 30，在页 30 中又发现应该在页 4 中查中，于是再次把页 4 加载进内存中，然后在页 4 中依次遍历查找，可以看到总共经历了 3 次 IO（B+树有几层就会有几次 IO），页读取之后会缓存在内存中，再读的话如果命中内存中的页就会直接从内存中获取。有人可能会问，如果 B+ 树层数很多，那岂不是可能会有很多次 IO，我们简单的算一下，假设数据页可以存储 100 条记录，目录页可以存储 1000 条记录（目录页由于只存储了主键，不存储完整的数据，所以可以存储更多的记录），那么
如果
B+树只有 1 层，也就是只有 1 个用于存放用户记录的节点，最多能存放100条记录。如果
B+树有 2 层，最多能存放1000×100=100000条记录。如果
B+树有 3 层，最多能存放1000×1000×100=100000000条记录。如果
B+树有 4 层，最多能存放1000×1000×1000×100=100000000000条记录！
所以一般3~4 层的 B+ 树足以满足我们的要求，而且每次读取后会缓存在内存中（当然也会根据一定的算法被换出内存），所以整体来看 3~4 层 B+ 树足以满足我们需求
聚簇索引与非聚簇索引
相信你已经发现了，上文中我们举的 B+ 树的例子针对的是 id 也就是主键的索引，不难发现主键索引中的叶子结点存储了完整的 SQL 记录，我们把这种存储了完整记录的索引称为聚簇索引，只要你定义了主键，那么主键索引就是聚簇索引。
那么如果是非主键的列创建的索引又是怎样的形式呢，非叶子节点的形式完全一样，但叶子节点的存储则有些不同，非主键列索引叶子节点上存储的是索引列及主键值，比如我们假设对 age 这个列建立了索引，那么它的索引树如下
可以看到非叶子节点保存的是「age 值 + 页码」，而叶子节点保存的是 「age 值+主键值」,那么你可能就会疑惑了，如下 SQL 是怎么取出完整记录的呢
select * from user where age = xxx
第一步大家都知道，上述 SQL 可以命中 age 列对应的索引，然后找到叶子节点上对应的记录（如果有的话），但叶子节点上的记录只有 age 和 id 这两列，而你用的是 select *，意味着要查找 user 的所有列信息，该怎么办呢，答案是根据拿到的 id 再到聚簇索引找 id 对应的完整记录，这就是我们所说的回表，如果回表多的话显然会造成一定的性能问题，因为 id 可能分布在不同的页中，这意味着要将不同的页从磁盘读入内存，这些页很可能不是相邻的，也就意味着会造成大量的随机 IO，会严重地影响性能，看到这相信大家不难明白一道高频面试题：为什么设置了命中了索引但还是造成了全表扫描，其中一个原因就是虽然命中了索引但在叶子节点查询到记录后还要大量的回表，导致优化器认为这种情况还不如全表扫描会更快些
有人可能会问，为啥都二级索引不存储完整的记录呢，当然是为了节省空间，毕竟完整的数据是很耗空间的，如果每加一个索引都要额外存储完整的记录，那会造成很多数据冗余。
怎么避免这种情况呢？索引覆盖，如果如下 SQL 满足你的需求，那么就建议采用如下形式
select age from user where age = xxx
select age,id from user where age = xxx
不难发现这种 SQL 的特点是要获取的列（age）就是索引列本身（包括 id），这样在根据 age 的索引查到叶子节上对应的记录后，由于记录本身就包含了这些列，就不需要回表了，能提升性能
磁盘预读
接下来我们讨论一个网上很多人搞不拎清的一个问题，我们知道操作系统是以页为单位来管理内存的，在 Linux 中，一页的大小默认为 4 KB，也就是说无论是从磁盘载入数据到内存还是将内存写回磁盘，操作系统都会以页为单位进行操作，哪怕你只对一个空文件只写入了一个字节，操作系统也会为其分配一个页的大小（ 4 KB）
如图示，向磁盘写入了两个 byte ，但操作系统依然为其分配了一个页（4 KB）的大小
innoDB 也是以页为单位来存储与读取的，而 innoDB 页的默认大小为 16 KB，那么网上很多人的疑问是这是否意味着它需要执行 4 次 IO 才能把 innoDB 的页读完呢?不是的，只需要一次 IO，为什么？这需要理解一点磁盘读取数据的工作原理
磁盘的构造
首先我们来看看磁盘的物理结构
硬盘内部主要部件为磁盘盘片、传动磁臂、读写磁头和转轴，数据主要写入磁盘的盘片上的，盘片又是由若干个扇区构成的，数据写入读取都是以扇区为基本单位的，另外以盘片中心为圆心，把盘片分成若干个同心圆，那每一个划分圆的“线条”，就称为磁道
那么数据是如何读取与写入的呢，主要有三步
寻道：既然数据是保存在扇区上的，那我首先我们需要知道它到底是在哪个扇区上吧，这就需要先让磁头移动到扇区所在的磁道上，我们把它称为寻道时间，平均寻道时间一般在3-15ms
旋转延迟: 磁盘移动到扇区所在的磁盘上时，此时的磁头对准的还不一定我们想要的数据对应的扇区，所以需要等待盘片旋转片刻，等到我们想要的数据对应的扇区落到磁头下，旋转延迟取决于磁盘转速，通常用磁盘旋转一周所需时间的1/2表示。比如：7200rpm的磁盘平均旋转延迟大约为60*1000/7200/2 = 4.17ms，而转速为15000rpm的磁盘其平均旋转延迟为2ms
数据传输:经过前面的两步，磁头终于开始读写数据了，目前IDE/ATA能达到133MB/s，SATA II可达到300MB/s的接口数据传输率，数据传输时间通常远小于前两部分消耗时间。可忽略不计
注意数据传输中的忽略不计是有前提的，即是需要读取连续相邻的扇区，也就是我们常说的顺序 IO，磁盘顺序 IO 的读写速度可以媲美甚至超越内存的随机 IO，所以这部分时间可以忽略不计，（大家熟知的 Kafka 之所以性能强悍，有一个重要原因就是利用了磁盘的顺序读写），但如果要读取的数据是分布在不同的扇区的话，也就变成了随机 IO，随机 IO 毫无疑问增大了寻道时间和旋转延迟，性能是非常堪忧的（典型代表就是上文提到的 回表时大量 id 分布在不同的页上，造成了大量的随机 IO）
如图示：图片来自著名学术期刊 ACM Queue 上的性能对比图，可以看到磁盘顺序 IO（Sequential Disk）的速度比内存随机读写（Random memory）还快
那读取 innoDB 中的一个页为啥算一次 IO 呢，相信你已经猜到了，因为这一个页是连续分配的，也即意味着它们的扇区是相邻的，所以它是顺序 IO
操作系统是以页为单位来管理内存的，它可以一次加载整数倍的页，而 innoDB 的页大小为 16KB，刚好是操作系统页（4KB）的 4 倍，所以可以指定在读取的起始地址连续读取 4 个操作系统页，即 16 KB，这就是我们说的磁盘预读，至此相信大家不难明白为啥说读取一页其实只是一次 IO 而不是 4 次了
总结
看完本文相信大家能明白索引的由来了，此外对页以及磁盘预读对性能的提升应该也有不少了解，其实 MySQL 的页结构与我们推演的结构有些许出入，不过不影响整体的理解，如果大家有兴趣深入了解 MySQL 的页结构，强烈建议大家看看文末的<