B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。普遍运用于数据库和文件系统。B树可以减少搜索时读取磁盘的次数，从而提高搜索的效率。
B树的定义
一棵B树是具有以下性质的有根树（根为T.root）：
1. 每个结点x有下面属性：
a. x.n，当前存储在结点x中的关键字个数。
b.
x.n个关键字本身x.key1，x.key2，...，x.keyx.n，以非降序存放，使得x.key1<=x.key2<=...<=x.keyx.n。
c.
x.leaf，一个布尔值，如果x是叶结点，则为TRUE；如果x为内部结点，则为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 <= x.key2 <= ...
<= x.keyx.n <=
kx.n+1
4. 每个叶结点具有相同的深度，即树的高度h。
5. 每个结点所包含的关键字个数有上界和下界。用一个被称为B树的最小度数（minimum
degree）的固定整数t>=2来表示这些界：
a.
除了根结点以外的每个结点必须至少有t-1个关键字。因此，除了根结点以外的每个内部结点至少有t个孩子。如果树非空，根结点至少有一个关键字。
b.
每个结点至多包含2t-1个关键字。因此，一个内部结点至多可有2t个孩子。当一个结点恰好有2t-1个关键字时，称该结点是满的（full）。
关于B树高度的一个定理：
如果n>=1，那么对任意一根包含n个关键字、高度为h，最小度数t>=2的B树T，有
h<=logt[(n+1)/2]
证明不复杂，这里略。
B树上的一些基本操作
下面给出B树上的一些基本操作的伪代码。有两个约定：
1.
B树的根结点始终在主存中，这样无需对根做DISK－READ操作；然而，当根结点被改变后，需要对根结点做一次DISK－WRITE操作。
2. 任何被当作参数的结点在被传递之前，都要对它们先做一次DISK－READ操作。
搜索B树
B-TREE-SEARCH(x, k)
1 i = 1
2
while i <=
x.n and k > x.keyi
3
i = i + 1
4
if i <= x.n
and k == x.keyi
5
return (x, i)
6
else if x.leaf
7
return NIL
8 else DISK-READ(x,
ci)
9
return B-TREE-SEARCH(x.ci,
k)
B树的搜索过程很简单，从上到下搜索。
创建一棵空的B树
创建B树的过程，要用到一个辅助过程ALLOCATE-NODE，它在O(1)的时间内为一个新结点分配一个磁盘页。
B-TREE-CREATE(T)
1 x = ALLOCATE-NODE()
2 x.leaf = TRUE
3 x.n = 0
4 DISK-WRITE(x)
5 T.root = x
向B树中插入一个关键字
向B树中插入关键字，主要要考虑的就是，如果某个结点已经是满的了，那么如何去插入？解决方法就是，将满的结点（2t-1个关键字）分裂成两个子结点（分别具有t-1个关键字），然后将中间的关键字提升到父结点中。这种思路要保证其父结点必须不是满的。从后续的插入的伪代码中可以看出，插入过程中，一开始就会检查根结点是否是满的，如果是满的，则将其分裂。那么再往下查找的过程中，只要结点是满的，就可以按这种思路直接分裂，因为其父结点一定不是满的。
分裂B树中的结点
下面的伪代码中，x是被分割的节点的父结点，i表示第i个孩子。函数的效果是将x的第i个孩子（拥有2t
-
1个结点）分割成两个结点。其中y表示x的第i个孩子，z是新产生的结点。
B-TREE-SPLIT-CHILD(x, i)
1 z = ALLOCATE-NODE()
2 y = x.ci
3 z.leaf = y.leaf
4 z.n = t - 1
5 for j = 1
to t - 1
6
z.keyj = y.keyj+t
7
if not y.leaf
8
for j = 1
to t
9
z.cj = y.cj+t
10 y.n = t - 1
11
for j = x.n + 1
downto i + 1
12
x.cj+1 = x.cj
13 x.ci+1 = z
14
for j =
x.n downto i
15
x.keyj = y.keyj
16 x.keyi =
y.keyt
17 x.n = x.n + 1
18 DISK-WRITE(y)
19 DISK-WRITE(z)
20 DISK-WRITE(x)
插入关键字的主体代码
B-TREE-INSERT(T, k)
1 r = T.root
2
if r.n == 2t -
1
3
s = ALLOCATE-NODE()
4
T.root = s
5
s.leaf = FALSE
6
s.n = 0
7
s.c1 = r
8
B-TREE-SPLIT-CHILD(s, 1)
9
B-TREE-INSERT-NONFULL(s, k)
10 else
B-TREE-INSERT-NONFULL(r, k)
B-TREE-INSERT-NOFULL(x, k)
1 i = x.n
2
if x.leaf
3
while i >= 1
and k <
x.keyi
4
x.keyi + 1 = x.keyi
5
i = i - 1
6
x.keyi + 1 = k
7
x.n = x.n + 1
8
DISK-WRITE(x)
9
else while i
>= 1 and k <
x.keyi
10
i = i - 1
11
i = i + 1
12
DISK-READ(x.ci)
13
if x.ci.n == 2t - 1
14
B-TREE-SPLIT-CHILD(x, i)
15
if k > x.keyi
16
i = i + 1
17
B-TREE-INSERT-NONFULL(x.ci, k)
B树的删除
B树的删除比插入复杂一些。插入的时候，我们保证递归某个节点之前，该节点的不能是满的。删除的时候，我们要保证，当递归调用到某结点x时，x中关键字的个数至少为最小度数t。这个条件比要求的最少关键字个数多一个，因为在递归下降到更低的子结点之前，有时候需要把x中的关键字移到子结点。这个加强的条件允许在一趟下降的过程中，将一个关键字从树中删除，而无需向上回溯。如果根结点x成为一个不含任何关键字的内部结点，那么x就要被删除，x的唯一孩子x.c1成为树的新根，从而树的高度降低1。
1.
如果关键字k在结点x中，并且x是叶结点，则从x中删除k。
2. 如果关键字k在结点x中，并且x是内部结点，则做以下操作：
a.
如果结点x中前于k的子结点y至少包含t个关键字，则找出k在以y为根的子树中的前驱k’。递归地删除k’，并在x中用k’代替k。（找到k’并删除它可在沿树下降下的单过程中完成。）
b.
对称地，如果y有少于t个关键字，则检查结点x中后于k的子结点z。如果z至少有t个关键字，则找出k在以z为根的子树中的后继k’。递归地删除k’，并在x中用k’代替k。（找到k’并删除它可在沿树下降的单过程中完成。）
c. 否则，如果y和z都只含有t -
1个关键字，则将k和z的全部合并进y，这样x就失去了k和指向z的指针，并且y现在包含2t
- 1个关键字。然后释放z并递归地从y中删除k。
3.
如果关键字k当前不在内部结点x中，则确定必包含k的子树的根x.ci（如果k确实在树中）。如果x.ci只有t
-
1个关键字，必须执行步骤3a或3b来保证降至一个至少包含t个关键字的结点。然后，通过对x的某个合适的子结点进行递归而结束。
a.
如果x.ci只含有t-1个关键字，但是它的一个相邻的兄弟至少包含t个关键字，则将x中的某一个关键字降至x.ci中，将x.ci的相邻左兄弟或右兄弟的一个关键字升至x，将该兄弟中相应的孩子指针移到x.ci中，这样就使得x.ci增加了一个额外的关键字。
b.
如果x.ci以及x.ci的所有相邻兄弟都只包含了t
-
1个关键字，则将x.ci与一个兄弟合并，即将x的一个关键字移至新合并的结点，使之成为该结点的中间关键字。
另外，B树的查找、插入、删除的复杂度都是O(th) = O(t
logtn)。
B树的Java实现
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
public class BTreeextends Comparable> {
private static final int DEFAULT_T = 2;
private BTNode root;
// 最小度数
private int t;
// 非根节点的最少关键字个数
private int minKeyNum;
// 非根节点的最大关键字个数
private int maxKeyNum;
private class BTNode {
// 关键字个数
public int n = 0;
public List keys = new ArrayList(maxKeyNum);
public List children = new ArrayList(maxKeyNum + 1);
public boolean isLeaf = true;
public void insertKey(int index, E key) {
keys.add(index, key);
n ++;
if (keys.size() > maxKeyNum) {
keys.remove(maxKeyNum);
}
}
public E removeKey(int index) {
E key = keys.remove(index);
n --;
return key;
}
public void insertChild(int index, BTNode child) {
children.add(index, child);
if (children.size() > maxKeyNum + 1) {
children.remove(maxKeyNum + 1);
}
}
public BTNode removeChild(int index) {
BTNode child = children.remove(index);
return child;
}
}
public BTree() {
this(DEFAULT_T);
}
public BTree(int degree) {
if (degree < 2) {
t = DEFAULT_T;
}
this.t = degree;
this.minKeyNum = degree - 1;
this.maxKeyNum = 2 * degree - 1;
BTNode node = new BTNode();
this.root = node;
}
private void sliptChild(BTNode x, int index) {
// 新增结点
BTNode z = new BTNode();
BTNode y = x.children.get(index);
z.isLeaf = y.isLeaf;
for (int j = 0; j < minKeyNum; j++) {
z.insertKey(j, y.keys.get(j + t));
}
if (!y.isLeaf) {
for (int j = 0; j < t; j++) {
z.insertChild(j, y.children.get(j + t));
}
}
z.n = minKeyNum;
y.n = minKeyNum;
x.insertChild(index + 1, z);
x.insertKey(index, y.keys.get(minKeyNum));
}
private void insertNoFull(BTNode x, E key) {
int i = x.n - 1;
if (x.isLeaf) {
while (i >= 0 && key.compareTo(x.keys.get(i)) < 0)
i--;
x.insertKey(i + 1, key);
} else {
while (i >= 0 && key.compareTo(x.keys.get(i)) < 0)
i--;
i = i + 1;
if (x.children.get(i).n == maxKeyNum) {
sliptChild(x, i);
if (key.compareTo(x.keys.get(i)) > 0)
i = i + 1;
}
insertNoFull(x.children.get(i), key);
}
}
public void insert(E key) {
BTNode r = root;
if (root.n == maxKeyNum) {
BTNode newRoot = new BTNode();
root = newRoot;
newRoot.isLeaf = false;
newRoot.insertChild(0, r);
sliptChild(newRoot, 0);
insertNoFull(newRoot, key);
} else
insertNoFull(r, key);
}
public void delete(E key) {
delete(root, key);
}
private void delete(BTNode x, E key) {
// 该过程需要保证，对非根节点执行删除操作时，其关键字个数至少为t。
int n = x.n;
assert n >= t || x == root;
int i = 0;
while (i < n && key.compareTo(x.keys.get(i)) > 0)
i ++;
if (i < n && key.equals(x.keys.get(i))) {
if (x.isLeaf) {
// 1 如果当前结点是叶子结点，直接删除关键字
x.removeKey(i);
} else {
BTNode y = x.children.get(i);
BTNode z = x.children.get(i + 1);
if (y.n >= t) {
// 2.a
E preKey = deleteMaxKey(y);
x.keys.set(i, preKey);
} else if (z.n >= t) {
// 2.b
E nextKey = deleteMinKey(z);
x.keys.set(i, nextKey);
} else {
// 2.c
int ySize = y.n;
int zSize = z.n;
y.insertKey(ySize, key);
ySize ++;
boolean isChildLeaf = y.isLeaf;
for (int j = 0; j < zSize; j++) {
y.insertKey(ySize, z.keys.get(j));
if (! isChildLeaf) {
y.insertChild(ySize, z.children.get(j));
}
ySize ++;
}
if (! isChildLeaf) {
y.insertChild(ySize, z.children.get(zSize- 1));
}
x.removeKey(i);
x.removeChild(i + 1);
if (x.n == 0) {
root = y;
}
delete(y, key);
}
}
} else if (x.isLeaf) {
// 没有找到该关键字，直接返回
return;
} else {
BTNode child = x.children.get(i);
boolean isChildLeaf = child.isLeaf;
if (child.n >= t) {
delete(child, key);
} else if (i > 0 && x.children.get(i - 1).n >= t){
// 3.a 左兄弟满足条件
BTNode leftBrother = x.children.get(i - 1);
int leftBrotherKeyNum = leftBrother.n;
E leftBrotherLastKey = leftBrother.keys.get(leftBrotherKeyNum - 1);
child.insertKey(0, x.keys.get(i - 1));
x.keys.set(i - 1, leftBrotherLastKey);
if (!isChildLeaf) {
BTNode leftBrotherLastChild = leftBrother.children.get(leftBrotherKeyNum);
child.insertChild(0, leftBrotherLastChild);
leftBrother.removeChild(leftBrotherKeyNum);
}
leftBrother.removeKey(leftBrotherKeyNum - 1);
delete(child, key);
} else if (i < x.n && x.children.get(i + 1).n >= t) {
// 3.a 右兄弟满足条件
BTNode rightBrother = x.children.get(i + 1);
E rightBrotherFirstKey = rightBrother.keys.get(0);
int childKeyNum = child.n;
child.insertKey(childKeyNum, x.keys.get(i));
x.keys.set(i, rightBrotherFirstKey);
if (!isChildLeaf) {
BTNode rightBrotherFirstChild = rightBrother.children.get(0);
child.insertChild(childKeyNum + 1, rightBrotherFirstChild);
rightBrother.removeChild(0);
}
rightBrother.removeKey(0);
delete(child, key);
} else if (i > 0){
// 3.b 存在左兄弟，合并
BTNode leftBrother = x.children.get(i - 1);
int leftBrotherKeyNum = leftBrother.n;
leftBrother.insertKey(leftBrotherKeyNum, x.keys.get(i - 1));
leftBrotherKeyNum ++;
for (int j = 0; j < t - 1; j ++) {
leftBrother.insertKey(leftBrotherKeyNum, child.keys.get(j));
if (!isChildLeaf) {
leftBrother.insertChild(leftBrotherKeyNum, child.children.get(j));
}
leftBrotherKeyNum ++;
}
if (!isChildLeaf) {
leftBrother.insertChild(leftBrotherKeyNum, child.children.get(t - 1));
}
x.removeChild(i);
x.removeKey(i - 1);
if (x.n == 0) {
root = leftBrother;
}
delete(leftBrother, key);
} else {
// 3.b 存在右兄弟，合并
BTNode rightBrother = x.children.get(i + 1);
int childKeyNum = child.n;
child.insertKey(childKeyNum, x.keys.get(i));
childKeyNum ++;
for (int j = 0; j < t - 1; j ++) {
child.insertKey(childKeyNum, rightBrother.keys.get(j));
if (!isChildLeaf) {
child.insertChild(childKeyNum, rightBrother.children.get(j));
}
childKeyNum ++;
}
if (! isChildLeaf) {
child.insertChild(childKeyNum, rightBrother.children.get(t - 1));
}
x.removeKey(i);
x.removeChild(i + 1);
if (x.n == 0) {
root = child;
}
delete(child, key);
}
}
}
private E deleteMinKey(BTNode x) {
if (x.isLeaf) {
return x.removeKey(0);
} else {
BTNode child = x.children.get(0);
boolean isChildLeaf = child.isLeaf;
BTNode rightBrother = x.children.get(1);
if (child.n >= t) {
return deleteMinKey(child);
} else if (rightBrother.n >= t){
// 3.a
E rightBrotherFirstKey = rightBrother.keys.get(0);
int childKeyNum = child.n;
child.insertKey(childKeyNum, x.keys.get(0));
x.keys.set(0, rightBrotherFirstKey);
if (!isChildLeaf) {
BTNode rightBrotherFirstChild = rightBrother.children.get(0);
child.insertChild(childKeyNum + 1, rightBrotherFirstChild);
rightBrother.removeChild(0);
}
rightBrother.removeKey(0);
return deleteMinKey(child);
} else {
// 3.b
int childKeyNum = child.n;
child.insertKey(childKeyNum, x.keys.get(0));
childKeyNum ++;
for (int j = 0; j < t - 1; j ++) {
child.insertKey(childKeyNum, rightBrother.keys.get(j));
if (!isChildLeaf) {
child.insertChild(childKeyNum, rightBrother.children.get(j));
}
childKeyNum ++;
}
if (! isChildLeaf) {
child.insertChild(childKeyNum, rightBrother.children.get(t - 1));
}
x.removeChild(1);
x.removeKey(0);
return deleteMinKey(child);
}
}
}
private E deleteMaxKey(BTNode x) {
int keyNum = x.n;
if (x.isLeaf) {
return x.removeKey(keyNum - 1);
} else {
BTNode child = x.children.get(keyNum);
boolean isChildLeaf = child.isLeaf;
BTNode leftBrother = x.children.get(keyNum - 1);
int leftBrotherKeyNum = leftBrother.n;
if (child.n >= t) {
return deleteMaxKey(child);
} else if (leftBrother.n >= t){
// 3.a
E leftBrotherLastKey = leftBrother.keys.get(leftBrotherKeyNum - 1);
child.insertKey(0, x.keys.get(keyNum - 1));
x.keys.set(keyNum - 1, leftBrotherLastKey);
if (!isChildLeaf) {
BTNode leftBrotherLastChild = leftBrother.children.get(leftBrotherKeyNum);
child.insertChild(0, leftBrotherLastChild);
leftBrother.removeChild(leftBrotherKeyNum);
}
leftBrother.removeKey(leftBrotherKeyNum - 1);
return deleteMaxKey(child);
} else {
// 3.b
leftBrother.insertKey(leftBrotherKeyNum, x.keys.get(keyNum - 1));
leftBrotherKeyNum ++;
for (int j = 0; j < t - 1; j ++) {
leftBrother.insertKey(leftBrotherKeyNum, child.keys.get(j));
if (!isChildLeaf) {
leftBrother.insertChild(leftBrotherKeyNum, child.children.get(j));
}
leftBrotherKeyNum ++;
}
if (!isChildLeaf) {
leftBrother.insertChild(leftBrotherKeyNum, child.children.get(t - 1));
}
// 删除关键字和孩子的操作最好放在后面来执行
x.removeChild(keyNum);
x.removeKey(keyNum - 1);
return deleteMaxKey(leftBrother);
}
}
}
public void print() {
Queue queue = new LinkedBlockingQueue.BTNode>();
queue.add(root);
while (!queue.isEmpty()) {
BTNode node = queue.poll();
for (int i = 0; i < node.n; i ++) {
System.out.print(node.keys.get(i) + " ");
}
System.out.println();
if (!node.isLeaf) {
for (int i = 0; i < node.n + 1; i ++) {
queue.add(node.children.get(i));
}
}
}
}
public static void main(String[] args) {
BTree bTree = new BTree(2);
bTree.insert("F");
bTree.insert("S");
bTree.insert("Q");
bTree.insert("K");
bTree.insert("C");
bTree.insert("L");
bTree.insert("H");
bTree.insert("T");
bTree.insert("V");
bTree.insert("W");
bTree.insert("M");
bTree.insert("R");
bTree.insert("N");
bTree.insert("P");
bTree.insert("A");
bTree.insert("B");
bTree.insert("X");
bTree.insert("Y");
bTree.insert("D");
bTree.insert("Z");
bTree.insert("E");
bTree.delete("Z");
bTree.delete("W");
bTree.delete("D");
bTree.delete("H");
bTree.delete("K");
bTree.delete("A");
bTree.delete("Y");
bTree.delete("F");
bTree.delete("M");
bTree.delete("Q");
bTree.delete("R");
bTree.delete("V");
bTree.delete("P");
bTree.delete("E");
bTree.delete("B");
bTree.delete("S");
bTree.delete("N");
bTree.delete("X");
bTree.delete("T");
bTree.delete("C");
bTree.delete("L");
bTree.print();
}
}
参考资料：《算法导论》
加载中…