MySQL索引常见的模型及优缺点总结

什么是索引？索引又是用来干什么的？

一句话概括就是：索引就是为了调高数据的查询效率

就像书的目录一样，如果你想找到某个知识点，通常我们都是翻看书的目录。同样，索引其实就是数据库表的“目录”。

实现索引的数据结构有很多，最常见的也是比较简单的数据结构有哈希表，有序数组和搜索树。

哈希表是一种以键-值（key-value）形式存储数据的结构，我们只需要输入查找的键key，就可以得到对应的值value。哈希的思路是，把值放在数组里，用一个哈希函数把key换成一个确定的位置，然后把value放在数组的这个位置。

但是会有一种情况，就是多个不同的key有可能通过哈希函数的换算得到相同的位置，解决这种情况就是在这个位置拉出一个链表。

假如我们有一张用户表，用户昵称（nickname）字段使用的是哈希索引，我们需要根据昵称查询用户信息，这时哈希索引的示意图如下所示：

哈希表

示意图中，user3和user4根据nickname字段算出来的位置都是4，所以在4位置用了一个链表表示，当我们在查询的时候，比如我们根据nickname4查询，查询步骤就是：先使用哈希函数计算nickname3得到4，然后遍历链表直到找到user4。

优点：因为哈希索引是根据索引字段计算位置，所以它的插入和根据key的查找会很快。

缺点：因为哈希索引是计算位置，而这个位置不一定是递增的，所以使用哈希索引做范围查询速度会很慢。如果要根据范围查找数据，就必须全部扫描一遍索引才能找到。

适合场景：哈希表适用于等值查询的场景，比如Redis或者其他的NoSQL数据库。

还是上面的例子，如果是使用有序数组索引的话，示意图如下：

有序数组

这个数组是根据nickname递增顺序保存的，如果我们要查nickname2对应的用户信息，用二分查找就可以很快找到对应的结果，时间复杂度为O(log(N))。

当然这个数据结构也是支持范围查询的，如果我们想要查到[nicknameX,nicknameY]这个区间的用户信息，我们只需要根据二分查找找到第一个nicknameX，然后向右遍历数组，找到找到最后一个nicknameY的用户即可。

优点：有序数组因为存入的数据已经是排好序的，所以根据等值查到和范围查到都比较快。

缺点：如果我们需要往数组中间插入一个值或者删除中间的某个值，那就需要挪动这个值所在位置后面的所有元素，成本比较高。

适合场景：有序数组适用于静态存储引擎，存储不会再修改的数据，比如某个城市过去的人口数。

还是上面的例子，如果是二叉搜索树的话，示意图如下：

二叉搜索树

二叉树特点：每个节点的左儿子小于父节点，父节点小于右儿子。如果我们要查user2的话，跟着上图我们的查询路径就是：userA -> userB -> userD -> user2。时间复杂度为O(log(N))。

优点：查询效率高

缺点：因为索引不止存在于内存中，也要写到磁盘里。如果一个二叉树高度为20，我们查询某个用户信息就要访问20次磁盘，这个效率是非常低的。

适用场景：二叉树适用于表数据比较少的引擎。

为了减少树的高度，也就是减少对磁盘的访问，数据库索引就不能用二叉树。那么既然有二叉数，那就有N叉树，这里的N取决于数据块的大小。

在MySQL中，索引是在存储引擎层实现的，不同存储引擎的索引使用的数据结构可能都不一样。InnoDB的索引使用的数据结构为B+树。

在InnoDB中，表都是根据主键顺序以索引的i形式存放的，这种存储方式的表称为索引组织表。每一个索引在InndDB中都对应一棵B+树。

假如我们有下面一张表：

create table T(
   id int primary key, 
   k int not null, 
   index (k)
)engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下：

B+树

从图中可以看出，根据叶子节点的数据，索引类型分为主键索引和非主键索引。

主键索引和非主键索引的区别：

主键索引的叶子节点存的是整行数据，在InnoDB里，主键索引也叫做聚簇索引；非主键索引的叶子节点存的内容是主键的值，在InnoDB里，非主键索引也叫做二级索引。
如果根据主键查询，则只需要查找id索引树即可；如果根据非主键索引查找（查找的数据不只有主键），则需要查找k索引树找到对应的主键，然后根据主键到id索引在查找一次。这个过程叫回表。

结束！