关于mysql:MySQL索引数据结构入门

之前松哥写过一个 MySQL 系列，然而过后是基于 MySQL5.7 的，最近有空在看 MySQL8 的文档，发现和 MySQL5.7 相比还是有不少变动，同时 MySQL 又是小伙伴们在面试时一个十分重要的知识点，因而松哥打算最近再抽空和小伙伴们聊一聊 MySQL，讲讲原理，讲讲优化，我会从最根本最简略的开始，和大家梳理 MySQL 中常见的面试知识点。

本文咱们就先从最简略的索引开始吧～

1. 什么是索引

说到索引，最常见的例子就是查字典，当咱们须要查问某一个字的含意时，失常操作都是先依据字典的索引，找到该字在哪一页，而后间接翻到该页就行了。如果没有这个索引的话，那么咱们就得一页一页的翻字典，直到找到该字。很显著，绝对于第一种计划，第二种计划效率就要低很多了。

数据库中的索引也是相似的。

索引，咱们也称之为 index 或者 key，当数据量比拟少的时候，索引对于查问产生的成果并不显著，所以索引经常被人所疏忽，然而当数据量比拟大的时候，一个优良的索引对查问产生的影响就是非常明显的了。在咱们所把握的各种 SQL 优化策略中，索引对 SQL 优化产生的成果算是最好的了，用好索引，SQL 性能可能会晋升好几个数量级。

这里有的小伙伴可能会有一个纳闷，很多索引优化策略都是针对传统的机械硬盘的，然而当初咱们大部分都是固态硬盘（SSD），很多针对机械硬盘的优化策略在 SSD 上仿佛并没有必要，那还有必要去思考索引优化吗？答案当然是有！无论是用什么样的磁盘，索引优化的整体准则都是不变的，只不过在 SSD 上，如果你的索引没有创立好，那么它对查问的影响不像对机械硬盘那么蹩脚。

2. 索引的数据结构

2.1 B+Tree 和 B-Tree

小伙伴们晓得，因为 MySQL 中的存储引擎设计成了可插拔的模式，任何机构和集体如果你有能力，都能够设计本人的存储引擎，而 MySQL 的索引是在存储引擎层实现的，而不是在服务器层实现的，所以不同存储引擎的索引工作形式都不一样，甚至，雷同类型的索引，在不同的存储引擎中实现计划都不同。

本文松哥次要和小伙伴们介绍咱们日常开发中最最常见的 InnoDB 存储引擎中的索引。

小伙伴们晓得，InnoDB 存储引擎的索引数据结构是一个 B+Tree，至于什么是 B+Tree，这并非本文的重点，我这里不啰嗦，不理解 B+Tree 的小伙伴能够自行搜寻一下学习一下。

假如我有如下数据：

当初我给 username 和 age 字段建设联结索引，那么最终数据在磁盘上的存储构造是 B+Tree，为了小伙伴可能更好的了解 B+Tree 和 B-Tree，我画了如下两张图：

这两张图看懂了，InnoDB 存储引擎的索引我感觉基本上都搞懂了 80% 了，松哥来和大家略微梳理一下这张图：

1. 首先这两张图都是一个多路均衡查找树，即，不是二叉树，是多叉树。
2. 绿色的方块示意指向下一个节点的指针；红色的方块示意指向下一个叶子节点的指针（B-Tree 中不存在该局部）；带暗影的矩形则示意索引数据。

3. B+Tree 非叶子节点只保留关键字的索引和指向下一个节点的指针（绿色区域），所有的数据最终都会保留到叶子节点。因而在具体的搜寻过程中，所有数据都必须要到叶子节点能力获取到，因而每次数据查问所需的 IO 次数都一样，这也就意味着 B+Tree 的查问速度比较稳定。

   如果是 B-Tree 则分支节点上也保留了指向具体数据的指针，并且分支节点上呈现的索引数据不会再次出现在叶子节点中，所以搜寻的时候可能搜寻到分支节点就找到须要的数据了，搜寻效率不稳固，如 af 在分支节点上就找到了，而 ac 则要到叶子节点上能力找到）。

4. B+Tree 中，因为分支节点只保留索引数据和指向下一个节点的指针，所以在雷同的磁盘空间中，可能指向更多的子节点，这就象征树的高度更低，搜寻所须要的 IO 次数更少，搜寻效率更高。

   B-Tree 中，因为分支节点不仅保留索引数据和指向下一个节点的指针，还保留了指向具体数据的指针，所以在雷同的空间下可能指向的子节点数量就少于 B+Tree，这就意味着雷同的数据量，B-Tree 树高更高，搜寻所需的 IO 次数更多，搜寻效率低。

