从二叉查找树到B*树，一文搞懂搜索树的演进！

对于准备面试这篇再适合不过了！详细讲解了从BST、AVL、红黑树、B树、B+树最后到B*树的演进过程，以及各种结构的优劣。

点击上方“后端开发技术”，选择“设为星标” ，优质资源及时送达

在面试中，面试官很容易抛出这样的问题：为什么MySQL多种数据引擎要用B+树不用别的数据结构呢？为什么红黑树结构在计算机中内存中被广泛应用？

如果你没有这样体系性的思考过这些问题，那非常应该看这篇文章。

本文将从二分查找说起，详细讲解搜索树型结构针对特定问题而产生的演进，让你知其然更知其所以然。

二分查找

对于查找数据，不得不提的一种基础算法就是二分法，很多数据结构的查找算法核心思想都是二分法，其查找效率也经常会用来和二分法来做对比。二分法的时间复杂度为O(logN)，这是一个非常优秀的时间复杂度，其效率仅次于常数时间复杂度 O(1)。

二分查找的实现思路是这样的：

对数据集进行排序
找到数据集的中间节点，判断是否为查找的值，等于直接返回。
根据与中间节点大小的比较结果，确定收缩查找区间范围是中间节点的左边还是右边。
重复上述 2、3 过程继续查找。

从其实现思路来看，有两个点很重要：一是可以保证数据的有序性，二是适合进行数据分段存储，方便缩小区间查找。所以根据这种思路，演化出了两个不同的路线，树和跳表两种数据结构。

二叉搜索树BST

二叉搜索树(BST，Binary Search Tree)（又叫二叉查找树）是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
它的左、右子树也分别为二叉排序树。

二叉搜索树的问题

二叉搜索树符合了使用二分法查询数据的要求，但是有个问题：因为插入顺序的不同，二叉树的高度不稳定，极端情况下可能变成链表（就是插入的数据是有序的，递增或者递减）。这就成了线性查询，时间复杂度最多变成O(n)，查询效率不稳定。

为了解决这个问题，就产生了各种树的平衡算法，保证树的节点高度不会差太多。所以就有了AVL树（平衡二叉树）和红黑树等新的数据结构。

AVL树

平衡二叉树全称叫做平衡二叉搜索（排序）树，AVL树是最早的平衡二叉树之一。

为了解决一般的二叉搜索树存在的问题，即根节点到叶子结点的高度相差太多，查询效率不问题，并且极端情况有成为链表的可能。所以AVL树具有以下特点：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
左右两个子树也都是一棵平衡二叉树。

在AVL树中，任何节点的两个子树的高度最大差别为 1 ，所以它也被称为平衡二叉树。

AVL树查找、插入和删除在平均和最坏情况下都是O(LogN)。

AVL 什么意思？AVL 是大学教授 G.M. Adelson-Velsky 和 E.M. Landis 名称的缩写，他们提出的平衡二叉树的概念，为了纪念他们，将平衡二叉树称为 AVL树。

与普通二叉搜索树的区别的是，它在插入和删除节点的时候，会根据需要进行左旋或者右旋，来保证二叉树的平衡，示意图如下。这不是本文的讨论重点，感兴趣自己可以研究。

AVL树的问题

AVL树高度的平衡情况固然很好，但这是有代价的。为了维持平衡，其旋转是非常耗时的。

AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要两次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn)。

由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。

场景：windows对进程地址空间的管理用到了AVL树。

针对于这种情况，红黑树对其做了优化。

红黑树RB-Tree

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明，在当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。

红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。

特性

一棵红黑树同时满足以下特性：

节点是红色或黑色
根是黑色
叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），下图中的那些null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点
红色节点的子节点都是黑色
- 红色节点的父节点都是黑色
- 从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

红黑树的查找，插入和删除操作，时间复杂度都是O(logN)。

红黑树解决了AVL树什么问题

AVL的左右子树高度差不能超过1，每次进行插入/删除操作时，几乎都需要通过旋转操作保持平衡
在频繁进行插入/删除的场景中，频繁的旋转操作使得AVL的性能大打折扣
红黑树通过牺牲严格的平衡，换取插入/删除时少量的旋转操作，整体性能优于AVL。红黑树插入时的不平衡，不超过两次旋转就可以解决；删除时的不平衡，不超过三次旋转就能解决
红黑树的红黑规则，保证最坏的情况下，也能在O(log 2N)时间内完成查找操作。

红黑树和AVL树的效率对比：

