各种树形结构的对比

二叉树

特点：
左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大。

如图：

平衡二叉树(avl树)

https://blog.csdn.net/bjweimengshu/article/details/106774187

1. 具有二叉查找树的全部特性。
2. 每个节点的左子树和右子树的高度差至多等于1

2-3树

https://mp.weixin.qq.com/s/yDBlQofHk8Yh3cXvInocUw
2-3树是一种非常巧妙的结构，在保持树结构的基础上，它允许在一个节点中可以有两个元素，等元素数量等于3个时候再进行调整。通过这种方式呢，来保证整个二叉搜索树的平衡性。

红黑树

https://zhuanlan.zhihu.com/p/139907457

1. 结点是红色或黑色。
2. 根结点是黑色。
3. 所有叶子都是黑色。（叶子是 NIL 结点）。
4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）。

5. 任意一节点到每个叶子节点的路径都包含数量相同的黑节点

   
   

b树

https://zhuanlan.zhihu.com/p/54084335

b树的概念太繁琐先不讲，演示一下b树的查找流程

如上图我要从上图中找到E字母，查找流程如下：

1. 获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；

2. 拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；

3. 拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）

b+树

https://zhuanlan.zhihu.com/p/54102723

B+树的特征：

1. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。