Mysql 索引

InnoDB 索引支持 B+ 树索引，全文索引，哈希索引。对于哈希索引是 InnoDB 存储引擎自动生成的，不能人为生成一张表的哈希索引。

1 数据结构

1.1 二分查找法

对于有序的数据，通过不断折半查找，找到需要的数据。

1.2 二叉查找树

在二叉查找树中，左子树的值总是小于根的值，右子树的值总是大于根的值，通过树的中序遍历可以输出值的排序结果。

当二叉查找树退化成链表时，查找效率就会变低。

1.3 平衡二叉树

平衡二叉树是在二叉树的基础上，且满足 任何节点的两个子树之间的高度差小于等于1，避免树退化为链表的问题。

为了满足平衡二叉树的条件，在插入、更新、删除的时候都需要对树进行平衡的操作。

1.4 B+ 树

在 B+ 树中，所有的记录节点都是按照键值大小的顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。

image-20210722214942206

从头到尾遍历叶子节点即可得到所有值的排序结果。

2 B+ 树索引

2.1 聚集索引

按照每张表的主键构造的一颗B+树，同时叶子节点存放的是整张表的行记录数据。

2.2 非聚集索引

非聚集索引的叶子节点不包含行记录的全部数据，只包含键值和一个指向对应行数据的聚集索引键。

所以对于非聚集索引的查找，首先要遍历非聚集索引树获得主键值，再遍历聚集索引树找到数据。

2.3 联合索引

对表上的多个列进行索引，在第一个列值确定的情况下，对索引上的第二个列进行了排序。

如对联合索引 (a,b)

select * from table where a = 1 order by b

根据索引可以直接返回排序后的数据，无需进行额外的排序操作。

2.4 覆盖索引

在索引中包含了要查询的数据，无需再查一次聚集索引。 且覆盖索引不包含整行记录的所有信息，即大小远小于聚集索引，可以减少IO操作。