如果插入一个node引起了树的不平衡，AVL树和红黑树都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而红黑树最多只需3次旋转，只需要O(1)的复杂度。
其次，AVL树的结构相较红黑树来说更为平衡，在插入和删除node更容易引起Tree的不平衡，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，红黑树在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，红黑树的统计性能是高于AVL的。

最坏情况下，AVL树有最多O(logN)次旋转，而红黑树最多三次。

场景：

红黑树的应用就很多了。

epoll在内核中的实现，用红黑树管理事件块。
nginx中，用红黑树管理timer等。
Java1.8版本后的的hashMap中使用链表+红黑树解决哈希冲突问题，Java中的TreeMap使用红黑树存储排序键值对。
著名的linux进程调度Completely Fair Scheduler，用红黑树管理进程控制块。

红黑树的问题

虽然红黑树是一种已经被性能优化了的自平衡的二叉查找树，插入修改效率和查找销量得到了平衡，但他依然存在一些问题。

依旧在插入和删除时需要对节点进行旋转，频繁修改数据的场景影响效率。
红黑树毕竟是一种二叉树，当数据量很大时，树的高度会变得很大，查找时经过的节点过多，效率变低。
红黑树在内存中表现优秀，但因为树的高度的问题，当使用磁盘等辅助存储设备读写数据时（如MySQL等数据库），会导致数据在磁盘中散布分散，并且IO次数过多，效率变低。
适合单个查询，对于数据查询中常见的范围查询场景，无法很好支持。

针对于上述问题，有了天生为磁盘存储而生的B树。

B树

B树是一种多路搜索树，又名平衡多路查找树（查找路径不只两个），与二叉树相比，B树的每个非叶节点可以有多个子树。因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。数据库索引技术里大量使用者B树和B+树的数据结构。

定义B树最重要的概念是阶数(Order)，对于一颗m阶B树（就是一个节点最多包含几个子节点），需要满足以下条件：

每个节点最多包含 m 个子节点。
如果根节点包含子节点，则至少包含 2 个子节点；除根节点外，每个非叶节点至少包含 m/2 个子节点。
拥有 k 个子节点的非叶节点将包含 k - 1 条记录。
所有叶节点都在同一层中。

度数：在树中，每个节点的子节点（子树）的个数就称为该节点的度 (degree)。

阶数：阶(order)定义为一个节点最多可以有多少个元素。

如下图，这是一个2阶3度的B树。

场景：MongoDB索引。

B树的优势

B树相对平衡二叉树在节点空间的利用率上进行改进，B树在每个节点保存更多的数据，减少了树的高度，从而提升了查找的性能。

B树的优势除了树高小，还有对访问局部性原理的利用。

所谓局部性原理，是指当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；换句话说，B树的缓存命中率更高。

在数据库应用中，B树的每个节点存储的数据量大约为4K, 这是因为考虑到磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次对磁盘进行IO数据读取时，同一个磁盘块的数据会被一次性读取出来，所以每一次磁盘IO都可以读取到B树中一个节点的全部数据。

对于顺数插入的数据，B树的结构优势可以使其在内存中顺序排列，存贮到同一个磁盘页中，顺序插入对磁盘的利用率和读取效率都非常友好。

场景：MySQL的InnbDB 索引。

B树的问题

B树虽然解决了磁盘存储的问题，但是在查询范围数据时依旧不够优秀，比如你要查询1-5的数据，必须按照树的中顺遍历来访问各个节点。

对于这个问题，B+树对其进行了优化。

B+树

B+树是在B树的基础上又一次的改进，其主要对两个方面进行了提升，一方面是查询的稳定性，另外一方面是在数据排序方面更友好。

B+树也是多路平衡查找树，其特性主要有以下4点：

B树中每个节点（包括叶节点和非叶节点）都存储真实的数据，B+树中只有叶子节点存储真实的数据，非叶节点只存储键。在MySQL中，这里所说的真实数据，可能是行的全部数据（如Innodb的聚簇索引），也可能只是行的主键（如Innodb的辅助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。
B树中一条记录只会出现一次，不会重复出现，而B+树的键则可能重复重现——一定会在叶节点出现，也可能在非叶节点重复出现。
B+树的叶节点之间通过双向链表链接。B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。因为叶子节点都是有序排列的，所以B+树对于数据的排序有着更好的支持。
B+树非叶子节点的子节点数=关键字数，或者非叶节点的关键字数=子节点数-1（这里有两种算法的实现方式)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）。

第一种算法：