『SQL』拜托，别再问我什么是 B+ 树了( 二 ) |数据结构|

哈希索引并不是按照索引值顺序存存储的，所以也就无法用于排序，也就是说无法根据区间快速查找

哈希索引只包含哈希值和行指针，不存储字段值，所以不能使用索引中的值来避免读取行，不过，由于哈希索引多数是在内存中完成的，大部分情况下这一点不是问题

哈希索引只支持等值比较查询，包括 =,IN ，不支持任何范围的查找，如 age > 17

综上所述，哈希索引只适用于特定场合，如果用得对，确实能再带来很大的性能提升，如在 InnoDB 引擎中，有一种特殊的功能叫「自适应哈希索引」，如果 InnoDB 注意到某些索引列值被频繁使用时，它会在内存基于 B+ 树索引之上再创建一个哈希索引，这样就能让 B+树也具有哈希索引的优点，比如快速的哈希查找。
2、链表
双向链表支持顺序查找和逆序查找，如图下

本文插图

但显然不支持我们说的按某个值或区间的快速查找，另外我们知道表中的数据是要不断增加的，索引也是要及时插入更新的，链表显然也不支持数据的快速插入，所以能否在链表的基础上改造一下，让它支持快速查找，更新，删除。有一种结构刚好能满足我们的需求，这里引入跳表的概念。
什么是跳表?简单地说，跳表是在链表之上加上多层索引构成的。如下图所示

本文插图

假设我们现在要查找区间 7- 13 的记录，再也不用从头开始查找了，只要在上图中的二级索引开始找即可，遍历三次即可找到链表的区间位置，时间复杂度是 O(logn) ，非常快，这样看来，跳表是能满足我们的需求的，实际上它的结构已经和 B+ 树非常接近了，只不过 B+ 树是从平衡二叉查找树演化而来的而已，接下来我们一步步来看下如何将平衡二叉查找树改造成 B+ 树。
先来看看什么是平衡二叉查找树，平衡二叉查找树具有如下性质：

若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
每个非叶子节点的左右子树的高度之差的绝对值（平衡因子）最多为1 。

下图就是一颗平衡二叉查找树

本文插图

从其特性就可以看到平衡二叉查找树查找节点的时间复杂度是 O(log2n)
现在我们将其改造成 B+ 树

本文插图

可以看到主要区别就是所有的节点值都在最后叶节点上用双向链表连接在了一起，仔细和跳表对比一下，是不是很像，现在如果我们要找15 ~ 27 这个区间的数只要先找到 15 这个节点（时间复杂度 logn = 3 次）再从前往后遍历直到 27 这个节点即可，即可找到这区间的节点，这样它完美地支持了我们提的三个需求：快速查找值，区间，顺序逆序查找。
假设有 1 亿个节点，每个节点要查询多少次呢，显然最多为 log21亿 = 27 次，如果这 1 亿个节点都在内存里，那 27 次显然不是问题，可以说是非常快了，但一个新的问题出现了，这 1 亿个节点在内存大小是多少呢，我们简单算一下，假设每个节点 16 byte ，则 1 亿个节点大概要占用 1.5G 内存！对于内存这么宝贵的资源来说是非常可怕的空间消耗，这还只是一个索引，一般我们都会在表中定义多个索引，或者库中定义多张表，这样的话内存很快就爆满了！所以在内存中完全装载一个 B+ 树索引显然是有问题的，如何解决呢。