Page 185 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes
Example: Here is a portion of a B-tree with order 2 (nodes have at least 2 keys and 3
pointers). Nodes are delimited with [square brackets]. The keys are city names, and are kept
sorted in each node. On either side of every key are pointers linking the key to subsequent
nodes:
Start here
|
v
[ Chicago Hoboken ]
| | |
+-----------+ | +------------+
| | |
v v v
[ Aptos Boston ] [ Denver Detroit ] [ San-Jose Seattle ]
| | | | | | | | |
v v v v v v v v v
X

To find the key “Dallas”, we begin searching at the top “root” node. “Dallas” is not in the node
but sorts between “Chicago” and “Hoboken”, so we follow the middle pointer to the next node.
Again, “Dallas” is not in the node but sorts before “Denver”, so we follow that node’s fi rst
pointer down to the next node (marked with an “X”). Eventually, we will either locate the key, or
encounter a “leaf” node at the bottom level of the B-tree with no pointers to any lower nodes and
without the key we want, indicating the key is nowhere in the B-tree.
Below is another fragment of an order 1 B-tree (nodes have at least 1 key and 2 pointers). Searching

for the key “Chicago” begins at “Marin”, follows the first pointer to “Aptos” (since Chicago sorts
before Marin), then follows that node’s second pointer down to the next level (since Chicago sorts
after Aptos), as marked with an “X”.
|
v
[ Marin ]
| |
+--+ +---+
| |
v v
[ Aptos ] [ Seattle ]
| | | |
v v v v
X
Searching a B-tree for a key always begins at the root node and follows pointers from node to
node until either the key is located or the search fails because a leaf node is reached and there are
no more pointers to follow.
B-trees grow when new keys are inserted. Since the root node initially begins with just one key,
the root node is a special exception and the only node allowed to have less than n keys in an order
n B-tree.
Here is an order 2 B-tree with integer keys. Except for the special root node, order 2 requires
every node to have from 2 to 4 keys and 3 to 5 pointers. Empty slots are marked with “.”,
showing where future keys have not yet been stored in the nodes:
[ 57 . . .]
| |
+---------------+ +---------------------+
| |
v v
[ 14 40 . .] [ 72 84 . .]
| | | | | |
+--------+ | +----------+ +----------+ | +-----------+
| | | | | |
v v v v v v
[01 12 . .] [15 16 17 .] [47 56 . .] [58 60 61 .] [74 75 76 78] [85 86 99 .]

180 LOVELY PROFESSIONAL UNIVERSITY