MySQL 索引深度解析
MySQL 索引深度解析
一、常见模型
1.1 索引实现
地点
在 MySQL 中，索引是在存储引擎层实现的，所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。（还记得前面存储引擎层实现了 undo log 的存储吗？）而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。
实现方式
在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又因为前面我们提到的，InnoDB 使用了 B+树索引模型，所以数据都是存储在 B+树中的。
每一个索引在 InnoDB 里面对应一棵 B+树（想想 everything 先建立索引，然后再便于我们查找文件就知道了，又或者是 ES 的倒排索引，索引的目的就是加快查找速度）。
索引类型
- 主键索引 - 的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）
- 非主键索引 - 的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）
主键索引和普通索引的查询区别
根据上面的索引结构说明，我们来讨论一个问题：基于主键索引和普通索引的查询有什么区别？
- 如果语句是
select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+树 - 如果语句是
select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表
也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
1.2 有序数组
有序数组在等值查询和范围查询场景中的性能就都非常优秀。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。
所以，有序数组索引只适用于静态存储引擎
1.3 哈希表
哈希表好处是增加新的记录时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的
1.4 搜索树
种类
树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。
二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。
你可以想象一下一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。
为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用”N 叉”树。这里，”N 叉”树中的”N”取决于数据块的大小。
以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。
N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。
二、B+树原理
2.1 ⭐为什么使用 B+ 树
MySQL 需要支持高效(有冗余索引 / 冗余节点 – 非叶子节点，树的变形不会过于复杂)，少 IO 操作(树的层数矮，非叶子节点存储的有效索引更多)，范围查找(双向链表)，这三个功能，所以其实就是分析为什么其他的数据结构不支持或者没 B+ 树这三个功能强大就行了。
磁盘知识
除此之外，我们需要知道关于磁盘的一点小知识:
- 磁盘读写的最小单位是扇区，只有 512B，操作系统一次会读写多个扇区
- 操作系统的最小读写单位是块 Block，Linux 中块的大小为 4KB
- 内存访问速度是磁盘访问速度的几万倍
通过 fsutil fsinfo ntfsinfo c: 命令可以看到 Windows 操作系统上块的大小也是 4KB，可以看到: 每扇区字节数: 512，每物理扇区字节数: 4096。
各种树的对比
BST 二叉树
- BST 有时候会退化为链表，高度会线性增加，很明显会导致磁盘 IO 次数过多
- BST = Binary Search Tree（二叉搜索树）
- 定义规则：对任意一个节点，左子树所有节点值 < 当前节点值，右子树所有节点值 > 当前节点值，左右子树本身也都是 BST
AVL 二叉树
- AVL 不会退化为链表，但是树的高度还是很容易增高，也就是 IO 次数还是很多
- AVL = 自平衡二叉搜索树（Adelson-Velsky and Landis）
- 本质：BST + 自动保持平衡
B 树 多叉树
- B 树范围查询需要进行中序遍历，涉及多节点 IO
- 而且由于 B 树会将数据存储在非叶子节点，会导致读取到的数据页中索引数据太少，要多进行几次 IO 才行，可以理解为有用索引数据率太低了，也会导致多次 IO
B+ 树 多叉树
- 非叶子节点不存放数据，读取到的数据页中有效索引更多，IO 次数会更少
- B+ 树有冗余节点，删除数据有概率不会发生复杂的变形操作
- B+ 树插入和删除效率比 B 树高
- B+ 树叶子节点用双向链表进行连接，对于范围查找很有帮助
还有一点要说清楚，数据持久化到磁盘其实是以索引的方式进行的。所以讨论用什么数据结构作为索引，其实是在讨论存储的时候用什么数据结构
2.2 ⭐B+ 树的查询过程
B+ 树是如何进行查询的呢？其实都是要进行二分的。
非叶子节点接到一个命令，要求查找一个 key 为 x 的数据，首先会在 Root 节点进行二分。因为非叶子节点的页目录的槽中会存储下一个节点的指针和该节点的最小值，直到找到叶子节点。
页目录会根据槽来二分定位，然后再遍历所有记录。槽主要的区别就是叶子节点存储的是一组最后一个记录的地址，非叶子节点存储的是页的地址
查询步骤
- 从 Root 页开始
- 在非叶子节点中比较 key
- 选择子页指针（不是二分）
- 重复直到叶子节点
- 在叶子节点：
- 对页目录二分
- 顺序遍历 record
- 找到行 / 或确认不存在
2.3 ⭐单表不要超过 2000W 行
之前的计算有一点不准确，具体的说就是我们还要用 16KB 减去每个页不用于存储数据的空间(大概是 1KB)，其他的就差不多了。
还是按照原来的一套计算流程。如果我们计算到四层 B+ 树，不难发现最多可以存几百亿行的数据。当然到第三层还是几千万行的数据(这个几是因为，主键类型是 int 还是 bigint 会有一点区别，这里的 2KW 行数据是按 bigint 来计算的)。
所以总的来说，其实就是 B+ 树的存储高度推荐是 3 层，不推荐层级更高，因为会影响查询性能
详细计算
B+ 树存储千万级的数据也只需要 3-4 层就行，所以才说它的查询效率很高。
至于为什么只用 3-4 层呢，解释一下：
其实这个和我们行数据占用空间的大小也是有关系的。假设一行数据占用 1KB 的空间，也就是说一个页可以存储 16 行数据，一个叶子节点存储 16 行数据。
非叶子节点存储的是主键值和指向下一个节点的指针：
- 一般主键值使用 int 也就够了，占用 4 个字节
- 指针占用 6 个字节（可以看看 mach_read_from_4 / mach_read_from_6 这个在 MySQL 源码中经常出现，大多数的都是 6 个字节，比如 trx_id row_id）
这里有一个比较合理的解释是 MySQL 说的指针不是真实的物理内存的地址指针（32 位 4 字节，64 位 8 字节），而是用来定位数据的指针，也就是 page_no 这个指针占用 4 个字节，如果加上详细的数据位置也就是 offset 才会是 6 个字节。这个玩意只是逻辑指针，不是直接指向虚拟地址的物理指针。
所以一个节点大概就占用 10 个字节，当然如果主键是 bigint 那就是 8 + 6 = 14 个字节。
计算结果
稍稍计算一下的话：
- int 类型：1600 个，3 层：1600 * 1600 * 16 = 4000w
- bigint 类型：1170 个，3 层：1170 * 1170 * 16 = 2000w
其中 1600 = 16 KB / 10 B
实际上物理存储和我们画的图的逻辑存储不是一个样子的，不是每个节点都是分开的，其实非叶子节点都是占用的一个页空间挤在一起，只是 offset 不一样，可能连 page_no 都是一样的。说实话 page_no 其实也是偏移量 16KB。