一、二叉树

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

基于二叉查找树的这种特点，在查找某个节点的时候，能够采取相似于二分查找的思维，疾速找到某个节点。n 个节点的二叉查找树，失常的状况下，查找的工夫复杂度为 O(logN)。之所以说是失常状况下，是因为二叉查找树有可能呈现一种极其的状况，例如：

这种状况也是满足二叉查找树的条件，然而，此时的二叉查找树曾经近似进化为一条链表，这样的二叉查找树的查找时间复杂度登时变成了 O(n)。由此必须避免这种状况产生，为了解决这个问题，于是引申出了均衡二叉树。

二、均衡二叉树

1️⃣概念
均衡二叉树是基于二分法的策略进步数据的查找速度的二叉树的数据结构。

2️⃣规定
均衡二叉树是采纳二分法思维把数据按规定组装成一个树形构造的数据，用这个树形构造的数据缩小无关数据的检索，大大的晋升了数据检索的速度；均衡二叉树的数据结构组装过程有以下规定：
①非叶子节点只能容许最多两个子节点存在。
②每一个非叶子节点数据分布规定为右边的子节点小以后节点的值，左边的子节点大于以后节点的值(这里值是基于本人的算法规定而定的，比方 hash 值)。

均衡树的层级构造：均衡二叉树的查问性能和树的层级 (高度 h) 成反比，h 值越小查问越快。为了保障树的构造左右两端数据大抵均衡。升高二叉树的查问难度个别会采纳一种算法机制实现节点数据结构的均衡，实现了这种算法的有比方 Treap、红黑树。应用均衡二叉树能保证数据的左右两边的节点层级相差不会大于 1，通过这样防止树形构造因为删除减少变成线性链表影响查问效率，保证数据均衡的状况下查找数据的速度近于二分法查找：

3️⃣均衡二叉树特点：
①非叶子节点最多领有两个子节点。
②非叶子节点值大于右边子节点、小于左边子节点。
③树的左右两边的层级数相差不会大于 1。
④没有值相等反复的节点。

三、红黑树

1️⃣为什么有了均衡树还须要红黑树？
尽管均衡树解决了二叉查找树进化为近似链表的毛病，可能把查找时间管制在 O(logn)，不过却不是最佳的，因为均衡树要求每个节点的左子树和右子树的高度差至少等于 1，这个要求切实是太严了，导致每次进行插入 / 删除节点的时候，简直都会毁坏均衡树的第二个规定，进而都须要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的均衡树。

2️⃣红黑树的个性
显然，如果在插入、删除很频繁的场景中，均衡树须要频繁调整，这会使均衡树的性能大打折扣，为了解决这个问题，于是有了红黑树，红黑树具备如下特点：
①每个节点或者是彩色，或者是红色。
②根节点是彩色。
③每个叶子节点(NIL) 是彩色。[留神：这里叶子节点，是指为空 (NIL 或 NULL) 的叶子节点]
④如果一个节点是红色的，则它的子节点必须是彩色的。
⑤从一个节点到该节点的子孙节点的所有门路上蕴含雷同数目的黑节点。[这里指到叶子节点的门路]

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

3️⃣红黑树的应用场景
java 中应用到红黑树的有 TreeSet 和 JDK1.8 的 HashMap。红黑树的插入和删除都要满足以上 5 个个性，操作非常复杂，为什么要应用红黑树？起因：
红黑树是一种均衡树，简单的定义和规定都是为了保障树的平衡性。如果树不保障平衡性就是下图：很显然这就变成一个链表了。

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

四、B 树(B-tree)

 B 树和 B -tree，其实是同一种树。

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

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

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

3️⃣B 树的查问流程
如要从上图中找到 E，查找流程如下：
①获取根节点的关键字进行比拟，以后根节点关键字为 M，E<M(26 个字母程序)，所以往找到指向右边的子节点(二分法规定，左小右大，右边放小于以后节点值的子节点、左边放大于以后节点值的子节点)。
②拿到关键字 D 和 G，D<E<G 所以间接找到 D 和 G 两头的节点。
③拿到 E 和 F，因为 E =E，所以间接返回关键字和指针信息(如果树结构外面没有蕴含所要查找的节点则返回 null)。

4️⃣B 树的插入节点流程
定义一个 5 阶树(均衡 5 路查找树)，当初要把 3、8、31、11、23、29、50、28 这些数字构建出一个 5 阶树进去。遵循规定：
①节点拆分规定：以后是要组成一个 5 路查找树，那么此时 m =5，要害字数必须 <=5-1(这里要害字数 >4 就要进行节点拆分)。
②排序规定：满足节点自身比右边节点大，比左边节点小。

先插入 3、8、31、11：

再插入 23、29：

再插入 50、28：

5️⃣B 树节点的删除

规定：
①节点合并规定：以后是要组成一个 5 路查找树，那么此时 m =5，要害字数必须大于等于 ceil(5/2)(这里要害字数 <2 就要进行节点合并)。
②满足节点自身比右边节点大，比左边节点小的排序规定。

③要害字数小于二时先从子节点取，子节点没有符合条件时就向父节点取，取两头值往父节点放。

特点：
B 树绝对于均衡二叉树的不同是，每个节点蕴含的关键字增多了，特地是在 B 树利用到数据库中的时候，数据库充分利用了磁盘块的原理 (磁盘数据存储是采纳块的模式存储的，每个块的大小为 4K，每次 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/3m)。
②B+ 树节点满时就会决裂，而 B * 树节点满时会查看兄弟节点是否满(因为每个节点都有指向兄弟的指针)，如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从以后节点和兄弟节点各拿出 1 / 3 的数据创立一个新的节点进去。

2️⃣特点
在 B + 树的根底上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，能够向兄弟节点转移关键字的个性使得 B * 树额合成次数变得更少；

七、总结

1️⃣雷同思维和策略
从均衡二叉树、B 树、B+ 树、B* 树总体来看它们的贯彻的思维是雷同的，都是采纳二分法和数据均衡策略来晋升查找数据的速度。

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

作者：日常更新
链接：https://www.jianshu.com/p/b59…

感觉有用的话，点赞、关注、谢谢激励！！