深入理解Mysql - 索引原理详解

一、什么是数据库索引

数据库索引，是数据库管理系统（DBMS）中一个排序的数据结构，以协助快速查询、更新数据库表中数据。

二、索引存储模型的推演

1，有序数组

过程：按照顺序由小往大或反向查询。

缺点：在开始或中间位置插入时，需要挪动后面全部的节点下标。新增、删除、修改效率低。

2，二叉查找树（BST Binary Search Tree）

特点：左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以后，就是一个有序的线性表。

过程：需要查询的值与根节点比较，大于根节点的在右子树继续比较，小于根节点的在左子树上继续查询，等于则直接结束查询，获取节点中的磁盘地址进行数据读取。

相比有序数组：查询效率更高，新增修改效率提高。

缺点：受该二叉查找树的深度影响，最坏情况下的时间复杂度可退化为O(n)，即该二叉树都只有一个子树的时候。

3，平衡二叉树（AVL Tree）（左旋、右旋）

特点：左右子树深度差绝对值不能超过1的二叉查找树。 左 ->左型 ：右旋；右->右型:左旋；

过程：同查找二叉树

相比二叉查找树：树的左右子树的深度相差小，查询相对比较稳定。

缺点：以二叉树作为数据索引的话，假设InnoDB的页大小16kb中存放一个节点（该节点中需要存放索引列的值，以及该记录在磁盘中的地址，以及左右子树的磁盘物理地址），那么如果在查询的过程中进行了多次的比较，那么将出现多次与硬盘的io操作。当数据量较大时则io耗时将会很高。

4，多路平衡查找树（B Tree, Balanced Tree）（分裂、合并）

特点：跟AVL 树一样，B 树在枝节点和叶子节点存储键值、数据地址、节点引用。分叉数（上图，路数N=3）永远比关键字（字段值）数多1（类似于绳子中间剪断几次一样）。一个页上面可以存放多个节点信息，减少了AVL树一个页存放少，同样的数据需要多次磁盘IO读取。

过程：比如我们要在这张表里面查找15。因为15 小于17，走左边。因为15 大于12，走右边。在磁盘块7 里面就找到了15，只用了3 次IO。

缺点：当出现新增数据，或者删除数据，或者更新索引列数据时，将会出现页的分裂与合并。也得分裂与合并将最终还是需要通过IO进行多次和磁盘IO交互。

5，B+树（加强版多路平衡查找树）

特点：1，它的关键字的数量是跟路数相等的。2，B+Tree 的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。

过程：见上图，小于根节点的第一位的不存在，然后大于等于节点中第一位，小于第二位的，顺着节点中第一位的指针往下走。大于等于节点中第二位，小于第三位的顺着第二位的指针往下走，大于等于页中第三位的顺着第三位的指针往下走。直到走到叶子节点上获取该记录的磁盘地址。

优势：1，由于上面节点中不存储节点的磁盘物理地址，每个页上面可以存放更多的数据。路数更多，树的层级越低；2，扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵B+Tree 拿到所有的数据）。3，B+Tree 的磁盘读写能力相对于B Tree 来说更强（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）4，排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）。5，效率更加稳定（B+Tree 永远是在叶子节点拿到数据，所以IO 次数是稳定的）。

三、mysql 不同存储引擎的索引差异

InnoDB

innoDB存储引擎下，一个表除了 tableName.frm 表结构文件外，还有一个tableName.ibd文件。在InnoDB 里面，它是以主键为索引来组织数据的存储的，所以索引文件和数据文
件是同一个文件，都在.ibd 文件里面。主键索引的叶子节点上，它直接存储了我们的数据。

聚集索引（聚簇索引）：索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。

非聚集索引（辅助索引，二级索引）：如果有主键索引，那么主键索引就是聚集索引。其他的索引统一叫做“二级索引”或者辅助索引。

