大数据培训 MySQL 索引 B+Tree

​

正确的创建合适的索引，是提升数据库查询性能的基础。在正式讲解之前，对后面举例中使用的表结构先简单看一下：

create table user(id bigint not null comment 'id' primary key,name varchar(200) null comment 'name',age bigint null comment 'age',gender int null comment 'gender',key (name));

索引是什么及工作机制？

索引是为了加速对表中数据行的检索而创建的一种分散存储的数据结构。其工作机制如下图：

上图中，如果现在有一条 sql 语句 select * from user where id = 40，如果没有索引的条件下，我们要找到这条记录，我们就需要在数据中进行全表扫描，匹配 id = 13 的数据。

如果有了索引，我们就可以通过索引进行快速查找，如上图中，可以先在索引中通过 id = 40 进行二分查找，再根据定位到的地址取出对应的行数据。

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

二叉树为什么不可行

对数据的加速检索，首先想到的就是二叉树，二叉树的查找时间复杂度可以达到 O(log2(n))。下面看一下二叉树的存储结构：

二叉树搜索相当于一个二分查找。二叉查找能大大提升查询的效率，但是它有一个问题：二叉树以第一个插入的数据作为根节点，如上图中，如果只看右侧，就会发现，就是一个线性链表结构。如果我们现在的数据只包含 1, 2, 3, 4，就会出现

以下情况：

如果我们要查询的数据为 4，则需要遍历所有的节点才能找到 4，即，相当于全表扫描，就是由于存在这种问题，所以二叉查找树不适合用于作为索引的数据结构_大数据培训。

平衡二叉树为什么不可行

为了解决二叉树存在线性链表的问题，会想到用平衡二叉查找树来解决。下面看看平衡二叉树是怎样的：

平衡二叉查找树定义为：节点的子节点高度差不能超过 1,如上图中的节点 20，左节点高度为 1，右节点高度 0，差为 1，所以上图没有违反定义，它就是一个平衡二叉树。保证二叉树平衡的方式为左旋，右旋等操作，至于如何左旋右旋，可以自行去搜索相关的知识。

如果上图中平衡二叉树保存的是 id 索引，现在要查找 id = 8 的数据，过程如下：

1. 把根节点加载进内存，用 8 和 10 进行比较，发现 8 比 10 小，继续加载 10 的左子树。

2. 把 5 加载进内存，用 8 和 5 比较，同理，加载 5 节点的右子树。

3. 此时发现命中，则读取 id 为 8 的索引对应的数据。

索引保存数据的方式一般有两种：

• 数据区保存 id 对应行数据的所有数据具体内容。

• 数据区保存的是真正保存数据的磁盘地址。

到这里，平衡二叉树解决了存在线性链表的问题，数据查询的效率好像也还可以，基本能达到 O(log2(n))， 那为什么 mysql 不选择平衡二叉树作为索引存储结构，他又存在什么样的问题呢？

1. 搜索效率不足。一般来说，在树结构中，数据所处的深度，决定了搜索时的 IO 次数（MySql 中将每个节点大小设置为一页大小，一次 IO 读取一页 / 一个节点）。如上图中搜索 id = 8 的数据，需要进行 3 次 IO。当数据量到达几百万的时候，树的高度就会很恐怖。

2. 查询不不稳定。如果查询的数据落在根节点，只需要一次 IO，如果是叶子节点或者是支节点，会需要多次 IO 才可以。

3. 存储的数据内容太少。没有很好利用操作系统和磁盘数据交换特性，也没有利用好磁盘 IO 的预读能力。因为操作系统和磁盘之间一次数据交换是以页为单位的，一页大小为 4K，即每次 IO 操作系统会将 4K 数据加载进内存。但是，在二叉树每个节点的结构只保存一个关键字，一个数据区，两个子节点的引用，并不能够填满 4K 的内容。幸幸苦苦做了一次的 IO 操作，却只加载了一个关键字。在树的高度很高，恰好又搜索的关键字位于叶子节点或者支节点的时候，取一个关键字要做很多次的 IO。

那有没有一种结构能够解决二叉树的这种问题呢？有，那就是多路平衡查找树。

多路平衡查找树(Balance Tree)

B Tree 是一个绝对平衡树，所有的叶子节点在同一高度，如下图所示：

上图为一个 2-3 树（每个节点存储 2 个关键字，有 3 路），多路平衡查找树也就是多叉的意思，从上图中可以看出，每个节点保存的关键字的个数和路数关系为：关键字个数 = 路数 – 1。

