Page 187 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes If a node underflows, we may be able to “redistribute” keys by borrowing some from a neighboring

node. For example, in the order 3 B-tree below, the key 67 is being deleted, which causes a node to
underflow since it only has keys 66 and 88 left. So keys from the neighbor on the left are “shifted

through” the parent node and redistributed so both leaf nodes end up with 4 keys:
Before deleting 67 After deleting 67
[ xx 55 xx ] [ xx 33 xx ]
| | | |
+--------+ +--------+ +--------+ +------+
| | | |
v v v v
[22 24 26 28 33 44] [66 67 88 . . .] [22 24 26 28 . .] [44 55 66 88 . .]

But if the underflow node and the neighbor node have less than 2n keys to redistribute, the two
nodes will have to be combined. For example, here key 52 is being deleted from the B-tree below,

causing an underflow, and the neighbor node can’t afford to give up any keys for redistribution.
So one node is discarded, and the parent key moves down with the other keys to fill up a single

node:
Before deleting 52 After deleting 52

[ 35 45 55 . ] [ 35 55 . . ]
| | | | | | |
-+ | | +- -+ | +-
| | |
+-----+ +---+ |
| | |
v v v
[40 42 . .] [50 52 . .] [40 42 45 50]
In the above case, moving the key 45 out of the parent node left two keys (35 and 55) remaining.
But if the parent node only had n keys to begin with, then the parent node also would underfl ow
when the parent key was moved down to combine with the leaf key. Indeed, underflow and the

combining of nodes may propagate all the way up to the root node. When the root underfl ows,
the B-tree shrinks in height by one level, and the nodes under the old root combine to form a new
root.
The payoff of the B-tree insert and delete rules are that B-trees are always “balanced”. Searching
an unbalanced tree may require traversing an arbitrary and unpredictable number of nodes and
pointers.
An unbalanced tree of 4 nodes A balanced tree of 4 nodes
[ x x ] [ x x ]
| | | |
[ x x ] +------+ | +------+
| | | |
[ x x ] [ x x ] [ x x ] [ x x ]
|
[ x x ]
Searching a balanced tree means that all leaves are at the same depth. There is no runaway pointer
overhead. Indeed, even very large B-trees can guarantee only a small number of nodes must be

retrieved to find a given key. For example, a B-tree of 10,000,000 keys with 50 keys per node never
needs to retrieve more than 4 nodes to find any key.

182 LOVELY PROFESSIONAL UNIVERSITY