Next:5.4.2
Complexity of Btree OperationsUp:5.4
BTreesPrevious:5.4
BTrees
5.4.1 Definition of BTrees
A Btree of order m is an mary search tree
with the following properties:
(p_{1}, k_{1}, p_{2}, k_{2},...,
k_{m  1}, p_{m})
where

p_{i}

is a pointer to the i^{th} child, 1 i m

k_{i}

Key values, 1 i m
 1, which are in the sorted order, k_{1}
< k_{2} < ^{... }< k_{m  1},
such that

all keys in the subtree pointed to by p_{1} are less than
k_{1}

For 2 i m
 1, all keys in the subtree pointed to by p_{i} are greater
than or equal to k_{i  1} and less than k_{i}

All keys in the subtree pointed to by p_{m} are greater
than (or equal to) k_{m  1}
Figure 5.27: Insertion and deletion in Btrees: An example

Next:5.4.2
Complexity of Btree OperationsUp:5.4
BTreesPrevious:5.4
BTrees
eEL,CSA_Dept,IISc,Bangalore