假设要从上图中查找 id = X 的数据，B TREE 搜索过程如下：

1. 取出根磁盘块，加载 40 和 60 两个关键字。

2. 如果 X 等于 40，则命中；如果 X 小于 40 走 P1；如果 40 < X < 60 走 P2；如果 X = 60，则命中；如果 X > 60 走 P3。

3. 根据以上规则命中后，接下来加载对应的数据， 数据区中存储的是具体的数据或者是指向数据的指针。

为什么说这种结构能够解决平衡二叉树存在的问题呢？

B Tree 能够很好的利用操作系统和磁盘的交互特性， MySQL 为了很好的利用磁盘的预读能力，将页大小设置为 16K，即将一个节点（磁盘块）的大小设置为 16K，一次 IO 将一个节点（16K）内容加载进内存。这里，假设关键字类型为 int，即 4 字节，若每个关键字对应的数据区也为 4 字节，不考虑子节点引用的情况下，则上图中的每个节点大约能够存储（16 * 1000）/ 8 = 2000 个关键字，共 2001 个路数。对于二叉树，三层高度，最多可以保存 7 个关键字，而对于这种有 2001 路的 B 树，三层高度能够搜索的关键字个数远远的大于二叉树。

这里顺便说一下：在 B Tree 保证树的平衡的过程中，每次关键字的变化，都会导致结构发生很大的变化，这个过程是特别浪费时间的，所以创建索引一定要创建合适的索引，而不是把所有的字段都创建索引，创建冗余索引只会在对数据进行新增，删除，修改时增加性能消耗。

B 树确实已经很好的解决了问题，我先这里先继续看一下 B+Tree 结构，再来讨论 BTree 和 B+Tree 的区别。

先看看 B+Tree 是怎样的，B+Tree 是 B Tree 的一个变种，在 B+Tree 中，B 树的路数和关键字的个数的关系不再成立了，数据检索规则采用的是左闭合区间，路数和关键个数关系为 1 比 1，具体如下图所示：

如果上图中是用 ID 做的索引，如果是搜索 X = 1 的数据，搜索规则如下：

1. 取出根磁盘块，加载 1，28，66 三个关键字。

2. X <= 1 走 P1，取出磁盘块，加载 1，10，20 三个关键字。

3. X <= 1 走 P1，取出磁盘块，加载 1，8，9 三个关键字。

4. 已经到达叶子节点，命中 1，接下来加载对应的数据，图中数据区中存储的是具体的数据。

B TREE 和 B+TREE 区别是什么？

1. B+Tree 关键字的搜索采用的是左闭合区间，之所以采用左闭合区间是因为他要最好的去支持自增 id，这也是 mysql 的设计初衷。即，如果 id = 1 命中，会继续往下查找，直到找到叶子节点中的 1。

2. B+Tree 根节点和支节点没有数据区，关键字对应的数据只保存在叶子节点中。即只有叶子节点中的关键字数据区才会保存真正的数据内容或者是内容的地址。而在 B 树种，如果根节点命中，则会直接返回数据。

3. 在 B+Tree 中，叶子节点不会去保存子节点的引用。

4. B+Tree 叶子节点是顺序排列的，并且相邻的节点具有顺序引用的关系，如上图中叶子节点之间有指针相连接。

MySQL 为什么最终要去选择 B+Tree？

1. B+Tree 是 B TREE 的变种，B TREE 能解决的问题，B+TREE 也能够解决（降低树的高度，增大节点存储数据量）

2. B+Tree 扫库和扫表能力更强。如果我们要根据索引去进行数据表的扫描，对 B TREE 进行扫描，需要把整棵树遍历一遍，而 B+TREE 只需要遍历他的所有叶子节点即可（叶子节点之间有引用）。

3. B+TREE 磁盘读写能力更强。他的根节点和支节点不保存数据区，所以根节点和支节点同样大小的情况下，保存的关键字要比 B TREE 要多。而叶子节点不保存子节点引用，能用于保存更多的关键字和数据。所以，B+TREE 读写一次磁盘加载的关键字比 B TREE 更多。

4. B+Tree 排序能力更强。上面的图中可以看出，B+Tree 天然具有排序功能。

5. B+Tree 查询性能稳定。B+Tree 数据只保存在叶子节点，每次查询数据，查询 IO 次数一定是稳定的。当然这个每个人的理解都不同，因为在 B TREE 如果根节点命中直接返回，确实效率更高。

