B+树是B树的变体，常用于数据库和操作系统的文件系统中。MySQL数据库的索引就是基于B+树实现的。
常见面试题：MySQL数据库的索引实现原理？为什么MySQL数据库的索引是基于B+树实现而不是B树？
本章节不写B+树的代码实现，主要分析MySQL数据库的索引为什么使用B+树实现。
一、B+树
B+树的特点：
- 分为内部节点（就是非叶子节点）和叶子节点2种节点
- 内部节点只存储key，不存储具体数据
- 叶子节点存储key和具体数据
- 所有的叶子节点形成一条有序链表
m阶B+树非根节点的元素数量x满足：ceilf(m/2) ≤ x ≤ m。
简单了解B+树的概念后，我们看下数据库和硬盘的概念，知道硬盘的存储原理后基本就能够知道为何MySQL数据库是基于B+树实现。
二、数据库和硬盘
2.1. 数据库
MySQL的发音：https://dev.mysql.com/doc/refman/8.0/en/what-is-mysql.html
The official way to pronounce “MySQL” is “My Ess Que Ell” (not “my sequel”).
but we do not mind if you pronounce it as “my sequel” or in some other localized way.
大概意思：“MySQL”的发音是“My Ess Que Ell”（除了My是正常发音，后面的三个字母都按照26字母的发音标准即可），不是“my sequel”发音（连续发音），但是我们也不会介意你这样发音或者是一些地方口音。
数据库其实就是一堆文件组成的库（例如，一堆书可以组成图书库（图书馆），那么一堆数据组成的就叫数据库）。
数据库的数据都是存储在硬盘上面的（例如，一堆书都是存放在书架上面的），对数据库文件的读写操作也叫作IO操作（Input Output）。所以访问数据库的性能取决于IO效率，为了优化访问数据库的效率，我们需要优化IO操作效率。
数据库索引主要是为了查询数据更快。
在了解如何优化之前，我们先看下硬盘的存储原理。
2.2. 硬盘的分类
市面上常见的硬盘：机械硬盘（Hard Disk Drive，简称：HDD）、固态硬盘（Solid State Drive，简称：SSD）。
我们主要介绍一下机械硬盘相关概念：
2.3. 硬盘的组成
2.3.1. 盘片(platter)、盘面(side)、读写磁头(head)
- 硬盘一般由多个盘片组成
- 每个盘片包含2个盘面
- 每个盘面有1个对应的读写磁头（每个盘面都可读写数据）
- 盘面和磁头由上到下从0开始编号（盘片的两个面都有编号）
2.3.2. 磁道(track)、扇区(sector)
如上图，是一个盘面，盘面中的一圈圈灰色圆环是一条条的磁道，磁道由外到内从0开始编号。
每条磁道上的一个弧段叫做一个扇区，扇区是磁盘的最小读写单位，一个扇区的大小通常是512字节（也有4096字节的）。
早期硬盘的扇区细节：
- 每条磁道的扇区数相同，所以外圈扇区的面积会比内圈扇区大
- 为了更好的读取数据，它们会存放相同的字节数，所以外圈扇区的记录密度要比内圈小，会浪费大量的存储空间
- 硬盘的存储容量 = 磁头数（盘面数） * 盘面磁道数 * 磁道扇区数 * 扇区字节数
2.3.3. 柱面(cylinder)
相同编号的磁道形成一个圆柱，称为柱面。磁盘的柱面数与一个盘面的磁道数是相等的。
2.3.4. 磁盘块
磁盘块，在Windows中叫做簇（cluster），在Linux中叫做块（block）。
相邻的$2^n$个扇区组合在一起，形成一个磁盘块，操作系统对磁盘进行管理时，以磁盘块作为最小读写单位，一般一个磁盘块是4096字节（4KB，由8个连续的512字节扇区组成）。
有些操作系统即使新建一个空文件夹也需要占用4KB空间。
注意：磁盘块是操作系统中的一个虚拟概念，扇区是磁盘上真实存在的物理区域。
2.4. 查看硬盘信息
Windows：如果是查看D盘，管理员权限打开命令行工具，输入fsutil fsinfo ntfsinfo d:。也可以直接到【系统信息】查看。
Mac：使用【磁盘工具】。
2.5. 操作系统读取硬盘数据的过程
- 操作系统将LBA（Logical Block Address，逻辑块地址）传送给磁盘驱动器并启动读取命令；
- 比如类似设备号4、磁头号4、磁道号8、扇区号16、扇区计数8这样的信息
- 磁盘驱动器根据LBA将磁头移动到正确的磁道，盘片开始旋转，将目标扇区旋转到磁头下；
- 磁盘控制器将扇区数据等信息传送到一个处于磁盘界面的缓冲区；
- 磁盘驱动器向操作系统发出“数据就绪”信号；
- 操作系统从磁盘界面的缓冲区读取数据；
- 既可以按照一个字节一个字节的方式读取
- 也可以启动DMA（Direct Memory Access，直接内存访问）命令读取
2.6. 磁盘完成IO操作的时间
主要由寻道时间、旋转延迟时间、数据传输时间3部分构成。
寻道时间（seek）：将读写磁头移动至正确的磁道上所需要的时间，这部分时间代价最高。
旋转延迟时间（rotation）：盘片旋转将目标扇区移动到读写磁头下方所需要的时间，取决于磁盘转速。
数据传输时间（transfer）：完成传输数据所需要的时间，取决于接口（计算机内部硬件之间通讯就是通过接口传输的）的数据传输率，通常远小于前两部分消耗时间。
决定时间长短的大部分因素是和硬件相关的，但所需移动的磁道数是可以通过操作系统来进行控制的。也就是说寻道时间可以通过代码优化，旋转延迟时间和数据传输时间完全依赖硬件，所以减少所需移动的磁道数是减少整个硬盘读写时间的有效办法，合理安排磁头的移动以减少寻道时间就是磁盘调度算法的目的所在。
三、MySQL的索引
MySQL的索引底层为何使用B+树？
为了减小IO操作数量，一般把一个节点的大小设计成最小读写单位的大小，MySQL的存储引擎InnoDB的最小读写单位是16K（也就是说一个节点可以存储很多的key）。
如下图，如果使用B树，一个节点就是一个磁盘块，而B树的节点存储的是key-value。一般情况下，key是比较小的（可以理解为数据表中的id），value是比较大的（可以理解为数据表中id对应的一整条数据），所以一个节点只能存储少量的信息，操作系统只能耗时（效率低）把数据读取出来。
对比B树，B+树的优势是：
- 每个节点存储的key数量更多，树的高度更低；
- 同样大小的节点，B树每个节点存储的数据包含value，所以能够容纳的key就少，树的高度也就更高
- 所有的具体数据都存在叶子节点上，所以每次查询都要查到叶子节点，查询速度比较稳定；
- 虽然B树数据是在节点上直接存储，但有可能要找的数据在树的最底层，所以查询速度不稳定
- 由于所有的叶子节点构成了一个有序链表，所以做区间查询时也更方便。
- B树做区间查询就只能用中序遍历（只有中序遍历才是有顺序的），比较麻烦
综上比较B+树的优势，可以得出结论：MySQL的索引底层使用B+树效率更高（主要是树的高度更低）。
四、扩展：B*树
B*树是B+树的变体：给内部节点增加了指向兄弟节点的指针。
m阶B*树非根节点的元素数量x满足：ceilf(2m/3) ≤ x ≤ m。
B*树相比B+树节点，可容纳元素数量更多，为什么数据库索引不使用B*树呢？
B*树分配新结点的概率比B+树要低，空间利用率高，但为此，有几个性能问题，比如深度、分裂的时候性能会很差等等。同时因为数据是动态的，索引会增加，某个节点现在没满以后也会满的，如果贪图暂时的空间利用率，而减缓索引速度是不值得的。
