Page 184 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 8: B-trees

Notes

Of course, you immediately see that the parent node now contains only one key, G. This is not
acceptable. If this problem node had a sibling to its immediate left or right that had a spare key,
then we would again “borrow” a key. Suppose for the moment that the right sibling (the node
with Q X) had one more key in it somewhere to the right of Q. We would then move M down
to the node with too few keys and move the Q up where the M had been. However, the old left
subtree of Q would then have to become the right subtree of M. In other words, the N P node
would be attached via the pointer field to the right of M’s new location. Since in our example we

have no way to borrow a key from a sibling, we must again combine with the sibling, and move
down the M from the parent. In this case, the tree shrinks in height by one.

8.7 B-tree Algorithms

A B-tree is a data structure that maintains an ordered set of data and allows effi cient operations

to find, delete, insert, and browse the data. In this discussion, each piece of data stored in a
B-tree will be called a “key”, because each key is unique and can occur in the B-tree in only one
location.
A B-tree consists of “node” records containing the keys, and pointers that link the nodes of the
B-tree together.
Every B-tree is of some “order n”, meaning nodes contain from n to 2n keys, and nodes are thereby
always at least half full of keys. Keys are kept in sorted order within each node. A corresponding
list of pointers are effectively interspersed between keys to indicate where to search for a key if it
isn’t in the current node. A node containing k keys always also contains k+1 pointers.

LOVELY PROFESSIONAL UNIVERSITY 179