InnoDB 为什么选择 B+ 树索引

首先在执行效率方面，我们希望查询效率尽可能的高、速度尽可能的快、存储空间方面我们希望他所需的空间尽可能的小

哈希表

哈希表查询的时间复杂度是 O(1)，但是哈希表不支持区间的查询方式哈希索引的哈希值存储是无序的，哈希索引不能进行范围的查找，也不能进行排序的操作

平衡二叉树

随着二叉树高度的增加，二叉树查找的速度会越来越慢

并且平衡二叉树也不支持快速的范围查找

B 树

B 树相对于平衡二叉树解决了树的高度的问题，但是依旧不能支持范围查找，在进行范围查找时需要进行回旋查找

B+ 树

B+ 树在B 树的基础上 增添了叶子节点，非叶子节点值存储 Key 叶子节点存储 Key+value，并且所有叶子节点有序且为双向循环链表，解决了范围查找的问题

跳表

跳表支持快速的插入和删除，查找的时间复杂度是 O(log n)

但是 B+ 树比跳表的检索效率更高，数据分布更均匀

跳表是通过二路分治的方式实现log n

B+树是通过多路分治的方式实现log n

当数据表数据足够多的时候， B+ 树的根节点到任何一块叶子节点的路径是固定的，而跳表的头节点到目标节点的路径数是不固定的，检索的value越大，跳表的路径就越深，磁盘 IO 的次数就越多

B+树的所有叶子节点构成了一个双向循环链表，每一块叶子节点可以存储一条或多条数据，这种结构不管是一条记录还是多条记录都能节省磁盘 IO

跳表对于多条记录的查询所需的IO次数会增多