数据结构 二叉树、平衡二叉树、红黑树、B树、B+树与B*树

一、二叉树

1️⃣二叉查找树的特点就是左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大，如图：

基于二叉查找树的这种特点，在查找某个节点的时候，可以采取类似于二分查找的思想，快速找到某个节点。n 个节点的二叉树，正常情况下，查找的时间复杂度为 O(logN)。之所以说是正常情况下，是因为二叉查找树有可能出现一种极端的情况，例如：

这种情况虽也满足二叉树的条件，但已经近似退化为一条链表，这样的二叉树的查找时间复杂度顿时变成了 O(n)。所以必须防止这种情况发生，于是引申出了平衡二叉树。

二、平衡二叉树 AVL

1️⃣平衡二叉树是基于二分法的策略提高数据查找速度的二叉树的数据结构。

2️⃣平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度。平衡二叉树的数据结构组装过程有以下规则：

非叶子节点只能允许最多两个子节点存在。每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如 hash 值)。

平衡树的层级结构：平衡二叉树的查询性能和树的层级(高度h)成反比，h 值越小查询越快。为了保证树的结构左右两端数据大致平衡。降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有 Treap、红黑树等。使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于 1，通过这样避免树形结构由于【删除/增加】变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找：

3️⃣平衡二叉树特点：

非叶子节点最多拥有两个子节点。非叶子节点值大于左边子节点、小于右边子节点。树的左右两边的层级数相差不会大于 1。没有值相等重复的节点。

AVL 树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1。和红黑树相比，它是严格的平衡二叉树，平衡条件必须满足(所有节点的左右子树高度差不超过1)。不管是插入还是删除，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此 AVL 树适合用于插入删除次数比较少，但查找多的情况。

三、红黑树

1️⃣为什么有了平衡树还需要红黑树？ 虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，却不是最佳的。因为平衡树要求每个节点的左子树和右子树的高度差至多等于 1，这个要求太严，导致每次进行【插入/删除】节点的时候，几乎都会破坏平衡树的第二个规则，进而都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

2️⃣红黑树的特性 显然，如果在【插入/删除】很频繁的场景中，平衡树需要频繁调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树，红黑树具有如下特点：

每个节点非黑即红。根节点总是黑色的。每个叶子节点(NIL)都是黑色的。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点]如果节点是红色的，则它的子节点必须是黑色的(反之不一定)。从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点。[这里指到叶子节点的路径]

包含 n 个内部节点的红黑树的高度是 O(log(n))。如图：

3️⃣Java 使用到红黑树的有 TreeSet 和 JDK8 的 HashMap。红黑树的【插入/删除】都要满足以上 5 个特性，操作非常复杂。 为什么要使用红黑树？原因：红黑树是一种平衡树，复杂的定义和规则都是为了保证树的平衡性。如果树不保证平衡性有可能变成链表：

保证平衡性的最大的目的就是降低树的高度，因为树的查找性能取决于树的高度。所以树的高度越低搜索的效率越高！

四、B 树：平衡多路查找树

B 树和 B-tree，其实是同一种树。B-Tree 中间是连字符(hyphen)，不是减号(minus)。

1️⃣B 树和平衡二叉树稍有不同的是 B 树属于多叉树又名平衡多路查找树(查找路径不只两个)，数据库索引技术里大量使用 B 树和 B+ 树的数据结构。

2️⃣规则

排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则。子节点数：非叶子节点的子节点数>1，且<=M ，且M>=2，空树除外(注：M 阶代表一个树节点最多有多少个查找路径，M=M路，当 M=2 则是二叉树，M=3 则是三叉)。关键字数：枝节点的关键字数量大于等于 ceil(m/2)-1 个且小于等于 M-1 个(注：ceil()是个朝正无穷方向取整的函数。如ceil(1.1)结果为2)。所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为 null 对应下图最后一层节点的空格子。

用一个图和一个实际的例子来理解 B 树(便于理解直接用实际字母的大小来排列C>B>A)：

3️⃣B树的查询流程(如要从上图中找到 E)

获取根节点的关键字进行比较，当前根节点关键字为 M，E

4️⃣B树的插入节点流程 定义一个五阶树(平衡五路查找树)，现在要把 3、8、31、11、23、29、50、28 这些数字构建出一个五阶树出来。遵循规则：

节点拆分规则：当前是要组成一个五路查找树，此时 m=5，关键字数必须<=5-1(这里关键字数>4就要进行节点拆分)。排序规则：满足节点本身比左边节点大，比右边节点小。

先插入 3、8、31、11：

再插入23、29：

再插入50、28：

5️⃣B树节点的删除

规则：

节点合并规则：当前是要组成一个五路查找树，此时 m=5，关键字数必须大于等于ceil(5/2)(这里关键字数<2就要进行节点合并)。满足节点本身比左边节点大，比右边节点小的排序规则。关键字数 <2 时先从子节点取，子节点没有符合条件时就向父节点取，取中间值往父节点放。

特点： B 树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在 B 树应用到数据库中的时候，数据库充分利用了磁盘块的原理(磁盘数据存储是采用块的形式存储的，每个块的大小为 4 K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来)把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。

五、B+ 树

1️⃣概念 B+ 树是 B 树的一个升级版，B+ 树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么 B+ 树查找的效率要比 B 树更高、更稳定？

2️⃣规则

B+ 树跟 B 树不同。B+ 树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得 B+ 树每个非叶子节点所能保存的关键字大大增加。B+ 树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样。B+ 树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。非叶子节点的子节点数=关键字数(百度百科。根据各种资料，这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1(维基百科)，虽然数据排列结构不一样，但其原理还是一样的。MySQL的 B+ 树是用第一种方式实现)。

3️⃣特点

【B+ 树的层级更少】：相较于 B 树，B+ 树每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快。【B+ 树查询速度更稳定】：B+ 树所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比 B 树更稳定。【B+ 树天然具备排序功能】：B+ 树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比 B 树高。【B+ 树全节点遍历更快】：B+ 树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像 B 树对每一层进行遍历，这有利于数据库做全表扫描。B 树相对于 B+ 树的优点：如果经常访问的数据离根节点很近，而 B 树的非叶子节点本身存有关键字其数据的地址，此种数据检索的时候会要比 B+ 树快。

六、B* 树

1️⃣B* 树是 B+ 树的变种，区别如下：

首先是关键字个数限制问题，B+ 树初始化的关键字初始化个数是 cei(m/2)，B* 树的初始化个数为 cei(2/3*m)。B+ 树节点满时就会分裂，而 B* 树节点满时会检查兄弟节点是否满(因为每个节点都有指向兄弟的指针)，如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出 1/3 的数据创建一个新的节点出来。

2️⃣特点 在 B+ 树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得 B* 树额分解次数变得更少；

七、 总结

1️⃣相同思想和策略 从平衡二叉树、B 树、B+ 树、B* 树总体来看它们的思想都是采用二分法和数据平衡策略来提升查找数据的速度。

2️⃣不同的方式的磁盘空间利用 不同点是它们一个一个在演变的过程中通过 IO 从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的。

3️⃣拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了，造成很深的问题)，遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于 8 的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

推荐链接