经典btree# 经典btree
btree的演进
BST
|
+---+--------+
| |
AVL 2-3 Tree
|
B-Tree
二分搜索树
二分搜索树(BST)是一种有序的内存数据结构，可以用来高效地进行键值查找。二分搜索树由多个节点组成，每个树节点由一个键、一个与该键关联的值以及两个子节点指针(因此称为二分)组成。二分搜索树从称为根节点的单一节点开始。一棵二分搜索树中只能有一个根节点。
搜索示意图
树平衡
插入操作并不会遵循任何特定模式，元素插入可能导致树不平衡的情况(即它的一个分支比另一个分支长)。最差的情况最终得到一棵病态树(pathologicaltree)，它看起来更像一个链表，此时我们得到的不是期望的对数时间复杂度，而是线性时间复杂度。
健康树复杂度0(log 2n)
4
/ \
2 6
/ \ / \
1 3 5 7
病态树 复杂度0(n)
1
\
2
\
3
\
4
\
5
\
6
\
7
AVL
AVL 提出了树旋转解决树平衡的算法。用于改进病态的树深度。降低复杂度。
分为四种旋转模型
1.左旋（LL旋转）：在右右情况下使用。
2. 右旋（RR旋转）：在左左情况下使用。
3. 左右旋（LR旋转）：在左右情况下使用，先左旋再右旋。
4. 右左旋（RL旋转）：在右左情况下使用，先右旋再左旋。
RR型失衡
当插入30时，失衡状态
10
\
20
\
30
旋转操作：左旋
平衡因子：10:右子树高度2 - 左子树高度0 = 2 (失衡!)
- 将节点20提升为新的根节点。
- 节点10成为节点20的左子树。
- 节点20原来的左子树（如果有）将成为节点10的右子树（这里没有，所以不用动）。
- 节点30保持不变（作为节点20的右子树）。
LL 型失衡
当插入50时候
30
/
20
/
10
旋转操作：右旋
平衡因子：30：左子树高度2 - 右子树高度0 = 2 (失衡!)
1、将节点20提升为新的根节点
2、节点30成为节点20的右子树
3、节点20原来的右子树（如果有）将成为节点30的左子树（此处无）
4、节点10保持不变（作为节点20的左子树）
LR型失衡
30
/
10
\
20
旋转操作：LR旋转
平衡因子：30：左子树高度2 - 右子树高度0 = 2 (失衡!)
先左旋(10)：
1、将节点20提升为10的位置
2、节点10成为20的左子树
3、节点20原来的左子树成为10的右子树（此处无）
再右旋(30)：
4、将节点20提升为新的根节点
5、节点30成为20的右子树
6、节点10成为20的左子树
RL型失衡
10
\
30
/
20
旋转操作：
平衡因子：10:右子树高度2 - 左子树高度0 = 2 (失衡!)
先右旋：
1、将节点20提升为30的位置
2、节点30成为20的右子树
3、节点20原来的右子树成为30的左子树（此处无）
再左旋(10)：
4、将节点20提升为新的根节点
5、节点10成为20的左子树
6、节点30成为20的右子树
旋转后结构
20
/ \
10 30
AVL树种其缺点也较为明显
1、插入/删除代价高
频繁旋转：每次插入/删除后需要回溯至根节点检查平衡
最坏情况：单次操作可能触发O(log2 n)次旋转
2.、存储密度较低
指针开销大：每个节点有2个指针（占总空间50%以上）
2-3树
2-3树的演进中，让节点可以存储多一个键值 、指针，同样基于平衡因子算法，2-3树采用分裂方式进行树平衡。
初始模型：
[20]
/ \
[10] [30]
当插入5, 15类似 LL 型失衡
[20]
/ \
[10] [30]
/ \
[5] [15]
平衡因子：20(左子树高度2 - 右子树高度1 )= 1 (失衡!)
中间键 10 上升到父节点 [20]（形成 [10 20]）
原[5]、[15] 成为新子树
[10 20]
/ | \
[5] [15] [30]
相较于AVL 2-3树在分裂/合并上本地化平衡操作（非全局旋转），写放大缩小 。
高度控制：所有叶节点严格同层，保证树复杂度接近为O(log3 n)，且其存储效率更高。
btree
btree每个节点可以存储N键和N+1个指针，
节点在逻辑上可以分为三类
- 根节点：树的最顶层节点，唯一存在。
- 内部节点：位于根节点和叶子节点之间。
- 叶子节点：没有子节点的节点，所有键的实际存储位置。
[20]
/ \
[10] [30 40]
/ \ / | \
[5] [15] [25] [35] [45]
根节点：[20]
内部节点：[10], [30 40]
叶子节点：[5], [15], [25], [35], [45]
btree 树和我们之前提到的索引类型一样，允许在根节点、内部节点、叶节点存储数据。在以上所以类型中，每一个节点都代表着一个数据页，当大量数据扫描时，其IO请求次数会较为频繁。
复杂度算法：
假设：
阶数 m = 100 (子节点指针数)
一个节点最多存放 99 个 key
若有约 100 万（10⁶）个 key
则树的最大高度大约是：
高度 h ≈ log₁₀₀ (10⁶) = log₁₀₀ 10⁶ = 2
在btree单个节点内部，采用二分法进行查找，其复杂度为
log2 M
btree 的分裂和合并
btree 分裂
## 初始状态
[20]
/ \
[10] [30,40]
/ \ / | \
[5] [15] [25,28] [35] [45]
##插入27导致叶节点溢出
[20]
/ \
[10] [30,40]
/ \ / | \
[5] [15] [25,27,28] [35] [45] 溢出!
## 叶节点分裂
[20]
/ \
[10] [30,40]
/ \ / | \
[5] [15] [25] [27,28] [35] [45] 🔄 分裂为两个节点
父节点分裂
[20,30] 🔼 30提升
/ | \
[10] [27] [40] 🔄 分裂为三个节点
/ \ / \ | \
[5][15][25][28][35][45]
btree 合并
##初始状态：
[20]
/ \
[10] [30,40]
/ \ / | \
[5][15] [25][35][45]
## 删除25节点中只剩下一个 key
[20]
/ \
[10] [30,40]
/ \ / | \
[5][15] [] [35] [45]
## 此时违反 B-Tree 的最小要求至少要有一个 key
向父节点借 key
[20]
/ \
[10] [35,40]
/ \ / \
[5][15] [30] [45]
## 假设删除内部节点30
[20]
/ \
[10] [,40]
/ \ / | \
[5][15] [25][35][45]
## 叶节点合并
向兄弟节点借 key
[20]
/ \
[10] [40]
/ \ / \
[5][15] [25,35] [45]
在btree基础上衍生出btree+，B+ 树所有数据都存储在叶子节点，内部节点仅用于索引导航，并且叶子节点之间通过链表有序连接，因此不仅保持了 B 树的平衡结构优势，还极大优化了范围查询、磁盘访问效率和顺序遍历性能。
树结构对比总结表
| 特性 | BST（二叉搜索树） | AVL（自平衡BST） | 2-3 树 | B 树（多路平衡） | B+ 树（数据库主流） |
|---|---|---|---|---|---|
| 节点度数 | 2 | 2 | 2 或 3 | 多个（阶 M） | 多个（阶 M） |
| 是否自平衡 | 否 | 是 | 是 | 是 | 是 |
| 查询效率 | 最坏 O(n) | O(log n) | O(log n) | O(log n) | O(log n) |
| 插入删除 | 快但不平衡 | 需旋转维护 | 自动维护 | 需分裂/合并 | 类似 B 树 |
| 范围查询 | 差 | 差 | 中 | 一般 | 优秀（链式连接） |
| 存储效率 | 高（无冗余） | 高 | 一般 | 高 | 最优 |
| 磁盘友好性 | 差 | 差 | 差 | 好 | 最强（块访问） |
| 使用场景 | 编译器、语法树 | 内存数据索引 | 理论教学 | 数据库、文件系统 | 数据库主索引结构 |
