【MySQL】B+ 树索引

一、索引是什么 ？ 为什么需要索引 ？

索引就是目录，目录就是索引。

索引从 InnoDB 存储引擎数据存储结构上来看，就是为各个页建立的目录。保证我们在查询时，可以通过二分法快速定位到页，再在页内通过二分法快速定位到组，再在组内进行查询。

背景知识：页分裂表示进行创建新页存放我们插入的数据的过程要求创建完的这些页中的记录具有主键值的递增关系。

二、为页建立的目录应该什么样子 —— 如何设计

为页建立目录，目录的目录项为 ：

• 用户记录中最小的主键值
• 页号

1. 为页建立的目录也被封装成页了 —— 成了索引

因为 InnoDB 以页为单位，所以我们上面说的为页建立的目录也需要被放在一个页里。这个页就是目录项页，目录项页中的记录就是把目录项封装为记录，即目录页中的记录为 （页号， 用户记录中最小的主键值）

目录项记录和我们的数据页中的记录具有如下区别：

1. 标志记录类型的值不同 —— 目录项记录的 record_type = 1, 普通用户记录为 0
2. 记录的内容不同

2. 有了目录项页后的查找过程

1. 在目录页中通过二分查找定位到所在的页
2. 在所在页的页目录中通过二分查找进行查找

3. 目录项页也是个页，其存不下那么多目录项了咋办

新增新的目录项页就行了，然后再为这些目录项页抽象出一个目录项页的目录页 。 —— … 太厉害了 ~

然后我们就可以发现这个结构变成树了 —— 这个树就是 B+ 树， 就是我们 InnoDB 中的索引实现方式

然后我们再去想，我们的用户数据记录都在树的叶子节点（就是最下层），其他的目录的内容都在非叶子节点上 —— 这就是 B+ 树的特点

三、索引类型

1. 聚簇索引

我们上文说的 B+ 树就是个聚簇索引，它具有两个特点：

1. 使用记录主键值进行排序
2. B+ 树的叶子节点就是用户记录

InnoDB 会自动为我们创建聚簇索引，而且这个聚簇索引就是 InnoDB 的数据存储结构，嘿嘿嘿，一句非常好的话 —— 索引即数据，数据即索引

2. 二级索引

我们不可能一直通过主键进行查询，有时候也需要通过一些非主键的列进行查找。这时的索引的策略是对这个非主键列建立一颗 B+ 树（就是按照这个列进行排序建立二叉树），但是其 叶子节点 存放的值只有 ： 索引列的值 + 主键值 + 页号 。 我们通过这个列得到要查找的记录的主键值，然后再拿着主键值进行回表 （就是再去聚簇索引那里查一遍），所以其需要遍历两棵 B+ 树，所以才叫 “二” 级索引鸭 ~~

注：为啥不全存上，为啥只存主键 id ，要是全存上不久不用回表了嘛 ？ —— 空间 ！！ 空间 ！！！

3. 联合索引

以多个列作为排序规则建立索引，本质上也是个二级索引

注： 排序方式为先按照第一个列，再按第二个列 …

四、用索引

1. 索引的缺点

占用空间 + 索引维护浪费时间

2. 什么情况下才使用到索引

背景： 创建索引 ——

1. 在 创建表 时创建

key idx_rowname1_rowname2....(rowname1, rowname2, ....)

2. 创建表之后，选择表创建

alter table table_name add key/index row_name

（1）情况一： 全值匹配

搜索条件的列和索引列一致，即我们建立了联合索引，然后我们的搜索条件刚刚好就是这个联合索引建立的列

注： 顺序没有影响， MySQL 的查询优化器会帮我们调整到最优顺序

（2）情况二： 匹配左面的列

联合索引中的列可以不全用到，只包含左面（一个或者多个列）就行 （理解联合索引的排序方式很重要 ！！！）

联合索引的后面的列可以没有，可以不用，下面举个例子

用户记录为 ：(row1, row2, row3, row4)，假如一个联合索引是这样的 row2_row3_row4

这种情况都可以用到索引 ： .... where row2 = value1 and row3=value2 and row1=value3

这种情况下我们可以用到 row2_row3 的索引，然后再筛选出 row1

这种情况就用不到索引了 ： .... where row3 = value 或者 ... where row4 = value 等等

（3）匹配列前缀原则

根据字符集的比较规则，对于字符串类型的索引，可以只匹配前缀

where row like 'Prefix%'

但是注意： 不可以匹配中缀，或者后缀，只能是前缀，这是由字符集的排序规则决定的

如果需要比较后缀，可以把字符串逆序存储 …

（4）情况四：匹配范围

因为我们的记录是按照索引的大小用链表连着的，所以可以取出范围，但是对多个索引列同时进行范围查找的话，只能用到最左面的那个索引列。理由很清晰：

只有当前索引值相同，才按下一个索引排序，而这个是个范围，对这个范围内的第一个索引下面的查找的那个索引列的值不一定啥样子，所以只能用到最左面的第一个索引列

（5）其他情况

这都是根据索引构造的原理决定的，还有如下情况也能用到索引：

1. 精确匹配 + 范围匹配
2. 排序情况
3. 分组

补充： 什么情况下排序不能用到索引

排序列不在索引里、按多个列进行排序的列不包含在一个联合索引里、排序列包含了复杂的表达式

3. 到底要不要回表

我们平时进行非范围查询， 这时候我们只需要拿着在 二级索引 中找到的 id，回表一次 聚簇索引就 ok 了

但是但我们进行范围查询时，我们是拿着一堆 id ， 等着要去回表， 这些 id 不挨着，做的是 随机 io ，非常损耗性能。 —— 这种情况宁可全表扫描，也不要回表一堆次聚簇索引。

当然是否回表是 MySQL 优化器决定的，其会根据回表次数自己判断是要回表还是全表扫描。

但是我们可以通过 覆盖索引 的方式彻底摆脱回表。所以我们尽量不要 select *

五、什么样子的列适合建立索引

1. 搜索、排序、分组的列
2. 不咋重复的列 —— 比如具有唯一值的列
3. 数据类型占用空间小的列 —— 比如数字类型
4. 对字符串值的前缀建立索引

六、注意事项

1. 不要在查询中对索引列瞎做运算，让索引列单独存在，不然不要索引列，而是挨个运算
2. 使用自增主键，降低维护聚簇索引的成本
3. 不要瞎建立一堆冗余索引，用一个联合索引就能解决