为什么会出现索引
索引的出现是为了提高数据查询的效率，就像书的目录一样
索引的常见模型
哈希表
哈希表是一种以键-值(key-value)存储数据的结构，我们只需要输入待查找的键即key，就可以找到对应的value值。哈希的思路很简单，把值放到数组里面，用一个哈希函数把key换算成一个确定的位置，然后把value值放入数组的这个位置。但是，多个key经过哈希函数计算会出现同一个值的情况，处理这种情况的方法其中一种是拉出一个链表，跟Java中的ArrayList集合有点类似。
图上的user_id都不是递增的，这样做的好处是增加数据的时候很快，但是缺点是不是有序的，通过哈希查询区间数据的时候，是很慢的，因为你需要把全表都扫描一遍，所以哈希表适用等值查询的场景，比如一些适用NOSQL引擎的数据库(Memcached)
有序数组
有序数组在等值查询和范围查询场景中的能力是非常优秀的，
假设图中的user_id都是不重复，那么数据在表内存储的时候都是有序的，按照身份证号进行递增排序，此时根据user_id查询对应的名字，通过二分法可以快速找到，时间复杂度为O(log(N))；而且对于范围查询也是支持的，对于查询[user_id_x,user_id_y]区间的user，通过二分法找到第一个大于id_card_x的id，然后向右遍历，找到第一个大于user_id_y的id,退出循环即可。
仅仅看查询效率的话，有序数组是最好的数据结构，但是更新数据的时候，往中间插入一个数据，需要移动的数据太多，效率很差。所以有序数组只适用于静态数据引擎，所谓静态数据，也就是不会再修改的数据。
二叉搜索树
二叉搜索树的特点是父子节点左边的值小于父子节点，右边的值大于父子节点，
如图所示，如果要查询id_card_2的值，按照顺序就是UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))。为了维持这个时间复杂度，就必须是平衡二叉树，为了这个平衡二叉树，更新的时间复杂度也是O(log(N))。那么树可以有二叉，就可以有多叉。多叉树表示一个父节点有多个子节点，子节点的大小从左到右依次是递增的。二叉树的搜索效率是最高的，但是实际上大多数数据库引擎却不用它，是因为索引不光存储在内存中,还存储在硬盘上，如果数据越来越多，则意味着二叉树的树高也就越来越大，一次查询就可能访问磁盘中很多个数据块，为了减少磁盘中数据块的访问次数，可以使用N叉树
注意
N叉树的这个N取决于数据块的大小，在Innodb模型中，一个整数字段索引的N大约是1200(MySql默认一个节点的长度为16K，一个整数（bigint）字段索引的长度为 8B,另外每个索引还跟着6B的指向其子树的指针；所以16K/14B ≈ 1170),那么树高为4的时候，可以存储1200的3次方个值，而且树根的值总是存储在内存中，那么最多需要查询三次数据块就行了。N叉树因为读写性能的优势和适配磁盘的访问模式，被广泛应用于数据库的引擎设计
Innodb索引模型
在Mysql中，索引和事务一样都是在存储引擎层实现的，所以没有统一的索引标准，即不同存储引擎的索引的工作方式是不一样的，而且即使多个存储引擎使用同一个类型的索引，那么索引的底层实现也可能是不一样的。那么Innodb的索引模型是B+树，为什么上面在说N叉树的时候，已经说了，下面专门说Innodb的索引模型