对于准备面试这篇再适合不过了！详细讲解了从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₂n)时间内完成查找操作。
红黑树和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+树是用第一种方式实现）。
第一种算法：
第二种算法：
B+树和B树的对比
1、B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，所以每个磁盘块存储的数据更多，树的层级更少所以查询数据更快
2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定
3、B+树天然具备排序功能：所有关键字都出现在叶子结点的链表中（稠密索引），B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。
5、B+树更适合文件索引系统
B+树的缺点
在B+树的构建过程中，为了保持树的平衡，节点的合并拆分是比较耗费时间的，所以B*树就是在如何减少构建中节点合并和拆分的次数，从而提升树的数据插入、删除性能。
B*树
相对于B+树，B*树的不同之处如下：
（1）首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b树的初始化个数为（cei(2/3m)）
（2）B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；
B*树 与B+树对比
在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少。
总结
对于上述的演进过程，这里给出一个简要总结，如下图。建议收藏！
