索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。
常见的索引模型
- 哈希表：哈希表是一种以键-值（key-value）存储数据的结构。通过待查找的Key值，就可以找到其对应的Value。哈希表这种结构适用于等值查询的场景。如果要进行区间的查询，就必须全部扫描一遍。
- 有序数组:有序数组在等值查询和范围查询场景中的性能很好。但是更新和插入性能比较差，往中间插入一条记录就必须挪动后面所有的记录，成本很高。有序数组只适用于静态存储引擎。
-
二叉搜索树 :每个节点的左儿子小于父节点，父节点又小于右儿子。二叉树的搜索效率是最高的，但是大多数数据库存储都不使用二叉树。因为 索引不止存在内存中，还要写入硬盘。硬盘寻址时间较长。
为了让一个查询尽可能少的读磁盘，就必须让查询过程访问尽量少的 数据块，我们不应该使用二叉树，应该使用“N”叉树。InnoDB 的整数字段为例，N为1200，树高为4的时候，可以存1200的3次方个值。大约17亿。10亿行整数字段的索引，查找一个值最多需要访问3次磁盘。
其他的索引模型：跳表，LSM树等。
InnoDB的索引模型
InnoDB使用了B+树索引模型，所以数据都是存储在B+树中的。每个索引在InnoDB里面对应一棵B+树。
索引分类
- 根据叶子节点的内容，索引类型分为主键索引和非主键索引。
- 主键索引 主键索引的叶子节点存的是整行的数据，在InnoDB中，主键索引也被称为聚簇索引。
-
非主键索引 非主键索引的叶子节点内容是主键的值。也被称为二级索引。基于非主键索引的查询需要多扫描一颗索引树。先搜索k索引树，得到主键，再按照主键搜索一次，这个过程叫做回表。
区别：主键索引只要搜索ID这个B+树就可以拿到数据，普通索引先搜索索引拿到主键值，再到主键索引树搜索一次（回表）。
删除索引的性能问题：新建主键索引，会同时去修改普通索引对应的主键索引，性能消耗比较大。删除普通索引影响不大。 - 覆盖索引:非主键索引已经覆盖了查询的需求，不需要回表。覆盖索引可以减少树搜索的次数，显著提升性能。
- 最左前缀原则:B+树这种索引结构，可以利用索引的“最左前缀”，来定位记录。
在建立联合索引的时候，如何安排索引内的字段顺序？可以根据索引的复用能力，因为可以支持最左前缀，所以当有了（a,b）联合索引后，一般就不需要再a上建立索引了。第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往是优先考虑采用的。如果说既有基于a的查询，又有基于b的查询，这时是无法使用（a,b）索引， 这时候就不得不维护另一个索引了，这时候需要考虑的就是空间问题。
- 索引下推:可以在索引遍历的过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表的次数。