MySQL B+Tree 具体落地形式

这里主要讲解的是 MySQL 根据 B+Tree 索引结构不同的两种存储引擎（MYISAM 和 INNODB）的实现。

首先找到 MySQL 保存数据的文件夹，看看 MySQL 是如何保存数据的：

mysql> show variables like '%datadir%';+---------------+------------------------+| Variable_name | Value |+---------------+------------------------+| datadir | /usr/local/mysql/data/ |+---------------+------------------------+

进入到这个目录下，这个目录下保存的是所有数据库，再进入到具体的一个数据库目录下。就能够看到 MySQL 存储数据和索引的文件了。

这里我创建了两张表，user_innod 和 user_myisam，分别指定索引为 innodb 和 myisam。对于每张表，MySQL 会创建相应的文件保存数据和索引，具体如下：

-rw-rw----. 1 mysql mysql 8652 May 3 21:11 user_innodb.frm-rw-rw----. 1 mysql mysql 109051904 May 7 21:26 user_innodb.ibd-rw-rw----. 1 mysql mysql 8682 May 16 18:27 user_myisam.frm-rw-rw----. 1 mysql mysql 0 May 16 18:27 user_myisam.MYD-rw-rw----. 1 mysql mysql 1024 May 16 18:27 user_myisam.MYI

从图中可以看出：

• MYISAM 存储引擎存储数据库数据，一共有三个文件： Frm：表的定义文件。 MYD：数据文件，所有的数据保存在这个文件中。 MYI：索引文件。

• Innodb 存储引擎存储数据库数据，一共有两个文件(没有专门保存数据的文件)： Frm 文件：表的定义文件。 Ibd 文件：数据和索引存储文件。数据以主键进行聚集存储，把真正的数据保存在叶子节点中。

MyISAM 存储引擎

说明：为了画图简便，下面部分图使用在线数据结构工具进行组织数据，组织的 B+Tree 为右闭合区间，但不影响理解存储引擎数据存储结构。

在 MYISAM 存储引擎中，数据和索引的关系如下：

如何查找数据的呢？

如果要查询 id = 40 的数据：先根据 MyISAM 索引文件（如上图左）去找 id = 40 的节点，通过这个节点的数据区拿到真正保存数据的磁盘地址，再通过这个地址从 MYD 数据文件（如上图右）中加载对应的记录。

如果有多个索引，表现形式如下：

所以在 MYISAM 存储引擎中，主键索引和辅助索引是同级别的，没有主次之分。

Innodb 存储引擎

Innodb 主键索引为聚集索引，首先简单理解一下聚集索引的概念：数据库表行中数据的物理顺序和键值的逻辑顺序相同。

Innodb 以主键索引来聚集组织数据的存储，下面看看 Innodb 是如何组织数据的。

如上图中，叶子节点的数据区保存的就是真实的数据，在通过索引进行检索的时候，命中叶子节点，就可以直接从叶子节点中取出行数据。mysql5.5 版本之前默认采用的是 MyISAM 引擎，5.5 之后默认采用的是 innodb 引擎。

在 innodb 中，辅助索引的格式如下图所示？

如上图，主键索引的叶子节点保存的是真正的数据。而辅助索引叶子节点的数据区保存的是主键索引关键字的值。

假如要查询 name = C 的数据，其搜索过程如下：

1. 先在辅助索引中通过 C 查询最后找到主键 id = 9.

2. 在主键索引中搜索 id 为 9 的数据，最终在主键索引的叶子节点中获取到真正的数据。

所以通过辅助索引进行检索，需要检索两次索引。

之所以这样设计，一个原因就是：如果和 MyISAM 一样在主键索引和辅助索引的叶子节点中都存放数据行指针，一旦数据发生迁移，则需要去重新组织维护所有的索引。

把 Innodb 和 MYISAM 区别放在一张图中看，就如下所示：

创建索引的几大原则

列的离散型

离散型的计算公式：count(distinct column_name):count(*)，就是用去重后的列值个数比个数。值在 (0,1] 范围内。离散型越高，选择型越好。

如下表中各个字段，明显能看出 Id 的选择性比 gender 更高。

