Definition of B-Tree:
A B-tree T is a rooted tree (whose root is root[T]) having the following properties:
Every node x has the following fields:
n[x], the number of keys currently stored in node x,
the n[x] keys themselves, stored in nondecreasing order, so that key1[x] ≤ key2[x] ≤ ··· ≤ keyn[x][x],
leaf [x], a boolean value that is TRUE if x is a leaf and FALSE if x is an internal node.
Each internal node x also contains n[x]+ 1 pointers c1[x], c2[x], ..., cn[x]+1[x] to its children. Leaf nodes have no children, so their cifields are undefined.
The keys keyi[x] separate the ranges of keys stored in each subtree: if ki is any key stored in the subtree with root ci [x], then
k1 ≤ key1[x] ≤ k2 ≤ key2[x] ≤··· ≤ keyn[x][x] ≤ kn[x]+1.
All leaves have the same depth, which is the tree's height h.
There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t ≥ 2 called the minimum degree of the B-tree:
Every node other than the root must have at least t - 1 keys. Every internal node other than the root thus has at least t children. If the tree is nonempty, the root must have at least one key.
Every node can contain at most 2t - 1 keys. Therefore, an internal node can have at most 2t children. We say that a node is fullif it contains exactly 2t - 1 keys.[1]
The simplest B-tree occurs when t = 2. Every internal node then has either 2, 3, or 4 children, and we have a 2-3-4 tree. In practice, however, much larger values of t are typically used.
Searching a B-tree：
B-TREE-SEARCH(x, k)
1 i ← 1
2 while i ≤ n[x] and k > keyi[x]
3 do i ← i + 1
4 if i ≤ n[x] and k = keyi[x]
5 then return (x, i)
6 if leaf [x]
7 then return NIL
8 else DISK-READ(ci[x])
9 return B-TREE-SEARCH(ci[x], k)
Creating an empty B-tree：
B-TREE-CREATE(T)
1 x ← ALLOCATE-NODE()
2 leaf[x] ← TRUE
3 n[x] ← 0
4 DISK-WRITE(x)
5 root[T] ← x
Inserting a key into a B-tree:
Splitting a node in a B-tree:
B-TREE-SPLIT-CHILD(x, i, y)
1 z ← ALLOCATE-NODE()
2 leaf[z] ← leaf[y]
3 n[z] ← t - 1
4 for j ← 1 to t - 1
5 do keyj[z] ← keyj+t[y]
6 if not leaf [y]
7 then for j ← 1 to t
8 do cj[z] ← cj+t[y]
9 n[y] ← t - 1
10 for j ← n[x] + 1 downto i + 1
11 do cj+1[x] ← cj [x]
12 ci+1[x] ← z
13 for j ← n[x] downto i
14 do keyj+1[x] ← keyj[x]
15 keyi[x] ← keyt[y]
16 n[x] ← n[x] + 1
17 DISK-WRITE(y)
18 DISK-WRITE(z)
19 DISK-WRITE(x)
Insert:
B-TREE-INSERT(T, k)
1 r ← root[T]
2 if n[r] = 2t - 1
3 then s ← ALLOCATE-NODE()
4 root[T] ← s
5 leaf[s] ← FALSE
6 n[s] ← 0
7 c1[s] ← r
8 B-TREE-SPLIT-CHILD(s, 1, r)
9 B-TREE-INSERT-NONFULL(s, k)
10 else B-TREE-INSERT-NONFULL(r, k)
Insert nonnull:
B-TREE-INSERT-NONFULL(x, k)
1 i ← n[x]
2 if leaf[x]
3 then while i ≥ 1 and k < keyi[x]
4 do keyi+1[x] ← keyi[x]
5 i ← i - 1
6 keyi+1[x] ← k
7 n[x] ← n[x] + 1
8 DISK-WRITE(x)
9 else while i ≥ 1 and k < keyi[x]
10 do i ← i - 1
11 i ← i + 1
12 DISK-READ(ci[x])
13 if n[ci[x]] = 2t - 1
14 then B-TREE-SPLIT-CHILD(x, i, ci[x])
15 if k> keyi[x]
16 then i ← i + 1
17 B-TREE-INSERT-NONFULL(ci[x], k)
other notes:
B-tree are balanced search trees designed to work well on magnetic disks or other direct-access secondary storage devices.
