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

本文从二分查找讲起，讲解了BST、AVL、红黑树、B树、B+树最后到B*树的演进过程，知其所以然！

在计算机中有一些数据结构总是与数据的查找分不开，比如二叉查找树（Binary Search Tree）、红黑树、B树、B+树等等数据结构。你可曾想过为什么会有这么多种用于搜索的数据结构？为什么红黑树结构在计算机中内存中被广泛应用？为什么MySQL多种数据引擎都选择B+树作为其索引实现？为什么Redis要使用跳表？

带着这些问题，这篇文章我们探讨一下这些数据结构在实际中的应用以及针对于存在的问题产生的演进。

二分查找

对于查找数据，不得不提的一种基础算法就是二分法，很多数据结构的查找算法核心思想都是二分法，其查找效率也经常会用来和二分法来做对比。二分法的时间复杂度为**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+树是用第一种方式实现）。

第一种算法：