往期推荐
看过很多关于B+Tree的文章，也看过很多教学视频，直白的说我还是不能够真正的理解B+Tree这个数据结构真正的原理，以及它的查询路径的优化，如何能够实现减少IO读写次数？我暗自发誓一定要弄明白它，然后能使用通俗易懂的方式科普给周围的小伙伴。
在这篇文章中我打算结合两部分来讲这个知识点：
第一点通过结合操作系统从磁盘读取数据到内存
第二点通过结合我们常用到的MySQL索引结构
对数据结构感兴趣的朋友，这里推荐一个可视化网站，里面包含各种数据结构：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
先看看B/B+Tree在我们工作中哪些应用与此有关，这里罗列一下他的用途：
B/B+Tree通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中，如：
Windows：HPFS文件系统
Mac：HFS，HFS+文件系统
Linux：ResiserFS，XFS，Ext3FS，JFS文件系统
数据库：ORACLE，MySQL，SQLServer等中
是不是离我们这么近，但又那么远？
在我们的计算机系统中，所有信息如果要持久化，那就必须落盘，只有把数据保存到磁盘中的文件里面，才能让数据真正的持久化。那么数据库的索引文件它也不例外，索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作，而磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。
请搬好小板凳，我们需要从头讲起，挺费事的！先看看磁盘结构与存取原理吧！
磁盘存取原理
一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）
盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。
当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
最小存储单元
扇区：磁盘的最小存储单位。扇区是块设备传输数据的基本单元，也就是说它是块设备中最小的寻址单位，扇区通常的大小为512B。
块：文件系统读写数据的最小单位。块是内核对文件系统的一种抽象，也就是说内核执行的所有磁盘操作都是以块为基本单位的。
页：内存的最小存储单位。
可以简单的将扇区和块理解为：扇区是硬件设备传输数据的最小单位，而块是操作系统传输数据的最小单位。一个块通常对应一个或多个相邻的扇区。一页的大小为磁盘块大小的2的n（n为正整数）次方倍。
总结：在计算机中，磁盘存储数据最小单元是扇区，一个扇区大小为512字节，而文件系统的最小存储单元是块，一个块的大小是4k（即如果一个文件即使只有1k，在磁盘上占的空间也是4k）。
说了这么多，我就是想表明InnoDB引擎的最小存储单元是页，一页默认值为16KB（MySQL5.5以前，一页固定为16k，MySQL5.5以后，页大小为4KB, 8KB, 或者16KB，MySQL5.7.6还支持32KB和64KB，但是默认情况下都是16KB。
参见官网https://dev.mysql.com/doc/refman/5.7/en/glossary.html#glos_page_size ）
请务必记住几个关键数字：扇区大小512B，块大小4K，页大小16K
这个概念对后面计算InnoDB引擎中一棵B+Tree可以存放多少行数据很重要。
可知磁盘的读写IO操作是性能提升的关键步骤，只有降低磁盘的读写次数才能本质上的提升数据的读取时间。聪明的人类，为了解决此类问题，发明了多种数据结构，从二叉查找树->平衡二叉树->B-Tree(平衡多路查找树)
->B+Tree(平衡多路查找树plus)，最终形成我们常见的B+Tree。
二叉查找树，由于缺点太多（出现“瘸子”现象，查询效率低下），我们这里不深入研究。
而平衡二叉树，虽然解决了二叉树出现“瘸子”现象，但是他要求左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的这个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树，如果频率太高了，大大降低了性能。
好了，我们重点分析一下B树系列的这两个数据结构，上面有提到InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。
B-Tree
概念都是比较枯燥乏味的，我们还是结合图片，这样更形象生动，易于理解，我们准备一个3阶的B-Tree图，数据包含：2，5，7，8，11，14，15，16，17，27，29，32，35，38，39，42，60，63，65，72，75，80
使用B-Tree数据结构网站生成一个，如下：
通过processOn 画图软件美化后如下：
每个节点占用一个盘块的磁盘空间，因为是3阶B-Tree，所以一个节点上有一到两个升序排序的关键字和三个指向子树根节点的指针(P1,P2,P3)，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为大于17。
根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
比较关键字32大于17，找到磁盘块1的指针P2。
根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
比较关键字32小于35，找到磁盘块3的指针P1。
根据P1指针找到磁盘块6，读入内存。【磁盘I/O操作第3次】
比较关键字32大于29，找到磁盘块6的指针P2。
根据P2指针找到磁盘块14，读入内存。【磁盘I/O操作第4次】
最后在关键字列表中找到关键字32。
由上图我们可以看到B-Tree的每个节点中都包含Key对应的Data数据，而之前提到过每个磁盘块的大小是固定的，MySQL中页的大小默认配置只有16K，假如每一个节点Key对应的Data数据都很大的时候，可以想象16K很快就满了，进而导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率，显示这种也不是很优雅。
B+Tree
概念：
B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储Key值信息，这样显然就可以加大每个节点存储的Key值数量，降低B+Tree的高度。
特性：
非叶子节点只存储键值信息。
所有叶子节点之间都有一个链指针。
数据记录都存放在叶子节点中。
数据结构网站生成的4阶B+Tree，如下图：
下面我们结合数据表来进一步说明，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储3个键值及指针信息，则变成B+Tree后其结构如下图所示：
由上图可以发现，通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。
我们常说数据库表设计规范，表中主键字段尽可能的使用INT（占用4个字节）或BIGINT（占用8个字节），是有一定道理的，加上指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为【10】^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。
上面的几个例子其实都是讲的MySQL的聚集索引，除了这个我们常用的还有辅助索引，也就是我们常说的非聚集索引，它两的区别在于聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据，而辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。
这里穿插一下面试知识点：
我每次在面试的时候，我都会问对方一个问题，什么叫"回表查询"? 很多面试者都可能没有听过这个词语或者说不清楚，这说明他对MySQL的索引数据结构一点儿都不了解。当我们查询条件是通过主键查询的时候，因为主键是聚集索引，这时直接就在索引的叶子节点就可以拿到数据;而当我们的查询条件是通过普通的索引过滤数据时，这里得分两种情况：
1、如果select xx from table 中 xx 的字段刚好是索引字段的话，那么直接就可以在索引中找到对应的值，不需要"回表查询"，直接返回结果。
2、如果xx中的字段包含除索引外的字段，那么这时就需要通过找到该记录的叶子节点中的主键信息，拿到主键信息后，再去聚集索引中找到主键对应的整条数据行，这就叫做"回表查询"了。
很想再画一个图，把上面图中非叶子节点的key换成name字段的值，然后把叶子节点的data换成主键值，再结合上图。就形成了 聚集索引，辅助索引共用使用的场景。（画图太费时间了，不好意思哈^V^）
话说回来，实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作，数据量很大的情况下，也能控制在1~3次I/O操作，这就真正的其它数据结构的问题。
还有一些内容：比如如何实现范围查找？B+Tree如何实现自动平衡？今天这里就不深入说了，内容太多也不太好消化。能看这些的朋友已经不错了，谢谢大家。
公众号：架构工匠（ID: gh_e3ddf5fb9980）
CSDN博客：架构工匠
长按二维码关注
愿一个热爱技术的灵魂，给你带来更多共鸣与激情碰撞。
感谢您的阅读！常来哦