5. B+Tree 叶子节点的关键字从小到大按顺序排列，右边结尾数据都会保留左边节点开始数据的指针（红色区域），这个指针在范畴搜寻的时候十分有用，例如想搜寻姓名在 ac～bc 之间的数据，依照树找到第一个节点 ac 之后，顺着指针始终往后找，找到第一个不满足条件的数据完结。

   如果是 B-Tree 则没有 ac 指向 bc 的指针，须要先回到分支节点 af 再持续向下搜寻，效率就会低很多。

6. B+Tree 的叶子节点都是有序排列的，所以 B+Tree 对于数据的排序有着更好的反对。

   B-Tree 因为有一部分数据保留在分支节点中，叶子节点并不是残缺的数据，所以对于排序、范畴搜寻的反对并不如 B+Tree。

7. B+Tree 数据划分的准则是左闭右开，以 (af,88) 这个节点为例，小于 (af,88) 节点的在右边，大于等于 (af,88) 节点的在左边。

   B-Tree 则是左开右开。

8. B+Tree 全表扫描更快，因为所有数据都呈现在叶子节点上，并且叶子节点之间还有指针相连，间接遍历即可。

   B-Tree 在全表扫描的时候则须要对树的每一层进行遍历能力读到所有数据。

9. 叶子节点指向数据的指针，如果是聚簇索引，则指向的是表中一条残缺的记录；如果是非聚簇索引，则指向的是具体的主键值。在以非聚簇索引为根据进行搜寻的时候，先找到记录的主键值，再依据 主键值去聚簇索引找到残缺的记录，这个过程就是回表（InnoDB 中）。

好了，置信通过下面八点的介绍，大家对于 B-Tree 和 B+Tree 曾经有了根本的认知了。

当咱们想要搜寻一条记录的时候，顺着根节点从上往下扫描树，比间接遍历一条一条的记录显然是要快很多。

说一个不太失当的比喻，MySQL 中的数据存储，就像是通过一个链表把所有数据依照程序串到一起，而后在这个链表下面又架了一个多路均衡查找树的感觉，搜寻的时候，依照链表一个一个找，就是全表扫描；从树的根节点开始找，就是用索引。

2.2 树高问题

一个经典的问题，高度为 3 的 B+Tree 大略能够保留多少条数据？

计算机在存储数据的时候，最小存储单元是扇区，一个扇区的大小是 512 字节，而文件系统（例如 XFS/EXT4）最小单元是块，一个块的大小是 4KB。然而 InnoDB 在进行磁盘操作的时候，并不是以扇区或者块为根据的，InnoDB 在进行磁盘操作的时候，是以页为单位的，有时候也称作逻辑页，每个逻辑页的大小默认是 16KB，即四个块。这就意味着，InnoDB 在实际操作磁盘的时候，每次从磁盘上读取数据，至多读取 16KB，每次向磁盘上写数据，也至多写 16KB，并不是你须要 1KB 就读取 1KB，即便你只须要 1KB 的数据，InnoDB 也会从磁盘中将 16KB 的数据读取到内存中。

通过如下命令咱们能够查看 MySQL 中 InnoDB 存储引擎逻辑页的大小：

16384/16=1024

后面的论断没问题。

以聚簇索引为例，当初咱们假如数据库中一条记录的大小是 1KB，那么一个逻辑页就能够存 16 条数据（叶子节点）。

对于非叶子节点存储的则是主键值 + 指针，在 InnoDB 中，一个指针的大小是 6 个字节，假如咱们的主键是 bigint，那么主键占 8 个字节，当然还有其余一些头信息也会占用字节咱们这里就不思考了，咱们大略算一下，小伙伴们心里有数即可：

16*1024/(8+6)=1170

即一个非叶子节点能够指向 1170 个子节点，那么一个三层的 B+Tree 能够存储的数据量为：

1170*1170*16=21902400

能够存储 2100 万 条数据。

在 InnoDB 存储引擎中，B+Tree 的高度个别为 2-4 层，这就能够满足千万级的数据的存储，查找数据的时候，一次页的查找代表一次 IO，那咱们通过主键索引查问的时候，其实最多只须要 2-4 次 IO 操作就能够了。

