索引是如何工作的

索引的类型

对于数据库来说索引就是为了尽可能高效的查询到需要的数据，不用遍历整个数据库找到相应数据，那么如何实现这一点呢？主要实现方式有有序数组、哈希表、搜索树。

有序数组很好理解，就是让数据按某些字段顺序依次排列，这样当需要查询数据时，便可以通过二分搜索在 O(logn) 的时间复杂度内找到相应的数据，同时如果需要按顺序查询且要求的顺序恰好是索引的顺序时，就不需要进行排序了，如果要对排序的键进行范围查询，那也可以很快的查询到指定的范围。但是这种方式有一种致命的缺点就是当需要在中间插入或者删除数据时，该数据后面的所有数据都需要移动，这可是 O(n) 的时间复杂度，插入删除都是很常用的功能，所以基本没有数据库使用这种索引。

哈希表的原理也很好理解，哈希表是一个 Key-Value 的数据结构，通过对索引键计算哈希函数得到一个哈希值整数，这个数就是数据在数组中的位置，当然有可能出现多个不同的键计算得到相同的哈希值，这也就是哈希冲突，具体的解决冲突方法有开放定址法、拉链法、再哈希法，具体这里不过多介绍。

哈希索引的优势就是可以在 O(1) 的时间复杂度找到所需数据，但是这种方法也有缺点，那就是无法进行范围查询，因为在通过哈希函数计算之后再数组中的数据都是乱序的，所以一般只有一些作为缓存的 NoSQL 使用这种方式。

搜索树有很多种类型，包括二叉搜索树（AVL 树、红黑树）、B 树、B+ 树。

二叉搜索树的基本原理是构造一个二叉树，规则是比父节点小的子节点放父节点的左边，比父节点大的子节点放父节点的右边。

如果要查询一个数据，沿着根节点一路搜索下去，就能实现 O(logn) 的查询时间复杂度，同时对于插入和删除也只是在二叉树上增加和删除节点，同时会配合自平衡（也就是让二叉树不会一边特别高一边特别矮，具体实现比较复杂，不做过多介绍），时间复杂度也是 O(logn) 。

但是对于数据库来说，数据还需要存放到磁盘中，访问磁盘的速度和访问内存的速度差了几个数量级，如果使用二叉搜索树，每一次搜索节点都会访问一次磁盘，这也就意味着搜索树越高，查询速度越慢，所以这时就需要考虑减少树高了。

解决方法很容易想到，也就是使用多叉树，其实也就是 B 树，假设一个节点有 1000 个子节点，那么 3 层树高就差不多能存放 10 亿行数据，这么多数据对于二叉树差不多需要 30 层树高。

B+ 树是在 B 树的基础上做了改进：只有叶子节点存放数据，根节点和中间节点都不存放数据，这样可以保证查询的稳定性，并且叶子节点之间通过双向链表相连，这样可以实现快速的范围查询。

innoDB 的索引

MySQL innoDB 引擎使用的索引是 B+ 树，每一个索引都对应着一个 B+ 树，这其中又要区分一下聚簇索引和二级索引。

聚簇索引就是指除了索引键以外其他数据也都在叶子节点上，这样好处是聚簇索引就是数据表，不需要额外的数据结构作为数据表，也就是说其实主键索引就是聚簇索引，如果没有定义主键的话 innoDB 还是默认生成一个自增键作为聚簇索引的键。

举个例子，如果有一个用户表，主键是 id，字段有 name、sex、phone，那么这个表的聚簇索引大致就是这样的：

二级索引就是指除了主键索引以外手动建立的索引，也就是普通索引，这样的索引叶子节点存放的不只是索引键，还有一个对应的主键，这样也就意味着当使用普通索引查询索引键和主键以外的其他数据时，当到对应索引之后还需要通过叶子节点的主键，再通过聚簇索引查询一次，这个查询称为“回表查询”。