索引

1.索引模型

• 哈希表

使用哈希函数将key换算成一个确定的位置，对于出现碰撞的key，则在每一个索引上接一个链表。

缺点：因为key不是递增的，因此做范围查询需要全表扫描。仅适用于等值查询。

• 有序数组

在等值查询和范围查询场景中性能比较好。所有key按序保存在数组中。

缺点：插入新数据需要挪动整个数组，成本高。因此有序数组只适用于静态存储引擎，比如2017年人口信息。

• 二叉搜索树

查询效率快。

缺点：为了保证log(N)的查询复杂度，需要保证这棵搜索树是一棵平衡二叉树。但是二叉搜索树的问题在于维护起来比较麻烦。

• N叉树

因为二叉树保存的数据量比较大时，树的层数比较高，导致需要频繁访问磁盘(一层树高对应一个索引块)。因此使用N叉树可以让查询流程尽量少走磁盘，减少树高，读更少的数据块。读写性能好。

注意N叉树的N实际上等于一个页的大小除以一个索引字段的大小，因此可以通过设置数据页的大小来改变N的值。

2.InnoDB索引模型

InnoDB采用B+树存储索引节点，每一个索引字段对应一棵B+树。

索引分为主键索引和非主键索引。查询语句根据使用的索引不同，索引树搜索树次数也不同：

• 如果用到主键索引，那么直接根据主键索引值搜索主键B+树，在叶子节点拿到对应的行记录
• 如果使用非主键索引，那么会先查找该字段的B+树，在叶子节点获取到对应主键索引值之后，再根据主键索引值去主键B+树搜索行记录。【🔑回表】

3.索引维护

B+树在维护过程中，会涉及到页分裂与合并的情况。根据添加记录的主键值包含两种情况：

• 添加的主键值递增插入 ( 自增主键AUTO_INCREMENT ) ，那么只需要进行追加操作，不涉及挪动其他的记录，也不会触发叶子节点的分裂。
• 当添加的主键值是乱序的（ 业务逻辑字段作为主键 ），往B+树插入新的记录时，可能会导致叶子节点的分裂，从而需要申请新的数据页，并将数据挪动过去。

自增字段作为主键的性能分析：从性能上分析，使用自增主键在维护时开销比较小；从存储空间考虑，如果选择的主键的字段比较长，那么对于所有二级索引B+树的叶子节点来说，就需要开辟更大空间保存每一个主键索引值。

业务字段直接作为索引：①只存在一个索引字段(不需要考虑其它索引叶子节点大小的问题)②该索引必须是唯一索引——kv场景。直接将该索引设置为主键。

4.删除索引

• 为什么要删除索引

在不断的往数据库插入新的数据过程中，一旦出现页分裂情况，就会导致数据页空间存在空洞。因此重新创建索引会将所有数据重新按照索引插入，从而节省空间，使索引更加紧凑。

• 重建主键索引

一张表重建主键索引时，不仅需要重建主键的B+树，同时对于所有其它的二级索引的B+树也会重新构建，从而导致较大的开销。

5.覆盖索引

数据表中ID是主键，k是非主键索引。有两条查询语句如下：

select * from T where k between 3 and 5
select ID from T where k between 3 and 5

如果查找的是整个行记录，那么每次查询完k的B+树之后，还会查询ID的主键B+树，因此每条记录会搜索两次树。P.S最后还会查找一次K的索引树，判断k超出范围搜索结束。

覆盖索引优化：如果直接查主键ID，因为在k的索引树的叶子节点中，已经包含ID主键字段的值，所以就不需要进行回表，大大减少B+树的查询次数。

覆盖索引可以减少树的搜索次数，显著提升查询性能。覆盖索引是一种特殊的联合索引。。

💡建立联合索引使用覆盖索引：如果有一个索引字段k1，还有一个数据库字段k2，有一个高频请求需要根据k1字段查找k2字段的值。如果是普通的做法先查k1然后进行回表，总共需要查询两次；而如果是建立(k1,k2)两个字段的联合索引，那么只需要查一次二级索引的B+树就可以得到k2字段的值。

💡二级索引比主键索引更快：仅限于使用覆盖索引的情况。

6.最左前缀原则

最左前缀原则：不仅包括联合索引中最左N个索引字段；同时还包括模糊查询字符串索引最左n个字符。细节如下：

• 如果已经建立了联合索引(a,b)，那么就没有必要单独在a字段上建立索引。它们两个都可以走同一个联合索引。
• 联合索引多个字段顺序的安排：①第一原则是调整顺序后，根据上述规则可以少维护一个索引字段②根据具体业务和热点字段③字段存储空间大小。

7.索引下推

假设存在联合索引(name,age)，如果有以下SQL查询语句：

select * from tuser where name like '张%' and age=10 and ismale=1;

根据使不使用索引下推可能会存在两种情况：

• 不使用索引下推：首先会在联合索引树搜索匹配到所有姓张的叶子节点(age因为遇到范围查询不会匹配),然后对于剩余没有匹配的字段，则会根据叶子节点匹配的主键索引去主键索引树拿到每个数据行，然后再对比非索引字段是否符合条件。因此每个非索引字段的条件判断都需要进行一次回表，并交给server层进行判断。

• 索引下推：联合索引树中已经存在age字段的值，因此对age的WHERE条件判断直接交给InnoDB存储引擎进行，不需要回表。对于索引B+树不存在的字段，才会通过回表拿到行数据再进行条件判断。

  对于所有索引字段的条件判断，无论是否命中都会使用索引下推在存储引擎完成。

8.联合主键

联合字段(a,b)作为主键，同时在c字段上建立索引，则在c的索引B+树木中，叶子节点需要同时保存联合主键字段a和b的值。如果此时又建立了联合索引(c,b)，那么索引树叶子节点只需要保存a的值(b已经在索引字段存在)。无论是联合索引还是联合主键本质上都是按照最左原则对字段进行排序。

那么考虑如下SQL语句，c索引叶子节点会根据最左前缀原则保存联合主键的值，因此下列语句的c,a索引不需要另外添加创建，直接走c索引。

select * from geek where c=N order by a limit 1;

而对于如下语句，在c字段没有重复的情况下，不需要建立(c,b)索引，直接走c索引得到的最终结果准确。如果重复值比较多则需要建立联合索引。

select * from geek where c=N order by a limit 1;