MySQL索引（二）B+树在磁盘中的存储

た入场券 2022-01-20 04:43 410阅读 0赞

## 回顾 ##

上一篇文章[《MySQL索引为什么要用B+树》][MySQL_B]讲了MySQL为什么选择用B+树来作为底层存储结构，提了两个知识点：

1.  B+树索引并不能直接找到行，只是找到行所在的页，通过把整页读入内存，再在内存中查找。
2.  索引的B+树高度一般为2-4层，查找记录时最多只需要2-4次IO。

为进一步知其所以然，今天来聊聊B+树索引在物理磁盘上是怎么设计存储的。

## 一、理解为什么要减少磁盘IO次数 ##

众所周知，MySQL的数据实际是存储在文件中，而磁盘IO的查找速度是要远小于内存速度的，所以减少磁盘IO的次数能很大程度的提高MySQL性能。

### 1.1 磁盘IO为什么慢 ###

先温习下知识点：**磁盘IO时间 = 寻道 + 磁盘旋转 + 数据传输时间**

从磁盘读取数据时，系统会将逻辑地址发给磁盘，磁盘将逻辑地址转换为物理地址（哪个磁道，哪个扇区）。 磁头进行机械运动，先找到相应磁道，再找该磁道的对应扇区，扇区是磁盘的最小存储单元（见`图1-1`）。

图1-1 磁盘物理结构

### 1.2 性能对比 ###

机械硬盘的连续读写性能很好，但随机读写性能很差。

*  顺序访问：内存访问速度是硬盘访问速度的6~7倍（`kafka`的特点，以后有机会的话再讲一讲）
 *  随机访问：内存访问速度就要比硬盘访问速度快上**10万倍以上**

随机读写时，磁头需要不停的移动，时间都浪费在了磁头寻址上。 而在实际的磁盘存储里，是很少顺序存储的，因为这样的维护成本会很高。

## 二、索引在磁盘上的存储 ##

知道磁盘IO的性能了吧，接下来看看MySQL是如何根据这种情况来设计索引的物理存储，以下内容以`InnoDB`引擎为例，`MyISAM`略有不同，后面再讲。

假设我们有一张这样的表，表中有如`图2-0`的数据

CREATE TABLE `user` (
      `ID` bigint(11) NOT NULL AUTO_INCREMENT,
      `NAME` varchar(20),
      PRIMARY KEY (`ID`),
      KEY `idx_name` (`NAME`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
    复制代码

图2-0 表数据

### 2.1 聚集索引（Clustered index ） ###

每个InnoDB表都有一个称为聚集索引的特殊索引，该索引是按照表的主键构造的一棵B+树。

根据示例数据构建如图2-1所示聚集索引：

图2-1 B+树聚集索引

#### 2.1.1 知识点 ####

*  叶子节点存放了整张表的所有行数据。
 *  非叶子节点并不存储行数据，是为了能存储更多索引键，从而降低B+树的高度，进而减少IO次数。
 *  聚集索引的存储在物理上并不是连续的，每个数据页在不同的磁盘块，通过一个双向链表来进行连接。

#### 2.1.2 查找：假设要查找数据项6 ####

1.  把根节点由磁盘块0加载到内存，发生一次IO，在内存中用二分查找确定6在3和9之间；
2.  通过指针P2的磁盘地址，将磁盘2加载到内存，发生第二次IO，再在内存中进行二分查找找到6，结束。

这里只进行了两次IO，实际上，每个磁盘块大小为4K，3层的B+树可以表示上百万的数据，也就是每次查找只需要3次IO，所以索引对性能的提高将是巨大的。

#### 2.1.3 怎样选择聚集索引 ####

每张InnoDB表有且只有一个聚集索引，那它是怎么选择索引的呢？

*  一般情况，用`PRIMARY KEY`来作为聚集索引。
 *  如果没有定义`PRIMARY KEY`，将会用第一个`UNIQUE`且`NOT NULL`的列来作为聚集索引。
 *  如果表没有合适的`UNIQUE`索引，会内部根据行ID值生成一个隐藏的聚簇索引`GEN_CLUST_INDEX`。

所以在建表的时候，如果没有逻辑唯一且非空列时，可以添加一个auto\_increment的列，方便建立一个聚集索引。

### 2.2 非聚集索引（Secondary indexes） ###

非聚集索引又叫辅助索引，叶子节点并不包含行记录数据，而是存储了聚集索引键。

根据示例数据（`idx_name`索引）构建如图2-2所示辅助索引：

图2-2 B+树非聚集索引

#### 2.2.1 知识点 ####

*  每个表可以有多个辅助索引
 *  通过辅助索引查数据时，先查找辅助索引获得聚集索引的主键，然后通过主键索引来查找完整的行记录。
 *  通过非主键索引比主键索引查找速度要慢一倍。

#### 2.2.2 查找：获取`NAME=Jake`的数据 ####

第一阶段：通过辅助索引查到主键索引的主键

1.  把idx\_name索引的根节点由磁盘块0加载到内存，发生一次IO，查找到在P2指针中
2.  根据P2指针的磁盘地址，加载磁盘块2到内存，发生第二次IO，查找到Jake节点以及它的主键索引9

第二阶段：通过主键索引找到完整的行记录

1.  把根节点由磁盘块0加载到内存，发生一次IO，在内存中用二分查找确定9在P3指针中
2.  通过指针P3的磁盘地址，将磁盘3加载到内存，发生第二次IO，再在内存中进行二分查找找到9，以及它的行记录，