学习笔记是学习了 极客时间 - 《MySQL实战45讲》整理的笔记。
在 MySQL 中，索引是在存储引擎层实现的，所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。由于目前主流的引擎是 InnoDB 存储引擎,因此我只记录InnoDB的索引擎模型。
B+ Tree
首先我们需要了解一下B+树
定义
- 每个结点最多有m-1个关键字。
- 根结点最少可以只有1个关键字。
- 非根结点至少有Math.ceil(m/2)-1个关键字。（向上去值）
- 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
- 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
- B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。
- B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。
- m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。
- 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
- 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
主键索引查找
如图所示:
我们可以看到这个就是一个典型的B+索引树。假设我们去搜索10这个数字，我们必须从根节点出发通过两段的查找，查找到所在的叶子节点，也就是保存数据的节点中，找到该值。
同时我们可以看到B+树的叶子节点的数据都是从大到小排列的，当我们查找一组数据大于10的数据时，我们会首先从根节点搜索，找到10的叶子节点，然后我们不必再从根节点去搜索大于10的叶子节点了，因为在每个叶子节点均有指向下一个叶子节点的指针，在这里也就是Q 。我们直接可以使用Q来进行大于10的数据的查找。
普通索引查找
基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小,从性能和存储空间方面考量，自增主键往往是更合理的选择。
索引的搜索过程
之前的普通索引查找，我们经历了一次回表（回到主键索引树搜索的过程，我们称为回表）。
但是当我们执行
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 *查询。
覆盖索引
如果执行的语句是 select ID from T where k between 3 and 5，这时只需要查 ID 的
值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是
说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。
由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用
的性能优化手段。
最左前缀原则
B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。
为了直观地说明这个概念，我们用（name，age）这个联合索引来分析。索引项是按照索引定义里面出现的字段顺序排序的。
可以看到，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。
联合索引建立技巧
如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。比如 刚刚的 姓名和年龄的联合索引，有了这个索引，其实我们不需要再去建立一个 name索引了。
索引下推
上一段我们说到满足最左前缀原则的时候，最左前缀可以用于在索引中定位记录。但是如果不符合呢？
假如我们执行这条语句
select * from tuser where name like '张 %' and age=10
在MySQL 5.6 之后引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
小结
了解Mysql基础的索引知识，更易于我们在业务上对数据表的优化。
