一、索引的实现模型

MySQL索引类似于书籍的目录，其设计目的是为了提高数据查询的效率。索引的本质是一个数据结构，那么自然有多种不同的数据结构设计，所以有不同的索引实现模型，典型的实现模型有哈希表、有序数组和搜索树。

1、哈希表

哈希表是一种键-值（key-value）的存储结构，只要确定了待查询的key，就可以很快速地查询到对应的value。设置一个合适离散度的哈希函数，将key值通过哈希函数映射成一个数值作为在数组中的位置下标，将对应的数据对象放在这个数组中。

当然不同的key有可能存在经过哈希函数映射以后的值是一样的情况，针对这种场景，可以在对应的数组存放一个链表，key映射后值一样的数据对象根据先后顺序存放在链表中，当进行查询时，则遍历此列表进行比对查询，这与Java中HashMap数据结构的实现十分类似。

以下是哈希表形式的示意图：

通过以上的描述可知，哈希表特别适合等值查询的场景，例如Redis，数据插入的效率也比较高，其时间复杂度为O(1)。但是，对于范围查询等场景，由于数据在哈希表中的存放是无序的，所以范围查询会造成全表的扫描，因此查询的效率会严重下降，时间复杂度为O(n)。

2、有序数组

有序数组的形式是将数据存放在一个大型数组当中，并且数据在数组当中存放是按照数据是进行有序存放的，这样子的场景下，等值查询和范围查询的速度都非常快。例如，可以使用二分法根据key值实现快速查询，针对范围查询则转化为根据等值查询查到第一个元素以后往后进行遍历即可，时间复杂度为O(log(N))。

以下是有序数组形式的示意图：

虽然在查询的场景下有序数组的效率很高，但是一旦要插入一条数据记录就需要挪动后面所有的数据，这个成本就非常的高，所以有序数组在数据插入的场景下效率比较低，时间复杂度为O(n)+O(log(N))。有序数组适用于那些数据基本不会变化的静态存储引擎。

3、搜索树

搜索树是经典的数据结构，最基础的有二叉搜索树。二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。

以下是搜索树形式的示意图：

如图所示，如果要查询User_9，则搜索路径为User_1>User_3>User_8>User_9，在平衡二叉树的情况下，其查询的时间复杂度为O(log(N))，当插入新的数据记录的时候，需要对树结构进行调节，维持树结构是一棵平衡二叉树，这个时间复杂度也为O(log(N))。

从以上分析来看，平衡二叉树的结构维持了数据查询和数据更新的时间复杂度都为O(log(N))，相比较有序数据和哈希表，其达到了一个数据插入和数据更新的一个平衡。

二、InnoDB存储引擎的索引模型

在第一节，我们提到使用平衡二叉树是一个实现索引组织的较好的方案，那么MySQL中实际的索引是否就可以采用平衡二叉树实现呢？

要回答这个问题，首先要了解MySQL数据的交互形式。

MySQL中数据数据最终存储在磁盘中，真正的数据处理其实是在内存中执行，由于磁盘读写的速度非常慢，特别是传统的机械磁盘，寻址时间较长，如果每个操作都直接读写磁盘，那么性能会很差。为了解决这个问题，InnoDB将数据分成了若干数据页，以页作为磁盘与内存交互的基本单位，每次读写至少都是以1页作为基本单位，这样子一来减少了与磁盘的交互次数，提升了性能。

既然InnoDB基于数据页进行读取，而数据的组织形式是二叉树，那么为了方便在内存中以二叉树的形式进行数据的查找和更新，就应该一次性读取整个二叉树，所以将每个二叉树节点作为一个数据页是合理的设计。这样子一来，当表中的数据增加，二叉树的高度就会变得很大，而每次访问一个节点都需要读取一个数据页，想象一棵 100 万节点的平衡二叉树，树高 20，一次查询可能需要访问 20 个数据页，在机械硬盘时代，从磁盘随机读一个数据页需要 10 ms 左右的寻址时间，也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这样的效率是不可接受的。

为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据页，于是应该减少树的高度，故应该采用N叉树，而不是二叉树，这里，“N 叉”树中的“N”取决于数据页的大小，数据页越大，则可以存放的索引值越多，则N越大。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，除根节点外，每个节点都可以存放1200个值，总共就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。结合以上提到的N叉树结合其他的存储特点，InnoDB选择了使用了 B+ 树索引模型，数据存储在 B+ 树中，表中每一个索引在Innodb中就对应一棵B+树。

注：本文总结自林晓斌老师的MySQL教程。