聚集索引的产生：如果我们定义了主键(PRIMARY KEY)，那么InnoDB 会选择主键作为聚集索引，如果没有显式定义主键，则InnoDB 会选择第一个不包含有NULL 值的唯一索引
作为主键索引。如果也没有这样的唯一索引，则InnoDB 会选择内置6 字节长的ROWID 作为隐藏的聚集索引，它会随着行记录的写入而主键递增。

在InnoDB存储引擎下，如果说一张表创建了主键索引，那么这个主键索引就是聚集索引，决定数据行的物理存储顺序。

二级索引存储的是辅助索引的键值，例如在name 上建立索引，节点上存的是name的值。而二级索引的叶子节点存的是这条记录对应的主键的值。所以，二级索引检索数据的流程是这样的：当我们用name 索引查询一条记录， 它会在二级索引的叶子节点找到name=Q，拿到主键值，也就是id=1，然后再到主键索引的叶子节点拿到数据。

MyISAM

在MyISAM 里面，一个表除了 tableName.frm 表结构文件外,另外有两个文件：一个是.MYD 文件，D 代表Data，是MyISAM 的数据文件，存放数据记录。一个是.MYI 文件，I代表Index，是MyISAM 的索引文件，存放索引。

MyISAM 的B+Tree 里面，叶子节点存储的是数据文件对应的磁盘地址。所以从索引文件.MYI 中找到键值后，会到数据文件.MYD 中获取相应的数据记录。

在MyISAM 里面，辅助索引也在这个.MYI 文件里面。辅助索引跟主键索引存储和检索数据的方式是没有任何区别的，一样是在索引文件里面找到磁盘地址，然后到数据文件里面获取数据。

四、索引的创建与使用

离散度

如果列的重复值越多，离散度就越低，重复值越少，离散度就越高。不建议大家在离散度低的字段上建立索引。

联合索引最左匹配

联合索引在B+Tree 中是复合的数据结构，它是按照从左到右的顺序来建立搜索树的（name 在左边，phone 在右边）。从这张图可以看出来，name 是有序的，phone 是无序的。当name 相等的时候，phone 才是有序的。这个时候我们使用where name= 'Mic' and phone = '180xx '去查询数据的时候，B+Tree 会优先比较name 来确定下一步应该搜索的方向，往左还是往右。如果name相同的时候再比较phone。但是如果查询条件没有name，就不知道第一步应该查哪个节点，因为建立搜索树的时候name 是第一个比较因子，所以用不到索引。

所以，我们在建立联合索引的时候，一定要把最常用的列放在最左边。

举例：当创建联合索引（a,b,c）时。相当于创建三个索引：index(a)、index(a,b)、index(a,b,c)

使用 where a=xx,b=xx,c=xx 命中索引 abc；使用 where a=xx ,c=xx 命中索引 a；使用 where b=xx,c=xx 无法命中索引。

回表：非主键索引，我们先通过索引找到主键索引的键值，再通过主键值查出索引里面没有的数据，它比基于主键索引的查询多扫描了一棵索引树，这个过程就叫回表。

覆盖索引：在辅助索引里面，不管是单列索引还是联合索引，如果select 的数据列只用从索引中就能够取得，不必从数据区中读取，这时候使用的索引就叫做覆盖索引，这样就避免
了回表。

创建索引的原则：

1. 在用于where 判断order 排序和join 的（on）字段上创建索引
2. 索引的个数不要过多（浪费空间，更新变慢）
3. 区分度低的字段，例如性别，不要建索引（离散度太低，导致扫描行数过多）
4. 频繁更新的值，不要作为主键或者索引（页分裂）
5. 随机无序的值，不建议作为主键索引，例如身份证、UUID（无序，分裂）
6. 创建复合索引，而不是修改单列索引

索引失效的情况：

1. 索引列上使用函数（replace\SUBSTR\CONCAT\sum count avg）、表达式计算（+ - * /）：SELECT * FROM `t2` where id+1 = 4;
2. 字符串不加引号，出现隐式转换。SELECT * FROM dept WHERE dname = 101
3. like 条件中前面带%
4. 负向查询，NOT LIKE失效 。!= （<>）和NOT IN 在某些情况下可以。

redis内部实现原理、