封面画师：Nengoro(ネんごろぅ) 封面ID：73531546

本文参考视频：小马哥教育(SEEMYGO) 2019年恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化 Data Structure Visualizations

PS：本文只做了解，不进行编码实现！

1. B+ 树

1.1 基本概念

B+ 树是 B 树的变体，常用于数据库和操作系统的文件系统中。

MySQL 数据库的索引就是基于 B+ 树实现的。

B+树结构

B+ 树的特点

B+ 树上的节点分为内部节点（非叶子）和叶子节点。

内部节点只存储 key，不存储具体数据。
叶子节点存储 key 和具体的数据。

所有的叶子节点形成一条有序的链表。

$m$ 阶 B+ 树非根节点的元素数量 $x$ 的取值范围是：

$\lceil \frac{m}{2} \rceil \le x \le m$

MySQL 的发音

官方文档：MySQL :: MySQL 8.0 Reference Manual :: 1.2.1 What is MySQL?

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 sequel，但是官方并不介意将其读成 my sequel，甚至读成其他本土化的方式。

开源，懂不懂开源啊，发音都是开源的。😆

1.2 MySQL 的索引与 B+ 树

MySQL 的索引底层为什么要使用 B+ 树？

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

2、对比 B 树，B+ 树的优势是：

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

B 树的结构

B树的结构

B* 树

B* 树是 B+ 树的变体：在 B+ 树的基础上给内部节点增加了指向兄弟节点的指针。

$m$ 阶 B* 树非根节点的元素数量 $x$ 的取值范围是：

$\lceil \frac{2m}{3} \rceil \le x \le m$

B+树的变体

2. 硬盘

2.1 盘片盘面磁头

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

对于机械硬盘来说，它一般由多个盘片（platter）组成，每个盘片（side）包含 2 个盘面，每个盘面有 1 个对应的读写磁头（head）。盘面、磁头由上到下从 0 开始编号。

机械硬盘结构

2.2 磁道与扇区

盘面中的一圈圈灰色圆环是一条条磁道，磁道由外到内从 0 开始编号。

每条磁道上的一个弧段叫做一个扇区。

扇区是磁盘的最小读写单位。一个扇区的大小通常是 512 字节，也有 4096 字节的。

磁道与扇区

早期磁盘的扇区细节

每条磁道的扇区数相同，所以外圈扇区的面积会比内圈扇区大。

为了更好地读取数据，它们会存放相同的字节数，所以外圈扇区的记录密度比内圈小，会浪费大量的存储空间。

硬盘的存储容量计算有如下公式：

$硬盘的存储容量 = 磁头数 \times 盘面磁道数 \times 磁道扇区数 \times 扇区字节数$

2.3 柱面

相同编号的磁道形成一个圆柱，称为柱面（cylinder）。磁盘的柱面数与一个盘面的磁道数是相等的。

柱面-cylinder

2.4 磁盘块

磁盘块，在 Windows 中叫做簇（cluster），在 Linux 中叫做块（ block ）。

相邻的 $2^n$ 个扇区组合在一起，形成一个磁盘块。

操作系统对磁盘进行管理时，以磁盘块作为最小读写单位。

一般一个磁盘块是 4096 字节，即 4 KB，由 8 个连续的 512 字节扇区组成。

注意

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

2.5 查看硬盘信息

在 Windows 上，以查看 D 盘信息为例：

以管理员权限打开命令行工具，执行 fsutil fsinfo ntfsinfo d:
或者在搜索框中输入 系统信息

在 Mac 上，使用【磁盘工具】进行查看。

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

操作系统将 LBA （Logical Block Address，逻辑块地址）传送给磁盘驱动器并启动读取命令，比如类似设备号 4、磁头号 4、磁道号 8、扇区号 16、扇区计数 8 这样的信息；
磁盘驱动器根据 LBA 将磁头移动到正确的磁道，盘片开始旋转，将目标扇区旋转到磁头下；
磁盘控制器将扇区数据等信息传送到一个处于磁盘界面的缓冲区；
磁盘驱动器向操作系统发出“数据就绪”信号；
操作系统从磁盘界面的缓冲区读取数据，既可以一个字节一个字节地进行读取，也可以启动 DMA（Direct Memory Access，直接内存访问）命令读取。