索引是什么？ 索引就是为了提高查询效率，类似于书的目录的东西。
索引的常见模型
索引的实现方式有很多种，这里主要说明三种：哈希表、有序数组和搜索树
哈希表
哈希表就是一种 key-value 存储数据的结构，通过寻找key，就可以取出对应的 value。 哈希的实现方式，就是把 key 通过一个 哈希函数 将其映射到数组的某个确定的位置，然后将 value 放入这个位置。
哈希表的优势就是单值查询速度很快，并且插入速度也很快。但是缺点就是，因为存储不是有序的，所以哈希索引做区间查询的速度很慢。
总结：哈希表结构只适用于等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。
有序数组
有序数组则在等值查询和区间查询都表现优秀。
如果要查询某个key，因为数组是有序的，通过 二分法很快就能查到，复杂度为 O(log(N))
对于区间查询，只需要先通过二分法查询左值，然后向右遍历找到右值。
但是有序数组的插入效率很低，如果往中间插入一个数据，就需要后面所有的记录跟着挪动。
总结：有序数组等值查询和区间查询效率都很高，但是插入效率低，只适用于静态存储引擎。
搜索树
搜索二叉树是非常经典的搜索树，其特点是：所有左子节点小于父节点的值，所有右节点大于父节点的值。查询的时间复杂度为 O(log(N))。
当然为了维持 O(log(N)) 的查询复杂度，就必须保持这棵树是平衡二叉树，所以其更新复杂度也是 O(log(N))。
然而，实际上，二叉搜索树并不适用于索引，这是因为平衡二叉树只有两个子节点，其层高会比较高。而索引不止存在内存中，还要写到磁盘上。而过高的层高会导致频繁访问磁盘，导致查询效率下降。
为了让其尽量少访问磁盘，就必须让查询过程访问尽量少的数据块。所以，索引结构一般使用的是N叉树，这里的N取决于数据块大小。
InnoDB 的索引模型
在 InnoDB 中，表都是根据主键顺序以索引的形式存放的。另外，InnoDB 使用的是 B+树的索引模型，所以数据都是存储在 B+ 树中的。
每一个索引在 InnoDB 中对应一棵 B+ 树。
索引分为 主键索引 和 非主键索引。
主键索引（聚簇索引）的叶子节点存的是整行数据。
非主键索引（二级索引）的叶子节点存的是主键的值。
那么，基于主键索引和非主键索引的查询有什么区别呢？
- 如果是根据主键查询，那么只需要搜索主键对应的 B+ 树
- 如果是根据非主键查询，那么就必须要先查询 非主键 对应的 B+ 树，取出对应的主键的值，然后再去 主键索引 查询整行值。这个过程被称回表。
也就是说，基于非主键索引的查询，会多一次搜索 B+ 树。 所以，在实际应用中，应当尽量使用主键查询。
