<算法导论 (3rd)> 第十八章 - B Tree!

之前学 DBMS 的时候接触到 B Tree, 但当时懵懵懂懂我的对 B Tree 的操作也是一知半解.
今天看了书(主要是严谨的定义和完整的伪代码流程), 感触颇深, 以此博客记录一下.

B Tree 的定义:

(看上去这些定义好像很啰嗦没什么意思, 但花点时间搞清楚后, 看伪代码和下文会清晰很多.)

1. 每个节点 x 有以下的性质
   • x.n → 一个节点中关键字的个数.
   • x.key1 <= x.key2 <= x.key3, e.g. 一个节点: [A, N, O] → A < N < O
   • x.leaf → 是否为叶子节点(True/False)
2. 每个节点如果有 n 个关键字, 就有 n+1 个 指向孩子的指针 **(x.c1, x.c2, ...)**
3. 每个叶子节点, 都有相同的深度, 即 树的高度 h (为什么呢? 每个叶子节点...)
4. 对于两个相邻关键字 x.key1, x.key2 之间 (子树上) 的任意一个关键字 k, 必定有 x.key1 <= k <= x.key2
5. 最后有个很重要的概念: 最小度数 (minimum degree) → t.
   得到一个节点关键字个数限制:

B Tree 的优势:

B Tree 最大的优势: 相对较小的磁盘存取次数.
为什么呢? 因为大部分的操作的时间复杂是和 B Tree 的高度成正比的 (每次查询一个节点都需要一次磁盘访问, 例如查询一个叶子节点需要访问 h(高度) 个节点).

B Tree 的高度(具体证明见书, 其实也是等比数列的求和):

而二叉树的高度:

可以看到 B Tree 的高度的对数的底可以比 2 大很多倍, 所以总高度会比二叉树小很多, 从而避免了大量的磁盘访问:

B Tree 的搜索:

直观的说就是:

1. 遍历节点中的所有关键字, 选择分支 → 找到子节点 | 输出 None(x.leaf==True).
2. 对子节点递归做第一步操作.

B Tree 的插入 (敲重点):

1. B-TREE-INSERT(T, k)
   • 伪代码:

   第 2-8 行: 其实就是对 root 节点为 full 的情况 (x.n >= 2t+1) 做了一个特殊处理, 进行 split 操作.
   第 8 行: SPLIT 操作图解:
   

2. 调用子方法 B-TREE-INSERT-NONFULL:

上图的分析:
1. 如果是叶子节点 (x.leaf==True):
就遍历节点中的关键字, 找到正确的位置插入.
2. 否则:
- (1) 遍历节点中的关键字, 找到正确的位置(指针)
- (2) 判断该指针 指向的子节点 是否为 full
- (3) 如果是就对这个子节点做分割(split).
- (4) 递归调用 B-TREE-INSERT-NONFULL

B Tree 的删除:

(TODO)