序言
数据库索引是在日常工作当中很常见的，面试时面试官问你对SQL优化有没有了解，也和索引息息相关。
一句话简单来说，索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。一本 500 页的书，如果你想快速找到其中的某一个知识点，在不借助目录的情况下，那我估计你可得找一会儿。同样，对于数据库的表而言，索引其实就是它的“目录”。
索引常见类型
索引的出现是为了提高查询效率，但是实现索引的方式却有很多种。这里先介绍三种常见、也比较简单的数据结构，它们分别是哈希表、有序数组和搜索树。
哈希表
哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。所以哈希表的查找效率很高，只需要O(1)的时间。
不可避免的可能会有多个key，经过计算后会出现同一个值的情况，这就是哈希冲突。遇见常见的哈希冲突就是在当前数组中拉出一个链表，当链表越长哈希查找的效率就越慢。所以一个好的哈希算法非常重要。
虽然哈希表查询的速度非常快，但它只适合等值查询，当遇到需要区间查询的数据时，就需要变量整张哈希表了。
所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。
有序数组
有序数组的区间查询和等值查询的性能都非常优秀，当需要查询一个对应的数值时，只需要用二分法就可以快速得到，这个时间复杂度是 O(log(N))。虽然不如哈希表的O(1)，但其性能仍十分优秀。
当执行区间查询时[value1,value2]，我们可以先使用二分查找找到value1(当value1不存在时找到比它大的第一个数)，然后向后遍历，直到查找的第一个大于value2的值。
如果只看查询效率的话，有序数组就是最优秀的数据结构了。但它的更新效率十分低下，为了维持数组的有序性，不得不耗费大量的时间来维护。
二叉搜索树
二叉搜索树的特点就是：左子节点小于父节点，而父节点又小于右子节点，其等值查询的时间复杂度为O(log(N))。当然为了维持O(log(N))的时间复杂度，就必须保证当前的树是平衡二叉树，为了做这个保证，更新时间复杂度也是O(log(N))。
数可以有二叉，也可以有多叉，多叉树保证子节点从左到右依次递增。二叉树的搜索效率是最高的，但大多数数据库的储存结构都不是二叉树，其原因是索引不止要写到内存中，还需要写到磁盘上。
一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。
为了让一个查询尽量少地读磁盘，我们可以使用“N叉”树减少数的高度，从而减少磁盘寻址时间，这里，“N 叉”树中的“N”取决于数据块的大小。
以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。
N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。
InnoDB 的索引模型
由于 InnoDB 存储引擎在 MySQL 数据库中使用最为广泛，所以下面我就以 InnoDB 为例，和你分析一下其中的索引模型。