索引上（4）

索引

作用：提高数据查询的效率

常用索引模型

• 哈希表
• 有序数组
• 搜索树

哈希表
以键值对的形式存储，适合于只有等值查询的场景。
用一个哈希函数把key换算成一个确定的位置，然后把value这个位置的数组中。一个key会对应一个数组，数组中会有多个value，value并不是有序的。
查找时先通过哈希函数算出key，找到具体的数组，然后遍历数组，找到具体的位置。

有序数组
以有序数组形式存储，等值查询和范围查询场景中性能非常优秀，只适用于静态存储引擎。
仅仅看查询效率，有序数组就是最好的数据结构了，但是，在需要更新数据多的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。
所以，有序数组索引只适用于静态存储引擎，比如你要保存2017年某个城市的所有人口信息，这类不会再修改的数据。

搜索树
以类似二叉树的多叉树来实现。

• 二叉搜索树：每个节点的左儿子小于父节点，父节点又小于右儿子。
• 多叉树：每个节点有多个儿子，儿子之间的大小保证从左到右。

在MySQL中，索引是在存储引擎层实现的，所有并没有同一的索引标准，即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。

InnoDB使用了B+树索引模型，所有的数据都是存储在B+树中的。每一个索引在InnoDB里面对应一棵B+树，主键索引对应主B+树。

• 主键索引：对应主B+树，叶子节点存储的是整行数据，也称为聚簇索引
• 非主键索引：每个非主键索引对应一个B+树，叶子节点存储的是主键的值，也称为二级索引。

基于主键索引和普通索引的查询的区别？

• 如果语句是select * from T where ID = 500，主键查询方式，即只需要搜索ID这棵B+树，叶子节点中有存储整行数据；
• 如果语句是select * from T where k = 5，普通索引查询方式，则需要先搜索k索引树，得到主键ID的值为500，再到主键ID索引树搜索一次，这个过程成为回表。

回到主键索引树搜索的过程，我们称为回表。

也就是说：基于非主键索引的查询需要多扫描一颗索引树。