二叉树
二分法形成的树
右子树大于左子树，长于左子树
平衡二叉树：右子树比左子树高度差不超过1
image.png
算法效率 O(logN)
劣势：如果数据有删除，会导致结构错乱，极端情况下形成线性树
算法效率为O(N)
红黑树
- 节点是红色或黑色。
- 根节点是黑色
- 每个叶节点是黑色的。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
-
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
红黑树
B 树
m阶B树
根节点最少两个子树
每个节点最多m个子节点
除根节点与叶节点外最少ceil（m/2）个节点 ceil()进一法
所有叶节点同一阶
image.png
由于B树遵循上述规则，且动态调整树结构，搜索复杂度为logb(N)
B+树
B树的变形
索引与指针的数量相同
非叶子节点不存储数据，只存储子节点指针与索引
所有叶子节点由链指针指向下一个叶子节点 ，区间取值速度加快
image.png
全盘扫描时可以只扫描叶子节点，B树需要扫描索引节点
单个数据查询，所有数据查询时间几乎相同，相对稳定
