《算法导论》第18章 B树 个人笔记

第18章 B树

18.1 B树的定义

一棵B树T是具有以下性质的有根树（根为T.root）； 1、 每个结点x有下面属性：

x.n ，当前存储在结点x中的关键字个数 x.n 个关键字本身 x.key1≤x.key2≤...≤x.keyx.n x.leaf ，一个布尔值，如果x是叶节点，则为TRUE，否则为FALSE

2、每个内部结点x还包含 x.n+1 个指向其孩子的指针 x.c1,x.c2,..,x.cx.n+1 。叶节点没有孩子，所以它们的 ci 属性没有定义 3、 关键字 x.keyi 对存储在各子树中的关键字范围加以分割：如果 ki 为任意一个存储在以 x.ci 为根的子树中的关键字，那么有

k1≤x.key1≤k2≤xkey2≤...≤x.keyx.≤kx.n+1 4、每个叶节点具有相同的深度，即树的高度h 5、每个结点所包含的关键字个数有上届和下界，用一个被称为B树的最小度数的固定整数 t≥2 来表示这些界：

除了根结点以外的每个结点必须至少有t-1个关键字。因此，除了根结点以外的每个内部结点至少有t个孩子。如果树非空，根结点至少有一个关键字。每个结点至少可包含2t-1个关键字。因此，一个内部结点至多可有2t个孩子。当一个结点恰好有2t-1个关键字时，则称该结点是满的。

定理：如果 n≥1 ，那么对任意一棵包含n个关键字、高度为h、最小度数 t≥2 的B树T，有 h≤logtn+12

18.2 B树上的基本操作

1、搜索B树

B-TREE-SEARCH(x,k) i = 1 while i<=x.n && k > x.key[i] i++ if i <= x.n and k = x.key[i] return (x,i) elif x.leaf reurn NIL else DISK-READ(x.c[i]) return B-TREE-SEARCH(x.c[i],k)

2、创建一棵空的B树

B-TREE-CREATE(T) x = ALLOCATE-NODE() x.leaf = TRUE x.n = 0 DISK-WRITE(x) T.root = x

3、向B树中插入一个关键字

分裂B树中的结点 B-TREE-SPLIT-CHILD(x, i) z = ALLOCATE-NODE() y = x.c[i] z.leaf = y.leaf z.n = t-1 for j=1 to t-1 z.key[i]=y.key[t+j] if !y.leaf for j=1 to t z.c[j]=y.c[t+j] y.n = t-1 for j = x.n+1 downto i+1 x.key[j+1] = x.key[j] x.c[i+1] = z for j = x.n downto i x.key[j+1] = x.key[j] x.key[i] = y.key[t] x.n++ DISK-WRITE(y) DISK-WRITE(z) DISK-WRITE(x) 沿树单程下行方式向B树插入关键字 B-TREE-INSERT(T,k) r = T.root if r.n == 2t-1 s = ALLOCATE-NODE() T.root = s s.leaf = FALSE s.n = 0 s.c = r B-TREE-SPLIT-CHILD(s,1) B-TREE-INSERT-NONFULL(s,k) else B-TREE-INSERT-NONFULL(r,k) B-TREE-INSERT-NONFULL(x,k) i = x.n if x.leaf while i>=1 && k<x.key[i] x.key[i+1] = x.key[i] i-- x.key[i+1] = k x.n++ DISK-WRITE(x) else while i>=1 && k<x.key[i] i-- i++ DISK-READ(x.c[i]) if x.c[i].n = 2t-1 B-TREE-SPLIT-CHILD(x,i) if k > x.key[i] i++ B-TREE-INSERT-NONFULL(x.c[i],k)