树--（二叉树、B树、B+树）

二叉树

二分法形成的树
右子树大于左子树，长于左子树
平衡二叉树：右子树比左子树高度差不超过1

image.png

算法效率 O(logN)

劣势：如果数据有删除，会导致结构错乱，极端情况下形成线性树
算法效率为O(N)

红黑树

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

5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
   这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

   
   红黑树

B 树

m阶B树
根节点最少两个子树
每个节点最多m个子节点
除根节点与叶节点外最少ceil（m/2）个节点 ceil()进一法
所有叶节点同一阶

image.png

由于B树遵循上述规则，且动态调整树结构，搜索复杂度为logb(N)

B+树

B树的变形
索引与指针的数量相同
非叶子节点不存储数据，只存储子节点指针与索引
所有叶子节点由链指针指向下一个叶子节点 ，区间取值速度加快

image.png

全盘扫描时可以只扫描叶子节点，B树需要扫描索引节点
单个数据查询，所有数据查询时间几乎相同，相对稳定

https://www.cnblogs.com/guohai-stronger/p/9225057.html