Page 177 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 8.3 Height of B-trees

For n greater than or equal to one, the height of an n-key b-tree T of height h with a minimum
degree t greater than or equal to 2,
n + 1
h ≤ log
t
2
The worst case height is O(log n). Since the “branchiness” of a b-tree can be large compared
to many other balanced tree structures, the base of the logarithm tends to be large; therefore,
the number of nodes visited during a search tends to be smaller than required by other tree
structures. Although this does not affect the asymptotic worst case height, b-trees tend to have
smaller heights than other trees with the same asymptotic height.

8.4 Operations on B-trees

The algorithms for the search, create, and insert operations are shown below. Note that these
algorithms are single pass; in other words, they do not traverse back up the tree. Since b-trees
strive to minimize disk accesses and the nodes are usually stored on disk, this single-pass
approach will reduce the number of node visits and thus the number of disk accesses. Simpler

double-pass approaches that move back up the tree to fix violations are possible.
Since all nodes are assumed to be stored in secondary storage (disk) rather than primary storage
(memory), all references to a given node be be preceeded by a read operation denoted by Disk-
Read. Similarly, once a node is modified and it is no longer needed, it must be written out to

secondary storage with a write operation denoted by Disk-Write. The algorithms below assume
that all nodes referenced in parameters have already had a corresponding Disk-Read operation.
New nodes are created and assigned storage with the Allocate-Node call. The implementation
details of the Disk-Read, Disk-Write, and Allocate-Node functions are operating system and
implementation dependent.
B-Tree-Search(x, k)
i <- 1
while i <= n[x] and k > keyi[x]
do i <- i + 1
if i <= n[x] and k = keyi[x]
then return (x, i)
if leaf[x]
then return NIL
else Disk-Read(ci[x])
return B-Tree-Search(ci[x], k)
The search operation on a b-tree is analogous to a search on a binary tree. Instead of choosing
between a left and a right child as in a binary tree, a b-tree search must make an n-way choice.
The correct child is chosen by performing a linear search of the values in the node. After fi nding
the value greater than or equal to the desired value, the child pointer to the immediate left of
that value is followed. If all values are less than the desired value, the rightmost child pointer
is followed. Of course, the search can be terminated as soon as the desired node is found. Since
the running time of the search operation depends upon the height of the tree, B-Tree-Search is
O(logt n).
B-Tree-Create(T)
x <- Allocate-Node()

172 LOVELY PROFESSIONAL UNIVERSITY