【进阶】索引底层数据结构和算法

墨蓝 2022-03-10 14:30 222阅读 0赞

# 前言 #

文章基于 MySql 5.7.24 分析，部分图片源于网络，是 MySQL 索引学习笔记。

MySQL 数据库支持多种索引类型，如 BTree 索引，哈希索引，全文索引等等。

这里只关注 BTree 索引，这是平时实战中使用最多的索引。

# 一 MySQL 索引概要 #

MySQL 索引是帮助 MySQL 高效获取数据的排好序的数据结构。索引存储在文件里面。

索引就好比书的目录，你可以通过目录直接找到对应的目标，而不需要从第一页翻起

逐页查找，运气不好，就得从头翻到尾。

简单来说，索引是一种存储在文件里面排好序的数据结构。

MyISAM 存储引擎表 test01，在MySQL 的 data 里面有三个文件：

test01.frm：存储表结构；

test01.MYD：存储数据；

test01.MYI：存储索引；

InnoDB 存储引擎表 test02，在 MySQL 的 data 里面有二个文件：

test02.frm：存储表结构；

test02.ibd：存储数据和索引；

# 二 索引基础数据结构和算法 #

为什么使用 B+Tree 作为索引的数据结构，为什么不用二叉树、红黑树、B-Tree 等等？

索引提高获取数据效率的本质是什么？

## 1、磁盘的读写原理 ##

### 1.1 磁盘立体示意图 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70][]

一个磁盘由大小相同且同轴的圆形盘片组成，这个旋转轴称为盘片主轴。而所有盘片之间是绝对

平行的，在每个盘片的存储面上都有一个磁头，磁头与盘片之间的距离非常小。所有的磁头连在

一个磁头控制器上，由磁头控制器负责各个磁头的运动。磁头可沿盘片的半径方向动作（实际是斜

切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠

的（不过目前已经有多磁头独立技术，可不受此限制）。而盘片以每分钟数千转到上万转的速度在

高速旋转，这样磁头就能对盘片上的指定位置进行数据的读写操作。

### 1.2 俯视示意图 ###

磁盘示意图和磁盘俯视图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 1][]    ![20190312121512388.png][]

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组

成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小

存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑

地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要

将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所

耗费时间叫做寻道时间（速度慢，费时），然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费

的时间叫做旋转时间（速度较快）。

MySQL 数据存储在磁盘上，一般来说需要经过寻道和旋转，将磁头对应这个数据扇区上方，

才能从磁盘上读取这条数据。如果我们能够通过某种方式明确的告诉计算机去磁盘的哪里存取数

据，而不是每次都让计算机去磁盘上“瞎忙”，地毯式搜索数据，存取数据的效率将会高很多。

而索引，正是 MySQL 用来解决减少磁盘 I/O 操作次数，提高存取效率的手段。所以，

提高 MySQL 查询效率的本质就是想办法减少磁盘 I/O 操作次数，尽快从磁盘上获取数据。

## 1.3 看一个例子，假设用一个树状结构优化查找效率 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 2][]

假设表上有 7 行两列数据，最左侧为物理地址，如果查找 Col2 的某一行数据，需要逐个遍历获取

对应数据。比如，查找 23 这行数据，需要从第一行开始查找，逐行查找，直到找到位置，总的要

查找 7 次。（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的，有可能查找更多次数，效

率更低）。为了加快 Col2 查找，可维护最右侧的树型结构，每个节点分别包含索引键值和一个指

向对应数据记录物理地址的指针。比如，查找 23 这行数据，3 次就能找到 23 这个索引键值，通

过对应的物理地址指针，直接就能获取 23 这行数据，获取数据效率更高。

这就是索引的目标，减少磁盘 I/O 操作次数，提高 MySQL 查询数据的效率。

下面讨论 MySQL 为什么选择我们最常打交道的 B+Tree 实现 BTree 索引。

## 2、二叉树 ##

MySQL 为什么不选择二叉树作为索引数据结构？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 2][]

