索引底层数据结构选型
Hash 表
哈希表是键值对的集合，通过键(key)即可快速取出对应的值(value)，因此哈希表可以快速检索数据（接近 O（1））。
为何能够通过 key 快速取出 value 呢？ 原因在于 哈希算法（也叫散列算法）。通过哈希算法，我们可以快速找到 key 对应的 index，找到了 index 也就找到了对应的 value。
hash = hashfunc(key)
index = hash % array_size
但是哈希算法有个 Hash 冲突 问题，也就是说多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。
为了减少 Hash 冲突的发生，一个好的哈希函数应该“均匀地”将数据分布在整个可能的哈希值集合中。
MySQL 的 InnoDB 存储引擎不直接支持常规的哈希索引，但是，InnoDB 存储引擎中存在一种特殊的“自适应哈希索引”（Adaptive Hash Index），自适应哈希索引并不是传统意义上的纯哈希索引，而是结合了 B+Tree 和哈希索引的特点，以便更好地适应实际应用中的数据访问模式和性能需求。自适应哈希索引的每个哈希桶实际上是一个小型的 B+Tree 结构。这个 B+Tree 结构可以存储多个键值对，而不仅仅是一个键。这有助于减少哈希冲突链的长度，提高了索引的效率。关于 Adaptive Hash Index 的详细介绍，可以查看 MySQL 各种“Buffer”之 Adaptive Hash Index 这篇文章。
既然哈希表这么快，为什么 MySQL 没有使用其作为索引的数据结构呢？
主要是因为 Hash 索引不支持顺序和范围查询。假如我们要对表中的数据进行排序或者进行范围查询，那 Hash 索引可就不行了。
并且，每次 IO 只能取一个。
试想一种情况:
SELECT * FROM tb1 WHERE id < 500;
在这种范围查询中，B+优势非常大，直接遍历比 500 小的叶子节点就够了。而 Hash 索引是根据 hash 算法来定位的，难不成还要把 1 - 499 的数据，每个都进行一次 hash 计算来定位吗?这就是 Hash 最大的缺点了。
二叉查找树(BST)
二叉查找树（Binary Search Tree）是一种基于二叉树的数据结构，它具有以下特点：
左子树所有节点的值均小于根节点的值。
右子树所有节点的值均大于根节点的值。
左右子树也分别为二叉查找树。
当二叉查找树是平衡的时候，也就是树的每个节点的左右子树深度相差不超过 1 的时候，查询的时间复杂度为O(log2(N))，具有比较高的效率。
然而，当二叉查找树不平衡时，例如在最坏情况下（有序插入节点），树会退化成线性链表（也被称为斜树），导致查询效率急剧下降，时间复杂退化为 O（N）。
也就是说，二叉查找树的性能非常依赖于它的平衡程度，这就导致其不适合作为 MySQL 底层索引的数据结构。
为了解决这个问题，并提高查询效率，人们发明了多种在二叉查找树基础上的改进型数据结构，如平衡二叉树、B-Tree、B+Tree 等。
AVL 树
AVL 树是计算机科学中最早被发明的自平衡二叉查找树，它的名称来自于发明者 G.M. Adelson-Velsky 和 E.M. Landis 的名字缩写。AVL 树的特点是保证任何节点的左右子树高度之差不超过 1，因此也被称为高度平衡二叉树，它的查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn)。
AVL 树采用了旋转操作来保持平衡。主要有四种旋转操作：
LL 旋转、
RR 旋转、
LR 旋转和
RL 旋转。其中 LL 旋转和 RR 旋转分别用于处理左左和右右失衡，而 LR 旋转和 RL 旋转则用于处理左右和右左失衡。
由于 AVL 树需要频繁地进行旋转操作来保持平衡，因此会有较大的计算开销进而降低了查询性能。并且， 在使用 AVL 树时，每个树节点仅存储一个数据，而每次进行磁盘 IO 时只能读取一个节点的数据，如果需要查询的数据分布在多个节点上，那么就需要进行多次磁盘 IO。 磁盘 IO 是一项耗时的操作，在设计数据库索引时，我们需要优先考虑如何最大限度地减少磁盘 IO 操作的次数。实际应用中，AVL 树使用的并不多。
红黑树
红黑树是一种自平衡二叉查找树，通过在插入和删除节点时进行颜色变换和旋转操作，使得树始终保持平衡状态，它具有以下特点：
每个节点非红即黑；
根节点总是黑色的；
每个叶子节点都是黑色的空节点（NIL 节点）；
如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。
和 AVL 树不同的是，红黑树并不追求严格的平衡，而是大致的平衡。正因如此，红黑树的查询效率稍有下降，因为红黑树的平衡性相对较弱，可能会导致树的高度较高，这可能会导致一些数据需要进行多次磁盘 IO 操作才能查询到，这也是 MySQL 没有选择红黑树的主要原因。也正因如此，红黑树的插入和删除操作效率大大提高了，因为红黑树在插入和删除节点时只需进行 O(1) 次数的旋转和变色操作，即可保持基本平衡状态，而不需要像 AVL 树一样进行 O(logn) 次数的旋转操作。
红黑树的应用还是比较广泛的，TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。对于数据在内存中的这种情况来说，红黑树的表现是非常优异的。
B 树& B+树
B 树也称 B-树,全称为 多路平衡查找树 ，B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。
目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。
B 树& B+树两者有何异同呢？
- B 树的所有节点既存放键(key) 也存放数据(data)；而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
- B 树的叶子节点都是独立的；B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
- B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
- 在 B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；而 B+树的范围查询，只需要对链表进行遍历即可。
综上，B+树与 B 树相比，具备更少的 IO 次数、更稳定的查询效率和更适于范围查询这些优势。
在 MySQL 中，MyISAM 引擎和 InnoDB 引擎都是使用 B+Tree 作为索引结构，但是，两者的实现方式不太一样。（下面的内容整理自《Java 工程师修炼之道》）
MyISAM 引擎中，B+Tree 叶节点的 data 域存放的是数据记录的地址。在索引检索的时候，首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域的值为地址读取相应的数据记录。这被称为“非聚簇索引（非聚集索引）”。
InnoDB 引擎中，其数据文件本身就是索引文件。相比 MyISAM，索引文件和数据文件是分离的，其表数据文件本身就是按 B+Tree 组织的一个索引结构，树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。这被称为“聚簇索引（聚集索引）”，而其余的索引都作为 辅助索引 ，辅助索引的 data 域存储相应记录主键的值而不是地址，这也是和 MyISAM 不同的地方。在根据主索引搜索时，直接找到 key 所在的节点即可取出数据；在根据辅助索引查找时，则需要先取出主键的值，再走一遍主索引。 因此，在设计表的时候，不建议使用过长的字段作为主键，也不建议使用非单调的字段作为主键，这样会造成主索引频繁分裂。
B树和B+Tree每一个节点实际上可以理解为是一个文件页 mysql默认给一个文件页分配16k存储
B树的每个节点都会存储data数据，而B+Tree的话非叶子节点是存储的索引（冗余），不存储data数据，这样每一页文件页能存储的节点就很多，树的高度就可以得到很好的控制，树的高度越高，从磁盘load节点到内存对比的次数就会越多，磁盘I/O是费时。
所以B+Tree在树高度相同的情况下能够存储更多的索引数据，间接的减少了磁盘的I/O操作，B+Tree的I/O次数会更加稳定一些。
还有就是从范围查询的角度上来说B+Tree也具备绝对的优势，因为B+Tree在每个相邻的叶子节点之间都有互相指向。
B+Tree在全表扫描的情况下也是比较占优势的，因为B+Tree的数据都是存储在非叶子节点的，所以只需要扫描叶子节点就可以拿到全部数据了，B Tree的话就需要从头遍历整颗树。
Mysql的索引为什么使用B+树而不使用跳表
B+树更适合磁盘IO
B+Tree一个节点是一个page，是一种多叉树结构，每个结点都是一个16k的数据页，能存放较多索引信息。一次IO一个page，大大节省了磁盘IO的操作。B+Tree一个page 能存放较多索引信息 ，所以树的层数比较低， 三层左右就可以存储2kw左右的数据也就是说查询一次数据，如果这些数据页都在磁盘里，那么最多需要查询三次磁盘IO。
原生跳表不适合磁盘IO
跳表是链表结构，一条数据一个结点，那么一个node节点一次磁盘io， 一个page 页规模的IO存储的性能 估计要下降1000倍以上。
原生跳表 一个node存放一个 索引信息 ，所以树的层数比较高，如果最底层要存放2kw数据，且每次查询都要能达到二分查找的效果，2kw大概在2的24次方 左右。所以，2kw数据的跳表大概高度在24层左右。 如果要进行查找，大概要进行 24次磁盘IO。这里讲的是原生跳表， 如果经过各种改进，那个不在此文讨论范围。
所以，虽然在理论上，跳表的时间复杂度和B+树相同 ，但是：
B+树更适合 磁盘IO， 更合适MYSQL。从反面来说，跳表更适合内存IO， 更适合redis。（redis没有io的烦恼）
Redis的索引为什么使用跳表而不使用B+树
那么，为啥 redis 用跳表而不用B+树？
关于这个问题，Redis作者是这么说的：
There are a few reasons:
1、They are not very memory intensive.
It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2、A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3、They are simpler to implement, debug, and so forth.
For instance thanks to the skip list simplicity I received a patch(already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
主要是从内存占用、对范围查找的支持、实现难易程度这三方面总结的原因，简单翻译如下：
- 它们不是非常内存密集型的。基本上由你决定。改变关于节点具有给定级别数的概率的参数将使其比 btree 占用更少的内存。
- Zset 经常需要执行 ZRANGE 或 ZREVRANGE 的命令，即作为链表遍历跳表。通过此操作，跳表的缓存局部性至少与其他类型的平衡树一样好。
- 它们更易于实现、调试等。例如，由于跳表的简单性，我收到了一个补丁（已经在Redis master中），其中扩展了跳表，在 O(log(N) 中实现了 ZRANK。它只需要对代码进行少量修改。
关于上述观点，做几点补充如下：
- 从内存占用上来比较，跳表比平衡树更灵活一些。平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。
- 在做范围查找的时候，跳表比平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
- 从算法实现难度上来比较，跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。