用过 MySQL 的应该都知道索引是干啥的吧，应该多少都设置过索引，但是若是问你索引是怎么实现的，你能说上来吗？
索引是什么？MySQL 官方对索引的定义为：索引是帮助 MySQL 高效获取数据的数据结构。
在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
索引的出现就是为了提高查询效率，就像书的目录。其实说白了，索引要解决的就是查询问题。
查询，是数据库所提供的一个重要功能，我们都想尽可能快的获取到目标数据，因此就需要优化数据库的查询算法，选择合适的查询模型来实现索引。
另外，为表设置索引要付出代价的：一是增加了数据库的存储空间，二是在插入和修改数据时要花费较多的时间，因为索引也要随之变动。
常见查询模型索引的实现模型有很多，这里我们先了解一下常用的查询模型。
顺序数组顺序数组是一种特殊的数组，里面的元素，按一定的顺序排列。
顺序数组在查询上有着一定的优势，因为是有序的数据，采用二分查找的话，时间复杂度是 O(log(N))。
顺序数组的优点就是查询效率非常高，但是要更新数据的话，就非常麻烦了。删除和插入元素都要涉及到大量元素位置的移动，成本很高。
因此，对于顺序数组更适合用于查询的领域，适合存储一些改动较小的静态存储引擎。
哈希索引哈希表是一种以 键-值（key-value） 存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 value。
哈希索引采用一定的哈希算法，对于每一行，存储引擎计算出了被索引字段的哈希码（Hash Code），把哈希码保存在索引中，并且保存了一个指向哈希表中的每一行的指针。
这样在检索时只需一次哈希算法即可立刻定位到相应的位置，速度非常快。
Hash 索引结构的特殊性，其检索效率非常之高，应该是 O(1) 的时间复杂度。
虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些：
1、Hash索引仅仅能满足 =，IN 和 <=> 查询，如果是范围查询检索，这时候哈希索引就毫无用武之地了。
因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索；
2、Hash 索引无法利用索引完成排序，因为存放的时候是经过 Hash 计算过的，计算的 Hash 值和原始数据不一定相等，所以无法排序；
3、联合索引中，Hash 索引不能利用部分索引键查询。
Hash 索引在计算 Hash 值的时候是联合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值。
所以对于联合索引中的多个列，Hash 是要么全部使用，要么全部不使用。通过前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。
4、Hash索引在任何时候都不能避免表扫描。
前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash 运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键可能存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
5、在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。
综上，哈希表这种结构适用于只有等值查询的场景，比如 Memcached、redis 及其他一些 NoSQL 引擎。
二叉搜索树索引二叉搜索树的每个节点都只存储一个键值，并且左子树（如果有）所有节点的值都要小于根节点的值，右子树（如果有）所有节点的值都要大于根节点的值。
当二叉搜索树的所有非叶子节点的左右子树的节点数目均保持差不多时（平衡），这时树的搜索性能逼近二分查找；并且它比连续内存空间的二分查找更有优势的是，改变树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销。
特殊情况下，根节点的左右子树的高度相差不超过 1 时，这样的二叉树被称为平衡二叉树；与之相对的是，二叉搜索树有可能退化成线性树。
