B+树是 B 树的变体，常用于数据库和操作系统的文件系统中，MySQL 数据库的索引就是基于 B+树的实现的，其大致结构如下：

• B+ Tree 的特点

  • 分为内部节点（非叶子）、叶子结点 2 种节点

    • 内部节点只存储 key，不存储具体数据
    • 叶子节点存储 key 和具体的数据。
  • 所有的叶子节点形成一条有序链表
  • m 阶 B+Tree 树非根节点的元素数量 x :⌈m /2⌉ ≤ x < m

为什么要设计成这样呢？

硬盘的分类

市面上常见的硬盘有：机械硬盘（Hard Disk Drive， HDD），固态硬盘（Solid State Drive，SSD）

在这里，我们主要介绍机械硬盘

盘片（platter）、盘面（side）、读写磁头（head）

机器硬盘的剖面图大概就长这个样子。

• 硬盘一般由多个盘片组成
• 每个盘片包含包含两个盘面，两面都可以放数据
• 每个盘面有 1 个对应的读写磁头
• 盘面、磁头由上到下从 0 开始编号

磁道（track）、扇区（sector）

• 盘面中一圈圈灰色圆环为一条条的磁道
• 磁道由外到内从 0 开始编码
• 每个磁道上的一个弧段叫做一个扇区
• 扇区就是磁盘的最小读写单位
• 一个扇区的大小通常是 512 字节，也有 4096 字节的

早期磁盘的扇区细节

• 每条磁道的扇区数是相同，所以外圈扇区的面积会比内圈扇区大
• 为了更好的读取数据，它们会存放相同的字节数，所以外圈扇区的记录密度要比去内圈小，会浪费大量的空间。
• 硬盘的存储容量 = 磁头书 盘面磁道数 磁道扇区数 * 扇区字节数

柱面（cylinder）

想通编号的磁道形成了一个圆柱，成为柱面，磁盘的柱面数与一个盘里面的磁道数是相等得分。

磁盘块

• 磁盘块，在 Windows 叫做簇（cluster），在 linux 中叫做块（block）
• 相邻的 2^n 个扇区组合在一起，形成一个磁盘块
• 操作系统对磁盘进行管理时，以磁盘块作为最小读写单位，一般来说一个磁盘块是 4096 字节（4kb，由 8 个连续的 512 字节扇区组成）

注意：

• 磁盘块是操作系统中的一个虚拟概念
• 扇区是磁盘上真实存在的物理区域

操作系统读取硬盘数据的过程

1. 操作系统将 LBA（Logical Block Address，逻辑块地址） 传送给磁盘驱动器并启动那个读取命令，比如类似设备号 4、磁头号4、磁道号 8、扇区号 6、扇区计数 8 这样的信息。
2. 磁盘驱动器会根据 LBA 将磁头移动到正确的磁道，盘片开始旋转，将目标扇区旋转到磁盘下
3. 磁盘控制器将扇区数据等信息传送到一个处于磁盘界面的缓冲区
4. 磁盘驱动器向操作系统发出“数据就绪”信号

5. 操作系统从磁盘界面的缓冲区读取数据

   1. 既可以按照一个字节一个字节的方式读取
   2. 也可以启动 DMA（Direct Memory Access，直接内存读取）命令获取

磁盘完成 IO 操作的时间

• 主要由寻道时间、旋转延迟时间、数据传输时间 3 个部分构成

  • 寻道时间 （seek）：将读写磁头移动至正确的磁道上所需的时间，这部分时间代价最高
  • 旋转延迟时间（rotation）：磁盘旋转将目标扇区移动到读写磁头下方所需的时间，取决于磁盘转速
  • 数据传输时间（transfer）：完成数据传输所需要的时间，取决于接口的数据传输率，通常远小于前两部分消耗时间的

• 决定时间长短的大部分因素是和硬件相关的，但所需移动的磁道数是可以通过操作系统来进行控制的。

  • 减少所需移动的磁道数是减少整个磁盘读写时间的有效办法
  • 合理安排磁头的移动以减少寻道时间就是磁盘调度算法的目的所在

MySQL 的索引底层为何使用 B+Tree

• 为了减小 IO 操作数量，一般把一个节点的大小设计成最小读写单位的大小
• MySQL 的存储引擎 InnoDB 的最小读取单位是 16K

• 对比 B Tree 和 B+ Tree 的优势：

  • 每个几点存储 key 数量更多，树的高度更低
  • 所有的具体数据都存在叶子节点上，所以每次查询都要查到叶子节点，查询速度比较稳定
  • 所有的叶子节点构成一个有序链表，做区间查询更方便