Page 178 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 8: B-trees

leaf[x] <- TRUE Notes
n[x] <- 0
Disk-Write(x)
root[T] <- x
The B-Tree-Create operation creates an empty b-tree by allocating a new root node that has no
keys and is a leaf node. Only the root node is permitted to have these properties; all other nodes
must meet the criteria outlined previously. The B-Tree-Create operation runs in time O(1).
B-Tree-Split-Child(x, i, y)
z <- Allocate-Node()
leaf[z] <- leaf[y]
n[z] <- t - 1
for j <- 1 to t - 1
do keyj[z] <- keyj+t[y]
if not leaf[y]
then for j <- 1 to t
do cj[z] <- cj+t[y]
n[y] <- t - 1
for j <- n[x] + 1 downto i + 1
do cj+1[x] <- cj[x]
ci+1 <- z
for j <- n[x] downto i
do keyj+1[x] <- keyj[x]
keyi[x] <- keyt[y]
n[x] <- n[x] + 1
Disk-Write(y)
Disk-Write(z)
Disk-Write(x)
If is node becomes “too full,” it is necessary to perform a split operation. The split operation
moves the median key of node x into its parent y where x is the ith child of y. A new node, z, is
allocated, and all keys in x right of the median key are moved to z. The keys left of the median
key remain in the original node x. The new node, z, becomes the child immediately to the right
of the median key that was moved to the parent y, and the original node, x, becomes the child
immediately to the left of the median key that was moved into the parent y.
The split operation transforms a full node with 2t – 1 keys into two nodes with t - 1 keys each.

Note One key is moved into the parent node. The B-Tree-Split-Child algorithm will run
in time O(t) where t is constant.

B-Tree-Insert(T, k)
r <- root[T]
if n[r] = 2t - 1

LOVELY PROFESSIONAL UNIVERSITY 173