如果使用二叉树作为索引数据结构，以 Col1 建立索引，极端情况下这里 Col1 从 1 到 7 是顺序

的，建立出来数据结构是这样的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 3][]

在极端情况下，如果某个列数据顺序增长，建立出来的索引结构也是顺序存储的，

跟从表里面顺序查找的效率是一样的，会失去索引存在的意义，这就是不用二叉树作为索引

数据结构的原因。极端情况下查找时间复杂度从 O(logn) 退化到 O(n)。

## 3、红黑树 ##

MySQL 为什么不选择红黑树作为索引数据结构？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 2][]

如果使用红黑树作为索引数据结构，以 Col1 建立索引，这里 Col1 从 1 到 7 是顺序的，建立出来

数据结构是这样的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 4][]

从红黑树结构可以看到，整棵树是失衡的，如果查找 7 的时候，会经历四次查找，

同时，每一个节点只能有两个子节点，如果数据量特别大的时候，树的深度非常大，

整棵树查找效率非常低，也不是 MySQL 引数据结构的最佳选择。

## 4、Hash ##

MySQL 用 Hash 作为索引数据结构的优缺点，为什么 Hash 用得哪么少？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 2][]

如果我们给 Col1 每行数据都算一个 Hash 值，查找的时候直接通过 Hash 值查找到对应的数据，

这样非常的快，磁盘能直接就定位到数据。但是用 Hash 有个弊端，如果要进行范围查找，

Hash 处理不了范围查找，而实际 SQL 中，范围查找也是非常常见的。索引 Hash 在个别值查找

时效率是不错的，比如身份证字段建一个 Hash 索引，范围查找用得比较少的，效率会比较不错，

千万不要在使用范围查找的列建立 Hash 索引。所以，在实际中使用 Hash 索引比较少。

## 5、B-Tree 树 ##

综合上面的数据结构，MySQL 自然会想到要用一种平衡的结构去解决索引存储问题。

自然会想到 B-Tree(不要读成B减Tree，要不然就跟回老家把亲戚辈分叫错了一样尴尬，它是 B

树，balance)。在分析B-Tree之前，还需要了解**局部性原理与磁盘预读**：

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往

是主存的几百分之一，因此为了提高效率，要尽量减少磁盘 I/O。为了达到这个目的，磁盘往往不

是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后

读取一定长度的数据放入内存。

这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集

中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部

性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往

将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得

大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一

个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或

几页载入内存中，然后异常返回，程序继续运行。

假设数据库有两列数据，如下：

![20190313130507316.png][]

如果设定 B-Tree 的 Degree 为 4，将 Col1 存储到 B-Tree，结构如下：

![20190313081157864.png][]

是不是感觉很清爽，如果要查找 7，最多两次就搞定，效率很高。

**B-Tree 特性：**

如下图，是从网上找的一个 B-Tree 简要结构，并不是磁盘存储的真正结构，是抽象出来的，

用它来说明 B-Tree 的特性比较直观。

![20190313081401875.png][]

*  度(Degree)-节点的数据存储个数;
 *  叶节点具有相同的深度;
 *  叶节点的指针为空;
 *  节点中的数据 key 从左到右递增排列;

15，56，77 等等为索引大节点中的小节点，每一个小节点均为 key-value 结构，key 存储键值，value 存储对应的行数据。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 5][]

当我们查询数据时，cpu 从磁盘把部分索引文件内容加载到内存，在内存查找到目标值，然后有目

标的去磁盘拿我们的目标数据，减少磁盘 I/O 操作次数。然而使用 B-Tree 建立索引文件后，每一

个节点上都有数据 data，而每次从磁盘加载到内存的数据是有限制的，一般为一页或几页（一般

一页的大小为 4k），如果一个节点数据很大的时候，我们需要很多次磁盘 I/O 操作才能把一个节

点载入到内存，效率很低，就失去了索引的意义。所以，这就是MySQL 不使用 B-Tree 作为索引

