索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。

索引常见模型

哈希表

哈希表是一种以键值对存储的数据结构，只要输入key，就可以根据key找到对应的vaule。不可避免的是会存在hash冲突，处理这种情况方法是拉出一个链表。（类比Java中HashMap结构）。

优点：

• 查找速度快，新增速度也快。

缺点：

• 因为不是有序的，如果需要范围查询，速度是很慢的。

哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。

有序数组

有序数组查询时，可以使用二分法进行搜索，时间复杂度是O(log(N))，并且有序数据还支持范围查询。但是需要插入的时候，就需要进行数据挪动（因为要保证顺序），成本是非常高的。

因此，有序数组索引只适用于静态存储引擎。

搜索树

二叉树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))。

当然为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

二叉树的主要缺点是：当数据量很大的时候，树高会非常高，假如树高为20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。

InnoDB 的索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB使用的是B+树索引模型，所以数据都是存储在B+树中的。

每一个索引在InnoDB中对应一颗B+树。

从上图来看，索引类型分为：主键索引和非主键索引。

主键索引在InnoDB中也成为聚簇索引（clustered index），非主键索引在InnoDB中成为二级索引（secondary index）。

基于主键索引和非主键索引搜索的区别：

• 基于主键索引查询只需要搜索对应的这颗B+树。

• 基于非主键索引首先先查到对应值的ID（假设ID为主键），再到ID索引树中搜索一次，这个过程称为回表。

索引的维护

页分裂

B+ 树为了维护索引的有序性，在插入新值的时候需要做必要的维护，如果插入的数据需要在页的中间，那么就需要进行数据的挪动，空出位置，如果插入的页刚好满了，就会触发页分裂，页分裂除了会影响性能，而且会使整体空间利用率降低50%（因为之前一个页，分裂成了两个）。

当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

基于业务字段做主键，往往不能保证插入的有序性，更容易造成页分裂，基于自增ID做主键，每插入一条记录都是追加操作，一般不会触发叶子结点分裂。由于每个非主键索引叶子结点都是主键的值，如果用整型做主键，只需要4个字节，如果是长整型，则是8个字节。

显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。