MySQL 索引的底层数据结构原理剖析 (二叉树、 红黑树、Hash、B-Tree、B+Tree)

一. 前言

1. 说明

　我们平时所说的：聚集索引(主键索引)，次要索引，覆盖索引，复合索引，前缀索引，唯一索引在 MySQL5.7 和 8.0 版本默认都是使用 B+Tree 索引，除此之外还有 Hash 索引。至于 MySQL5.7 之前版本，这里就不过多探究了。

　学习各种数据结构图解网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html (推荐)

2. 有索引和没索引的区别

　下图，左边表格是没有索引，右边是二叉树索引，以 col2 为索引列.

　PS: 在右边二叉树的结构中，每个节点都是 key-value 键值对的形式。key：col2 所在行在磁盘文件中的地址指针（比如 34 所在行，通过 key 中存储 0x07 这个指针就能找到是第 1 行），value：就是 col2 的值。

​分析下面 SQL 语句

select * from t where col2 = 89；

(1). 左边没有索引，搜索 col2=89 需要从上往下搜索， 6 次 才能找到，也就是 6 次回表操作（6 次 IO）。

(2). 右边是二叉树索引，搜索 col2=89 搜索 2 次 就可以找到，也就是 2 次回表操作（2 次 IO），性能提升明显。

二. 二叉树、红黑树、Hash

1. 二叉树

(1). 二叉树的特点

　左子节点值 < 节点值；右子节点值 > 节点值；当数据量非常大时，要查找的数据又非常靠后，和没有索引相比，那么二叉树结构的查询优势将非常明显。

(2). 存在的问题

　如下图，可以看出，二叉树出现单边增长时，二叉树变成了“链”，这样查找一个数的时候，速度并没有得到很大的优化。

​2. 红黑树

(1). 特点

　A. 节点是红色或者黑色

　B. 根节点是黑色

　C. 每个叶子的节点都是黑色的空节点（NULL）

　D. 每个红色节点的两个子节点都是黑色的。

　E. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

​(2). 存在的问题

红黑树虽然和二叉树相比，一定程度上缓解了单边过长的问题，但是它依旧存储高度问题。

　假设现在数据量有 100 万，那么红黑树的高度大概为 100,0000 = 2^n， n 大概为 20。那么，至少要 20 次的磁盘 IO，这样，性能将很受影响。如果数据量更大，IO 次数更多，性能损耗更大。所以红黑树依旧不是最佳方案。

(3). 思考：针对上面的红黑树结构，我们能否优化一下呢？

　上述红黑树默认一个节点就存了一个 (索引+磁盘地址)，我们设想一个节点存多个 （索引+磁盘地址），这样就可以降低红黑树的高度了。 实际上我们设想的这种结构就是 B-Tree。

3. Hash

(1). 原理