数据结构。【注意 CPU 只跟内存打交道，切确的说是只跟寄存器打交道，CPU 直接操作不磁盘】

## 6、B+Tree 树 ##

经过以上分析，终于见到MySql索引数据结构B+Tree，B+Tree是B-Tree的一个变种。B+Tree特

性：

*  非叶子节点不存储 data，只存储 key，可以增大度;
 *  叶子节点存储文件指针或数据，但是 MySQL 不同引擎存储的内容不一样;
 *  顺序访问指针，提高区间访问的性能;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 6][]

为什么要使用 B+Tree 作为索引的数据结构？

一般使用磁盘 I/O 次数评价索引结构的优劣。

B+Tree 在非叶子节点上不存储数据，只存索引的键值，这样能保证每一个节点上数据非常小，

MySQL 根据 B+Tree 的特性和局部性原理，将 B+Tree 节点的大小设为等于一个页，每次新建节

点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载

入只需一次I/O，大大减少磁盘 I/O 次数，提高获取数据的效率。同时 B+Tree 的度 d 一般会超过

100，因此h非常小(一般为3到5之间)，只需要几次I/O操作就能把索引检索完，效率非常高。

# 三 MyISAM 引擎索引实现（非聚簇） #

MyISAM 存储引擎上的索引是**非聚簇索引**，因为索引文件和数据文件是分离存储的。

MyISAM 存储引擎和 InnoDB 存储引擎在叶子节点上存储的数据不一样。

MyISAM 存储引擎表 test01，在 MySQL 的 data 里面有三个文件：

test01.frm：存储表结构；

test01.MYD：存储数据；

test01.MYI：存储索引；

## 1、MyISAM 主键索引 ##

MyISAM 主键索引的数据结构如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 7][]

比如以主键 Col1 建立索引，在叶子节点上存储的是文件指针，如果我们要查找 30 这行数据，

则先在索引文件（MYI）根据 B+Tree 查找到 30 这条数据的文件指针，然后通过文件指针

直接从磁盘数据文件（MYD）中查找到对应的数据。如果是范围查找，因为索引已经排好序了，

直接从磁盘读取对应范围的数据。

## 2、MyISAM 非主键索引 ##

MyISAM 存储引擎的非主键索引存储结构与其主键索引的存储结构相同，查找方式一样。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 8][]

# 四 InnoDB引擎索引实现 #

InnoDB 存储引擎表 test02，在 MySQL 的 data 里面有二个文件：

test02.frm：存储表结构；

test02.ibd：存储数据和索引；

数据文件本身就是索引文件，表数据文件本身就是按 B+Tree 组织的一个索引结构文件。

## 1、InnoDB 聚簇索引 ##

InnoDB 引擎聚簇索引在叶子节点存储的不是文件指针，与 MyISAM 存储引擎在叶子节点存储文件

指针不同，因为索引文件和数据文件是合在一起的，所以，在叶子节点存储的是对应索引键值的数

据。我们只要通过索引遍历就能查找到数据，相比 MyISAM引 擎，能够减少一次通过文件指针

从数据文件（ibd）获取数据的一次磁盘 I/O。

![20190313224139434.png][]

**为什么 InnoDB 表必须有主键，并且推荐使用整型的自增主键？**

MySQL InnoDB 引擎默认会基于主键建立 B+Tree 数据结构，如果没有主键，

它会选择唯一数据列（比如唯一索引列）建立 B+Tree 数据结构。

如果主键和唯一键都没有，它就随便给你搞一列建立 B+Tree 数据结构。

所以，MySQL 推荐使用整型的自增主键，因为整型比较大小查找比字符串快，

整型一比较就知道大小，字符串需要根据 ASCII 码进行比较，相对较慢，

同时，在插入数据的时候，使用字符串移动次数比较频繁，并且使用字符串也比较占用存储空间，

所以从空间和时间上推荐使用整型自增主键。

## 2、InnoDB 非聚簇索引或二级索引 ##

InnoDB 非聚簇索引在叶子节点存储的是该行数据的主键值，而不是整行数据文件。

