实现索引的的方式有很多，可以用于提高读写效率的数据结构也很多，常见的数据结构有哈希表、有序数组、搜索树，在 MySQL 索引是为了提高查询效率的，而 MySQL 中的索引又分为主键索引和二级索引，了解了 MySQL 的索引模型之后，可以帮助对索引的理解，这篇文章就来学习一下 MySQL 的索引模型。
1.笔记图
2.索引的常见模型
- 哈希表：
- 哈希表是一种以键-值（key-value）存储数据的结构，把值放在数组里，用一个哈希函数把 key 转化为整数，然后取模计算得到一个索引位置，然后把 value 放在数组的这个位置
- 多个 key 值经过哈希函数的换算，会出现同一个值的情况，这总情况称为哈希冲突，处理这种情况通常可以拉出一个链表
- 哈希表这种结构适用于只有等值查询的场景，因为不是有序的，所以哈希索引做区间查询的速度是很慢的
- 有序数组：
- 如果仅仅看查询效率，有序数组就是最好的数据结构了
- 但是在需要更新数据的时候，往中间插入一个记录就必须得挪动后面所有的记录，成本太高
- 搜索树：
- 二叉搜索树的父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值
- 当然为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))
- 为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块，要使用 N 叉树
3.InnoDB 的索引模型
- 在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表
- InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的
- 每一个索引在 InnoDB 里面对应一棵 B+ 树
- 页分裂：
- 如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录
- 如果新插入的 ID 值为 400，需要逻辑上挪动后面的数据，空出位置
- 如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去，这个过程称为页分裂，性能会受到影响
- 页分裂操作还影响数据页的利用率，原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%
- 页合并：当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并
4.主键索引和普通索引查询的区别
- 主键查询方式，则只需要搜索 ID 这棵 B+ 树
select * from T where ID=500
- 普通索引查询方式，需要先搜索 k 索引树，得到 ID 的值 500，再到 ID 索引树搜索一次，这个过程称为回表
select * from T where k=5
- 非主键索引的查询需要多扫描一棵索引树，在应用中应该尽量使用主键查询
5.如何选择主键字段
- 每个非主键索引的叶子节点上都是主键的值
- 主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小
- 从性能和存储空间方面考量，自增主键往往是更合理的选择
6.笔记图
7.回表过程
select * from T where k between 3 and 5
- 在 k 索引树上找到 k=3 的记录，取得 ID = 300
- 再到 ID 索引树查到 ID=300 对应的 R3
- 在 k 索引树取下一个值 k=5，取得 ID=500
- 再回到 ID 索引树查到 ID=500 对应的 R4
- 在 k 索引树取下一个值 k=6，不满足条件，循环结束
- 这个过程中，回到主键索引树搜索的过程称为回表
- 覆盖索引：
- 如果执行的语句是 select ID from T where k between 3 and 5，只需要查 ID 的值，而 ID 的值已经在 k 索引树上，因此可以直接提供查询结果，不需要回表，索引 k 已经 覆盖了 查询需求，称为覆盖索引
- 由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段
- 索引下推：
- select * from tuser where name like ‘张%’ and age=10 and ismale=1
- MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数
8.最左前缀原则
- B+ 树这种索引结构，可以利用索引的 最左前缀，来定位记录
- 举例：
- 用（name，age）这个联合索引来分析
- 索引项是按照索引定义里面出现的字段顺序排序的
- 当你的逻辑需求是查到所有名字是 张三 的人时，可以快速定位到 ID4，然后向后遍历得到所有需要的结果
- 如果要查的是名字第一个字是 张 的人，SQL 语句条件是 where name like ‘张 %’，查找到第一个符合的记录是 ID3，然后向后遍历，直到不满足条件为止
- 只要满足最左前缀，就可以利用索引来加速检索，可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符
