之前学 DBMS 的时候接触到 B Tree, 但当时懵懵懂懂我的对 B Tree 的操作也是一知半解.
今天看了书(主要是严谨的定义和完整的伪代码流程), 感触颇深, 以此博客记录一下.
B Tree 的定义:
(看上去这些定义好像很啰嗦没什么意思, 但花点时间搞清楚后, 看伪代码和下文会清晰很多.)
- 每个节点 x 有以下的性质
x.n
→ 一个节点中关键字的个数.x.key1 <= x.key2 <= x.key3
, e.g. 一个节点: [A, N, O] → A < N < Ox.leaf
→ 是否为叶子节点(True/False)
- 每个节点如果有 n 个关键字, 就有 n+1 个 指向孩子的指针 **(x.c1, x.c2, ...)**
- 每个叶子节点, 都有相同的深度, 即 树的高度 h (为什么呢? 每个叶子节点...)
- 对于两个相邻关键字 x.key1, x.key2 之间 (子树上) 的任意一个关键字 k, 必定有 x.key1 <= k <= x.key2
- 最后有个很重要的概念: 最小度数 (minimum degree) → t.
得到一个节点关键字个数限制:
B Tree 的优势:
B Tree 最大的优势: 相对较小的磁盘存取次数.
为什么呢? 因为大部分的操作的时间复杂是和 B Tree 的高度成正比的 (每次查询一个节点都需要一次磁盘访问, 例如查询一个叶子节点需要访问 h(高度) 个节点).
B Tree 的高度(具体证明见书, 其实也是等比数列的求和):
而二叉树的高度:
可以看到 B Tree 的高度的对数的底可以比 2
大很多倍, 所以总高度会比二叉树小很多, 从而避免了大量的磁盘访问:
B Tree 的搜索:
直观的说就是:
- 遍历节点中的所有关键字, 选择分支 → 找到子节点 | 输出 None(x.leaf==True).
- 对子节点递归做第一步操作.
B Tree 的插入 (敲重点):
- B-TREE-INSERT(T, k)
- 伪代码:
第 2-8 行: 其实就是对 root 节点为 full 的情况 (x.n >= 2t+1) 做了一个特殊处理, 进行 split 操作.
第 8 行: SPLIT 操作图解:
- 伪代码:
- 调用子方法 B-TREE-INSERT-NONFULL:
上图的分析:
1. 如果是叶子节点 (x.leaf==True):
就遍历节点中的关键字, 找到正确的位置插入.
2. 否则:
- (1) 遍历节点中的关键字, 找到正确的位置(指针)
- (2) 判断该指针 指向的子节点 是否为 full
- (3) 如果是就对这个子节点做分割(split).
- (4) 递归调用 B-TREE-INSERT-NONFULL
B Tree 的删除:
(TODO)