mysql> select * from user;+----+--------------+------+--------+| id | name | age | gender |+----+--------------+------+--------+| 20 | 君莫笑 | 15 | 1 || 40 | 苏沐橙 | 12 | 0 || 50 | 张楚岚 | 25 | 1 || 60 | 诸葛青 | 27 | 1 || 61 | 若有人兮 | 38 | 0 || 64 | 冯宝宝 | 18 | 0 |+----+--------------+------+--------+

为什么说离散型越高，选择型越好？

因为离散度越高，通过索引最终确定的范围越小，最终扫面的行数也就越少。

最左匹配原则

对于索引中的关键字进行对比的时候，一定是从左往右以此对比，且不可跳过。之前讲解的 id 都为 int 型数据，如果 id 为字符串的时候，如下图：

当进行匹配的时候，会把字符串转换成 ascll 码，如 abc 变成 97 98 99，然后从左往右一个字符一个字符进行对比。所以在 sql 查询中使用 like %a 时候索引会失效，因为 %表示全匹配，如果已经全匹配就不需要索引，还不如直接全表扫描。

最少空间原则

前面已经说过，当关键字占用的空间越小，则每个节点保存的关键字个数就越多，每次加载进内存的关键字个数就越多，检索效率就越高。创建索引的关键字要尽可能占用空间小。

联合索引

• 单列索引：节点中的关键字[name]

• 联合索引：节点中的关键字[name, age]

可以把单列索引看成特殊的联合索引，联合索引的比较也是根据最左匹配原则。

联合索引列的选择原则

• 经常用的列优先（最左匹配原则）

• 离散度高的列优先（离散度高原则）

• 宽度小的列优先（最少空间原则）

实例分析

下面简单举例平时经常会遇到的问题：

如，平时经常使用的查询 sql 如下：

select * from users where name = ?select * from users where name = ? and age = ?

为了加快检索速度，为上面的查询 sql 创建索引如下：

create index idx_name on users(name)create index idx_name_age on users(name, age)

在上面解决方案中，根据最左匹配原则，idx_name 为冗余索引， where name = ?同样可以利用索引 idx_name_age 进行检索。冗余索引会增加维护 B+TREE 平衡时的性能消耗，并且占用磁盘空间。

覆盖索引

如果查询的列，通过索引项的信息可直接返回，则该索引称之为查询 SQL 的覆盖索引。覆盖索引可以提高查询的效率。

如上图，如果通过 name 进行数据检索：

select * from users where name = ?

需要需要在 name 索引中找到 name 对应的 Id，然后通过获取的 Id 在主键索引中查到对应的行。整个过程需要扫描两次索引，一次 name，一次 id。

如果我们查询只想查询 id 的值，就可以改写 SQL 为：

select id from users where name = ?

因为只需要 id 的值，通过 name 查询的时候，扫描完 name 索引，我们就能够获得 id 的值了，所以就不需要再去扫面 id 索引，就会直接返回。

当然，如果你同时需要获取 age 的值：

select id，age from users where name = ?

这样就无法使用到覆盖索引了。

知道了覆盖索引，就知道了为什么 sql 中要求尽量不要使用 select *，要写明具体要查询的字段。其中一个原因就是在使用到覆盖索引的情况下，不需要进入到数据区，数据就能直接返回，提升了查询效率。在用不到覆盖索引的情况下，也尽可能的不要使用 select *，如果行数据量特别多的情况下，可以减少数据的网络传输量。当然，这都视具体情况而定，通过 select 返回所有的字段，通用性会更强，一切有利必有弊。

总结

• 索引列的数据长度满足业务的情况下能少则少。

• 表中的索引并不是越多越好，冗余或者无用索引会占用磁盘空间并且会影响增删改的效率。

• Where 条件中，like 9%， like %9%， like%9，三种方式都用不到索引。后两种方式对于索引是无效的。第一种 9%是不确定的，决定于列的离散型，结论上讲可以用到，如果发现离散情况特别差的情况下，查询优化器觉得走索引查询性能更差，还不如全表扫描。

• Where 条件中 IN 可以使用索引， NOT IN 无法使用索引。

• 多用指定查询，只返回自己想要的列，少用 select *。

• 查询条件中使用函数，索引将会失效，这和列的离散性有关，一旦使用到函数，函数具有不确定性。

• 联合索引中，如果不是按照索引最左列开始查找，无法使用索引。

• 对联合索引精确匹配最左前列并范围匹配另一列，可以使用到索引。

• 联合索引中，如果查询有某个列的范围查询，其右边所有的列都无法使用索引。

文章转载来源于大数据学习与分享

​