2.3 什么样的搜寻能够用到索引？

依据后面的介绍，咱们能够得出结论，在以下类型的搜寻中，会用到索引：

• 全值匹配

如上图中，如果咱们要搜寻 username 为 ac 且 age 为 98 的用户，就能够间接应用索引精确定位到。

• 最左匹配

如果咱们只是想搜寻 username 为 ac 的用户，很显著也能够应用上图索引，因为用户名是有序的。在上图中，username 和 age 组成了联结索引，其中 username 在前，age 在后，所以索引是先依照 username 进行排序，username 雷同的时候，再依照 age 进行排序的（如 bw 这个用户），如果咱们依照 username 进行搜寻，那么没问题，能够用上索引；然而如果咱们依照 age 进行搜寻，很显著，age 在整个索引树中是无序的，所以当咱们应用 age 作为搜寻条件的时候，是没法应用上图这个联结索引的。

• 前缀匹配

如果咱们搜寻的关键字只是 username 字段的前半部分，那么很显著，也是能够应用索引的，例如搜寻所有以 a 开始的 username。

• 范畴匹配

如果咱们的搜寻条件是一个范畴，很显著也能够应用到上述索引，例如搜寻姓名介于 ab～cc 之间的用户，只须要先从索引树的根节点开始，先找到 ab，而后依据叶子节点之间的指针顺藤摸瓜，找到 cc 之后的第一个数据（不满足条件的第一个数据）完结。

• 后面全值匹配，前面范畴匹配

例如查找 username 为 bw 且 age 介于 90～99 之间的用户，这种状况也能够应用到上图的索引。在上图索引树中，当 username 雷同的时候，就是依照 age 排序的，所以对于 username 都为 bw 的用户，它就是依照 age 进行排序的，此时，咱们当然能够依照 age 的范畴进行搜寻了。

• 笼罩索引

有的时候，咱们搜寻的数据都在索引树中了，例如上图中的索引，咱们想搜寻 username 为 bw 的用户的 age，因为 age 就在索引树中，间接返回即可，这就是笼罩索引了。

2.4 应用限度

毫无疑问，基于 B+Tree 的索引，其实也存在一些应用限度。例如：

1. 如果咱们将 age 作为搜寻条件，尽管 age 也是联结索引的一部分，然而 age 整体上在索引树中是无序的，所以将 age 作为搜寻条件是没法应用上述索引的。
2. 基于第一点，如果联结索引中还有第三、第四列等，那么但凡跳过第一列间接应用前面的列作为查问条件，索引都是不会失效的。
3. 范畴条件的左边无奈应用索引间接定位。例如搜寻 username 以 a 结尾并且年龄为 99 的用户：where username like 'a%' and age=99，此时 age=99 这个条件就无奈在索引树中间接解决了（能够通过索引下推过滤）。起因很简略，当咱们找到所有 username 以 a 开始的用户之后，这些用户的 age 并不是有序的，所以 age 就没法持续应用索引搜寻了（然而能够通过索引下推过滤）。

对于第三点，我举一个例子，假如咱们还有两个用户，别离是：

• username 为 ad 且 age 为 80；
• username 为 ae 且 age 为 88；

那么咱们欠缺一下下面 B+Tree 的图应该变成上面这样：

能够看到，username 以 a 开始的用户，age 并不是有序的，所以就只能通过索引下推过滤了，而无奈间接通过索引扫描定位数据。

对于第三点，如果范畴搜寻的字段值的可能性比拟少，则能够通过多个等于比拟来代替范畴搜寻。

2.5 自适应哈希索引

Hash 索引在 MySQL 中次要是 Memory 和 NDB 引擎反对，InnoDB 索引自身是 不反对的，然而 InnoDB 索引有一个个性叫做自适应哈希索引，自适应 三个字意味着整个过程是全自动的，不须要开发者配置。

当 InnoDB 监控到某些索引值被频繁的拜访时，那么它就会在 B+Tree 索引之上，构建一个 Hash 索引，进而通过 Hash 查找来快速访问数据。

默认状况下，自适应哈希索引是开启的状态，通过如下 SQL 咱们能够查看：

能够看到，这个默认就是开启的。

3. 小结

整体上来说，应用索引有如下长处：

• 缩小了服务器须要扫描的数据量。
• 索引能够帮忙服务器防止排序和创立长期表。
• 索引将随机 IO 变为了程序 IO。