　A. 事先将索引通过 hash 算法后得到的 hash 值(即磁盘文件指针）存到 hash 表中。

　B. 在进行查询时，将索引通过 hash 算法，得到 hash 值，与 hash 表中的 hash 值比对。通过磁盘文件指针，只要一次磁盘 IO 就能找到要的值。

例如：

　在第一个表中，要查找 col=6 的值。hash(6) 得到值，比对 hash 表，就能得到 89。性能非常高。

(2). 存在的问题

　但是 hash 表索引存在问题，如果要查询 带范围的条件时，hash 索引就歇菜了。

select *from t where col1>=6;

更多 C++后台开发技术点知识内容包括 C/C++，Linux，Nginx，ZeroMQ，MySQL，Redis，MongoDB，ZK，流媒体，音视频开发，Linux 内核，TCP/IP，协程，DPDK 多个高级知识点。

C/C++Linux服务器开发高级架构师/C++后台开发架构师​免费学习地址

【文章福利】另外还整理一些C++后台开发架构师 相关学习资料，面试题，教学视频，以及学习路线图，免费分享有需要的可以点击领取

三. B-Tree 和 B+Tree

1. B-Tree

(1). 特点

　B-Tree 索引能很好解决红黑树中遗留的高度问题，B-Tree 是一种平衡的多路查找（又称排序）树，在文件系统中和数据库系统有所应用，主要用作文件的索引，其中的 B 就表示平衡（Balance）。

　为了描述 B-Tree，首先定义一条数据记录为一个二元组 [key, data]，key 为记录的键值 key，对于不同数据记录，key 是互不相同的；data 为数据记录除以 key 外的数据 （这里指的是聚集索引）。那么 B-Tree 是满足下列条件的数据结构：

　　A. d 为大于 1 的一个正整数，称为 BTree 的度；

　　B. h 为一个正整数，称为 BTree 的高度；

　　C. key 和指针互相间隔，节点两端是指针；

　　D. 叶子节点具有相同的深度，叶子节点的指针为空，节点中数据索引(下图中的 key)从左往右递增排列。

说明：下面的图都是以主键索引为例来画图，至于非主键索引(非聚集索引)，无非就是 data 里存的内容不同，详细对比见后面章节。

图 1：

​图 2：

​(2). 分析

模拟下查找 key 为 29 的 data 的过程：

　A、根据根结点指针读取文件目录的根磁盘块 1。【磁盘 IO 操作第 1 次】

　B、磁盘块 1 存储 17，35 和三个指针数据。我们发现 17<29<35，因此我们找到指针 p2。

　C、根据 p2 指针，我们定位并读取磁盘块 3。【磁盘 IO 操作 2 次】

　D、磁盘块 3 存储 26，30 和三个指针数据。我们发现 26<29<30，因此我们找到指针 p2。

　E、根据 p2 指针，我们定位并读取磁盘块 8。【磁盘 IO 操作 3 次】

　F、磁盘块 8 中存储 28，29。我们找到 29，获取 29 所对应的数据 data。

(3). 存在问题

A. 比如，下面查询语句，那么不但需要叶子节点>20 的值，也需要非叶子节点在右边节点的值。即下图画圈的两部分， B-Tree 似乎在范围查找没有更简便的方法，为了解决这一问题。我们可以用 B+Tree。

select *from t where col1 > 20;

​B. 深度问题

　从图上可以看到，每个节点中不仅包含数据的 key 值，还有 data 值。而每一个节点的存储空间是有限的(mysql 默认设置一个节点的大小为 16K)，如果 data 中存放的数据较大时，将会导致每个节点（即一个页）能存储的 key 的数量（索引的数量）很小，所以当数据量很多，且每行数据量很大的时候，同样会导致 B-Tree 的深度较大，增大查询时的磁盘 I/O 次数，进而影响查询效率。所以引入 B+Tree

2. B+Tree

(1). 特点

B+Tree 是在 B-Tree 基础上的一种优化，使其更适合实现外存储索引结构。在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。

　A. 非叶子节点不存储 data，只存储索引，可以存放更多索引。

　B. 叶子节点不存储指针。

　C. 顺序访问指针，提高区间访问性能。

　D. 非叶子节点中的索引最终还是会在叶子节点上存储一份，也就是叶子节点会包含非叶子节点上的所有索引。

　E. 一个父节点，它的左侧子节点都小于父节点的值，右侧的子节点都大于等于父节点的值。

　F. 每一层节点从左往右都是递增排列，无论是数值型还是字符型。

注：MySQL 索引默认的存储结构使用的就是 B+Tree。

图 1：

​图 2：

​剖析：如上图，在叶子节点上注意是 MySQL 已经有成双向箭头（原生 B+Tree 是单向的），而且从左到右是递增顺序的，所以很好的解决了 > 和 < 这类查找问题。

(2). 分析

　假如：以一个高度为 3 的 B+Tree 为例，B+Tree 的表都存满了，能存储多少数据？

首先，查看 MySQL 默认一个节点页的大小：

SHOW GLOBAL STATUS like 'Innodb_page_size';

如下图：大小为 16K。

​然后，假设主键 Id 为 bigint 类型，那么长度就是 8B，指针在 Innodb 源码中大小为 6B，所以一共就是 14B，再假设最后一层，存放的数据 data 为 1k 大小（能存很多内容了），那么

A. 第一层最大节点数为： 16k / (8B + 6B) = 1170 (个)；

　　B. 第二层最大节点数也应为：1170 个；

　　C. 第三层最大节点数为：16k / 1k = 16 (个)。

　则，一张 B+Tree 的表最多存放 1170 * 1170 * 16 = 21902400 ≈ 2 千万。所以，通过分析，我们可以得出，B+Tree 结构的表可以容纳千万数据量的查询。而且一般来说，MySQL 会把 B+Tree 根节点放在内存中，那只需要两次磁盘 IO（第二层 1 次，第三层 1 次）就行。

(3). 扩展

　数据库中的 B+Tree 索引可以分为聚集索引（clustered index，也叫主键索引）和辅助索引（secondary index，也叫非聚集索引）。

　上面的 B+Tree 示例图在数据库中的实现对应的是聚集索引，聚集索引的 B+Tree 中的叶子节点存放的是整张表的行记录数据(除主键以外的所有数据)，辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的对应的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB 存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。

四. 深究索引在 B+Tree 上的存储

说明：下面的介绍均是指 InnoDB 存储引擎 B+Tree

1. 聚集索引

　聚集索引也叫主键索引，叶子节点中的 data 存储的是该主键对应整行数据，通常 B+Tree 的高度为 3，也就是有三层节点，MySQL 会把 B+Tree 第一层也就是根节点放在内存中，我们根据主键索引查数据，只需要两次磁盘 IO（第二层 1 次，第三次 1 次）即可。寻址过程类似上面 B-Tree 那个寻址步骤。

​2. 非聚集索引

　非聚集索引也叫辅助索引，叶子节点中的 data 存储的该索引对应的该行数据的主键值，所以非聚集索引的寻址过程分两种情况：

(1). 非聚集索引已经索引覆盖了，那么只需要遍历这非聚集索引这一个 B+Tree 即可，按照上面的分析，需要两次磁盘 IO 即可（mysql 会把根节点放到内存中）。

(2). 非聚集索引不能索引覆盖，那么先需要在非聚集索引这个 B+Tree 上两次 IO 找到该行数据对应的主键值，然后拿着主键去 聚集索引的 B+Tree 上找对应的其它数据。相比第一种情况 IO 次数要多，所以我们通常喜欢索引覆盖。

下图表示非聚集索引不能索引覆盖的情况：

　　右侧的辅助索引先拿到主键值 5，然后去左侧的主键索引中寻址，最后可以得到整行内容。

​3. 联合索引

　假设有一张表 T1，有 id、x1、x2、x3、x4 字段，id 上有主键索引，给 x1、x2、x3 添加联合索引，如下图：

​剖析：

　(1). 上图联合索引的 key 中存储 x1-x2-x3 三个值，存储顺序从左往右依次递增，

　先比较 x1，如：10002<10004，

​　如果 x1 相同，在比较 x2，如 Assistant < Engineer

​　如果 x2 相同，再比较 x3，如 1997-08-03 < 2001-09-03

​ (2). 如果查找 x1 x2 x3，在非聚集索引这个 B+Tree 直接就可以从 key 中拿到，如果还要查找 x4，则需要拿到 data 中存储的主键值，然后再去聚集索引中查找。（这就是为什么首选覆盖索引的原因）

4. 灵魂拷问

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

A. 为什么要有主键？

　mysql 底层就是用 B+Tree 维护的，而 B+Tree 的结构就决定了必须有主键才能构建 B+Tree 树这个结构。每个表在磁盘上，是单独的一个文件。索引和数据都在其中，文件是按照主键索引组织的一个 B+TREE 结构。假如没有定义主键，MySQL 会在挑选能唯一标识的字段作为索引；假如找不到，会生成一个默认的隐藏列作为主键列。

B. 为什么用整型主键？

假如使用类似 UUID 的字符串作为主键，那么在查找时，需要比较两个主键是否相同，这是一个相比整型比较 非常耗时的过程。需要一个字符，一个字符的比较，自然比较慢。

C. 为什么用自增主键？

　① 后面的主键索引总是大于前面的主键索引，在做范围查询时，非常方便找到需要的数据。

　② 在添加的过程中，因为是自增的，每次添加都是在后面插入，树分裂的机会小；而 UUID 大小不确定，分裂机会大，需要重新平衡树结构，性能损耗大。

(2). 为什么非主键索引结构叶子节点存储的是主键值，而不是全部数据？

　① 节省空间：指向主键的节点，不用再存储一份相同的数据；（否则的话，如果建立多个非主键索引，每个上面都存储的完整数据，非常占用空间）

　② 数据一致性：如果修改索引 15 的数据，那只要修改主键的 data，而如果非主键的 data 也存一份的话，那得修改两份，这样就涉及到事务一致性的问题，耗时，性能低。

(3). 为什么希望使用覆盖索引？

　如果非聚集索引中能索引覆盖，那么我们只需要遍历非聚集索引这个 B+Tree 从其中的 Key 里拿到索引值就可，只需要遍历一棵树。 如果不能索引覆盖，需要先遍历非聚集索引，然后拿到 data 中存储的主键值，再去聚集索引中遍历查找数据，相比索引覆盖的话，IO 次数更多，性能相对低。

五. MyISAM 和 InnoDB 的索引结构对比

1. MyISAM 下索引结构

MyISAM 索引文件和数据文件是分开的(非聚集)，存储引擎在磁盘中文件有三个，

　　一个是 .frm 文件(数据表定义)，

一个是 .MYI(索引)，

一个是 .MYD(实际数据，存储的是一整行的数据，包括索引值)。

MY 文件是 B+Tree 为底层组织的文件。

​　　剖析： 比如查找 49，那么在 .MYI 中找到 49 对应的磁盘指针 0x49，根据 0x49 去 .MYD 找到实际的数据内容 data。

　　注：在 MyISAM 存储引擎中，无论是主键索引还是非主键索引，B+Tree 中叶子结点中的 data 存储的都是该行数据对应的磁盘指针，根据指针再去拿数据。

2. InnoDB 索引结构

InnoDB 存储引擎它的表数据文件本身就是按 B+Tree 组织的一个索引文件。不同于 MyISAM 存储引擎是，数据不分离。

　一个 frm 文件存储数据表定义，一个 ibd 文件存放的索引和实际数据。

​ 如下图一，为聚集索引，找到 49 的索引之后，数据就在该节点，不必像 MyISAM 存储引擎那样，需要根据磁盘指针到另一个文件中取数据。性能比 MyISAM 高。

​原文链接：第二节：MySQL索引的底层数据结构原理剖析(二叉树、 红黑树、Hash、B-Tree、B+Tree)