树

二叉查找树（不平衡）

1. 某节点的左子树节点仅包含小于该节点值
2. 某节点的右子树节点仅包含大于该节点值
3. 左右子树每个也是个二叉树

image.png

但是二叉查找树存在问题，如下图：

image.png

这个畸形的树查找次数与时间复杂度度O(h)随着腿长而无线增长，由此而产生自平衡二叉树红黑树。

平衡二叉树（旋转耗时）

AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(lgn)。

AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；

但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn)。由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。

红黑树（树太高）

与AVL树相比，红黑树的查询效率会有所下降，这是因为树的平衡性变差，高度更高。

但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转。总的来说，红黑树的统计性能高于AVL。

因此，在实际应用中，AVL树的使用相对较少，而红黑树的使用非常广泛。例如，Java中的TreeMap使用红黑树存储排序键值对；Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时，使用链表，当冲突节点较多时，使用红黑树)。

但是对于数据在磁盘等辅助存储设备中的情况（如MySQL等数据库），红黑树并不擅长，因为红黑树长得还是太高了。

1. 每个节点或者是黑色，或者是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树的左旋与右旋

红黑树有两大操作:

1. recolor (重新标记黑色或红色)
2. rotation (旋转，这是树达到平衡的关键)

左左
这种情况很简单，想象这是一根绳子，手提起 P 节点，然后变色即可

image.png

左右
左旋: 使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的左孩子，然后再应用 左左情况

image.png

右右
与左左情况一样，想象成一根绳子

image.png

右左
右旋: 使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的右孩子，然后再应用 右右情况

image.png

B树：为磁盘而生

B树也称B-树(其中-不是减号)，是为磁盘等辅存设备设计的多路平衡查找树，与二叉树相比，B树的每个非叶节点可以有多个子树。
因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。

定义B树最重要的概念是阶数(Order)，对于一颗m阶B树，需要满足以下条件：

1. 每个节点最多包含 m 个子节点。
2. 如果根节点包含子节点，则至少包含 2 个子节点；除根节点外，每个非叶节点至少包含 m/2 个子节点。
3. 拥有 k 个子节点的非叶节点将包含 k - 1 条记录。
4. 所有叶节点都在同一层中。

可以看出，B树的定义，主要是对非叶结点的子节点数量和记录数量的限制。下图是一个3阶B树的例子：

image.png

B树的优势除了树高小，还有对访问局部性原理的利用。所谓局部性原理，是指当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。
B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；

B树在数据库中有一些应用，如mongodb的索引使用了B树结构

B+树

B+树的特征

1. 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引；
2. 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)；
3. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)；

image.png

在上面这棵树中，8是2,5,8的最大元素，也是叶子节点6,8的最大元素。
需要注意的是，根的最大元素15，也就相当于整个B+树的最大元素。
由于叶子节点包含了所有父节点的元素，所以叶子节点包含了全量信息。

B+树与B树对比：

1. 更少的IO次数：B+树由于中间节点不存指针，同样大小的磁盘页可以容纳更多的节点元素，树的高度就小，访问IO次数更少。
2. 由于每个节点存储的记录更多，所以对局部性原理更好，缓存命中率更高。
3. B+树的每一个叶子节点都有指向下一个叶子节点的指针，方便范围查询和全表查询：只需要从第一个叶子节点开始顺着指针一直扫描下去即可，而B树则要对树做中序遍历。
4. B+树每次查找都必须到叶子节点才能获取数据，而B树不一定，B树可以在非叶子节点上获取数据。因此B+树查找的时间更稳定。

B+的劣势在于：由于键会重复出现，因此会占用更多的空间。

从下图我们可以直观的看到B树和B+树的区别：紫红色的箭头是指向被索引的数据的指针，大红色的箭头即指向下一个叶子节点的指针。

image.png

我们假设被索引的列是主键，现在查找主键为5的记录，模拟一下查找的过程：
B树，在倒数第二层的节点中找到5后，可以立刻拿到指针获取行数据，查找停止。
B+树，在倒数第二层的节点中找到5后，由于中间节点不存有指针信息，则继续往下查找，在叶子节点中找到5，拿到指针获取行数据，查找停止。

时间复杂度

image.png

参考：https://zhuanlan.zhihu.com/p/79980618
https://www.cnblogs.com/xumBlog/p/13337687.html