通过索引结构找到对应数据的主键，然后通过主键物理地址去聚簇索引上回表查询，

除非使用的是覆盖索引优化查询，可以避免回表查询。

![20190313224159408.png][]

**为什么非聚簇索引结构叶子节点存储的是主键值？**

1）一致性，为了聚簇和非聚簇索引数据一致性。如果非聚簇索引上面存储的是数据，

哪么如果数据发生变动，需要修改聚簇索引上的数据，同时也需要维护非聚簇索引的数据，

从事务的角度来说，这样就需要采取措施保证聚簇索引和非聚簇索引上的数据一致，

大大增加了处理数据的复杂性，可能会产生数据不同不，哪么使用不同索引查找到的数据就不一致

了。所以在非聚簇索引上存储主键值，如果数据发生改动，只需要修改聚簇索引上的数据，

而非聚簇索引存储的主键值不需要变动。本质上就是保证聚簇索引和非聚簇索引都是

从同一个地方拿数据，保证数据的一致性。

2）节省存储空间

非聚簇索引叶子节点存储主键的另外一个原因就是为了节省存储空间，能把数据归类在一个地方

供大家调用，何必要把数据到处散落呢。

# 五 联合索引实现原理 #

单值索引只是联合索引字段为 1 个的情况，联合索引由多个字段构成。

比如通过表里面三个字段建立联合索引。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 9][]

联合索引查找分析：

1）如果第一个字段是 101，直接就能比较出大小，无需第二个字段比较。

2）如果第一个字段 101 一样，则通过第二个字段比较大小。

3）如果第一个 103 和第二个 html5 一样，则通过第三个字段比较大小，

如此依次类推，就是联合索引查找方式。

# 六 最左前缀实现原理 #

比如有通过三个字段 seqNo，name, date 构建联合索引，如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 9][]

最左前缀就是多列字段构建的联合索引，最左边的字段优先比较。

最左前缀原理有很多使用原则，比如：全值匹配法则，最左前缀法则等等。

# 七 总结 #

1、MySQL BTree 索引使用 B+Tree 数据结构；

2、MySQL 不同存储引擎在 B+Tree 叶子节点存储的数据不一样，

MyISAM 主键索引和非主键索引存储文件指针，InnoDB 聚簇索引存储数据，InnoDB 非聚簇索引

存储主键值；

3、联合索引由多个字段联合构建，最左前缀原理查找时最左边的字段优先比较。

索引优化博大精深，这篇主要分析BTree底层数据结构，下篇结合索引数据结构去分析、使用和优

化。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70]: /images/20220310/f3f957b2417f46dabdd69ca6677d0d95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190312193047855.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk=,size_16,color_FFFFFF,t_70
[20190312121512388.png]: /images/20220310/d246d7d8395b49bfadc4419d5aceeb5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 2]: /images/20220310/645dacfa16fe4319b4db0f13ddf42fb8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 3]: /images/20220310/d2f1babf47d649c893ba6184548f8b2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 4]: /images/20220310/bfddba0c6e97479aab2865c5f76adffc.png
[20190313130507316.png]: /images/20220310/e2a130ca676a49b49234c5075a13c960.png
[20190313081157864.png]: /images/20220310/02732ccdc2044290954869bc86bcfbf1.png
[20190313081401875.png]: /images/20220310/7b55e2cbe4f1492986f25a2e868960c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 5]: /images/20220310/9ff6e84b2587498a9c5130b733c75459.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 6]: /images/20220310/0e2d001da16d43998da339f2708dd102.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 7]: /images/20220310/f546b12c494a40fd9399aa12e7cc17f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 8]: /images/20220310/c081380d39374a7f9323e577d671449a.png
[20190313224139434.png]: /images/20220310/16382240ba8e41758cf81d146b0c1e7b.png
[20190313224159408.png]: /images/20220310/fdf1e10ea94b4147a377a64ae9acdbf5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 9]: /images/20220310/10393566cc244b19af8127bde2f3154d.png