本文由 简悦 SimpRead) 转码， 原文地址 mp.weixin.qq.com)
背景
我相信大家在数据库优化的时候都会说到索引，我也不例外，大家也基本上能对数据结构的优化回答个一二三，以及页缓存之类的都能扯上几句，但是有一次阿里 P9 的一个面试问我：你能从计算机层面开始说一下一个索引数据加载的流程么？（就是想让我聊 IO）
我当场就去世了…. 因为计算机网络和操作系统的基础知识真的是我的盲区，不过后面我恶补了，废话不多说，我们就从计算机加载数据聊起，讲一下换个角度聊索引。
正文
MySQL 的索引本质上是一种数据结构
让我们先来了解一下计算机的数据加载。
磁盘 IO 和预读：
先说一下磁盘 IO，磁盘读取数据靠的是机械运动，每一次读取数据需要寻道、寻点、拷贝到内存三步操作。
寻道时间是磁臂移动到指定磁道所需要的时间，一般在 5ms 以下；
寻点是从磁道中找到数据存在的那个点，平均时间是半圈时间，如果是一个 7200 转 / min 的磁盘，寻点时间平均是 600000/7200/2=4.17ms；
拷贝到内存的时间很快，和前面两个时间比起来可以忽略不计，所以一次 IO 的时间平均是在 9ms 左右。听起来很快，但数据库百万级别的数据过一遍就达到了 9000s，显然就是灾难级别的了。
考虑到磁盘 IO 是非常高昂的操作，计算机操作系统做了预读的优化，当一次 IO 时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。
每一次 IO 读取的数据我们称之为一页 (page)，具体一页有多大数据跟操作系统有关，一般为 4k 或 8k，也就是我们读取一页内的数据时候，实际上才发生了一次 IO。
（突然想到个我刚毕业被问过的问题，在 64 位的操作系统中，Java 中的 int 类型占几个字节？最大是多少？为什么？）
那我们想要优化数据库查询，就要尽量减少磁盘的 IO 操作，所以就出现了索引。
索引是什么？
MySQL官方对索引的定义为：索引 (Index) 是帮助MySQL高效获取数据的数据结构。
MySQL中常用的索引在物理上分两类，B - 树索引和哈希索引。
本次主要讲BTree索引。
BTree 索引
BTree又叫多路平衡查找树，一颗 m 叉的 BTree 特性如下：
- 树中每个节点最多包含 m 个孩子。
- 除根节点与叶子节点外，每个节点至少有 [ceil(m/2)] 个孩子（ceil()为向上取整）。
- 若根节点不是叶子节点，则至少有两个孩子。
- 所有的叶子节点都在同一层。
- 每个非叶子节点由 n 个 key 与 n+1 个指针组成，其中 [ceil(m/2)-1] <= n <= m-1 。
这是一个 3 叉（只是举例，真实会有很多叉）的 BTree 结构图，每一个方框块我们称之为一个磁盘块或者叫做一个 block 块，这是操作系统一次 IO 往内存中读的内容，一个块对应四个扇区，紫色代表的是磁盘块中的数据 key，黄色代表的是数据 data，蓝色代表的是指针 p，指向下一个磁盘块的位置。
来模拟下查找 key 为 29 的 data 的过程：
1、根据根结点指针读取文件目录的根磁盘块 1。【磁盘 IO 操作 1 次】
2、磁盘块 1 存储 17，35 和三个指针数据。我们发现 17<29<35，因此我们找到指针 p2。
3、根据 p2 指针，我们定位并读取磁盘块 3。【磁盘 IO 操作 2 次】
4、磁盘块 3 存储 26，30 和三个指针数据。我们发现 26<29<30，因此我们找到指针 p2。
5、根据 p2 指针，我们定位并读取磁盘块 8。【磁盘 IO 操作 3 次】
6、磁盘块 8 中存储 28，29。我们找到 29，获取 29 所对应的数据 data。
由此可见，BTree 索引使每次磁盘 I/O 取到内存的数据都发挥了作用，从而提高了查询效率。
但是有没有什么可优化的地方呢？
我们从图上可以看到，每个节点中不仅包含数据的 key 值，还有 data 值。而每一个页的存储空间是有限的，如果 data 数据较大时将会导致每个节点（即一个页）能存储的 key 的数量很小，当存储的数据量很大时同样会导致 B-Tree 的深度较大，增大查询时的磁盘 I/O 次数，进而影响查询效率。
B+Tree 索引
B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构。在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。
B+Tree 相对于 B-Tree 有几点不同：
非叶子节点只存储键值信息， 数据记录都存放在叶子节点中， 将上一节中的 B-Tree 优化，由于 B+Tree 的非叶子节点只存储键值信息，所以 B+Tree 的高度可以被压缩到特别的低。
具体的数据如下：
InnoDB 存储引擎中页的大小为 16KB，一般表的主键类型为 INT（占用 4 个字节）或 BIGINT（占用 8 个字节），指针类型也一般为 4 或 8 个字节，也就是说一个页（B+Tree 中的一个节点）中大概存储 16KB/(8B+8B)=1K 个键值（因为是估值，为方便计算，这里的 K 取值为〖10〗^3）。 也就是说一个深度为 3 的 B+Tree 索引可以维护 10^3 10^3 10^3 = 10 亿 条记录。（这种计算方式存在误差，而且没有计算叶子节点，如果计算叶子节点其实是深度为 4 了）
我们只需要进行三次的 IO 操作就可以从 10 亿条数据中找到我们想要的数据，比起最开始的百万数据 9000 秒不知道好了多少个华莱士了。
而且在 B+Tree 上通常有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。所以我们除了可以对 B+Tree 进行主键的范围查找和分页查找，还可以从根节点开始，进行随机查找。
数据库中的 B+Tree 索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。
上面的 B+Tree 示例图在数据库中的实现即为聚集索引，聚集索引的 B+Tree 中的叶子节点存放的是整张表的行记录数据，辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。
当通过辅助索引来查询数据时，InnoDB 存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。
不过，虽然索引可以加快查询速度，提高 MySQL 的处理性能，但是过多地使用索引也会造成以下弊端：
- 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
- 除了数据表占数据空间之外，每一个索引还要占一定的物理空间。如果要建立聚簇索引，那么需要的空间就会更大。
- 当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。
注意：索引可以在一些情况下加速查询，但是在某些情况下，会降低效率。
索引只是提高效率的一个因素，因此在建立索引的时候应该遵循以下原则：
- 在经常需要搜索的列上建立索引，可以加快搜索的速度。
- 在作为主键的列上创建索引，强制该列的唯一性，并组织表中数据的排列结构。
- 在经常使用表连接的列上创建索引，这些列主要是一些外键，可以加快表连接的速度。
- 在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，所以其指定的范围是连续的。
- 在经常需要排序的列上创建索引，因为索引已经排序，所以查询时可以利用索引的排序，加快排序查询。
- 在经常使用 WHERE 子句的列上创建索引，加快条件的判断速度。
现在大家知道索引为啥能这么快了吧，其实就是一句话，通过索引的结构最大化的减少数据库的 IO 次数，毕竟，一次 IO 的时间真的是太久了。。。
（END）
有你想看的精彩
一文带你深扒 ClassLoader 内核，揭开它的神秘面纱！
Hi，这里是 我没有三颗心脏，一个兴趣爱好广泛的 96 年 自由技术人，在公众号 wmyskxz 分享 「MoreThanCode」 的 知识 / 技术 / 成长 / 思考，2020，与您在 Be Better 的路上共同成长！
非常感谢各位人才能 看到这里，创作不易，文章有帮助可以点个 「在看」 或 「分享」，都是支持（莫要白嫖）！
Somewhere not here，愿你我都能奔赴在各自想去的路上，我们下篇文章见！
点击留言
若有收获，就点个赞吧
0 人点赞
