Page 179 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes then s <- Allocate-Node()

root[T] <- s
leaf[s] <- FALSE
n[s] <- 0
c1 <- r
B-Tree-Split-Child(s, 1, r)
B-Tree-Insert-Nonfull(s, k)
else B-Tree-Insert-Nonfull(r, k)
B-Tree-Insert-Nonfull(x, k)
i <- n[x]
if leaf[x]
then while i >= 1 and k < keyi[x]
do keyi+1[x] <- keyi[x]
i <- i - 1
keyi+1[x] <- k
n[x] <- n[x] + 1
Disk-Write(x)
else while i >= and k < keyi[x]
do i <- i - 1
i <- i + 1
Disk-Read(ci[x])
if n[ci[x]] = 2t - 1
then B-Tree-Split-Child(x, i, ci[x])
if k > keyi[x]
then i <- i + 1
B-Tree-Insert-Nonfull(ci[x], k)
To perform an insertion on a b-tree, the appropriate node for the key must be located using an
algorithm similiar to B-Tree-Search. Next, the key must be inserted into the node. If the node
is not full prior to the insertion, no special action is required; however, if the node is full, the
node must be split to make room for the new key. Since splitting the node results in moving one
key to the parent node, the parent node must not be full or another split operation is required.
This process may repeat all the way up to the root and may require splitting the root node. This
approach requires two passes. The first pass locates the node where the key should be inserted;

the second pass performs any required splits on the ancestor nodes.
Since each access to a node may correspond to a costly disk access, it is desirable to avoid the
second pass by ensuring that the parent node is never full. To accomplish this, the presented
algorithm splits any full nodes encountered while descending the tree. Although this approach
may result in unecessary split operations, it guarantees that the parent never needs to be split and
eliminates the need for a second pass up the tree.

Task In twenty words or less, explain how treesort works.

174 LOVELY PROFESSIONAL UNIVERSITY