![next](http://lcm.csa.iisc.ernet.in/dsa/next_motif.gif)
![up](http://lcm.csa.iisc.ernet.in/dsa/up_motif.gif)
Next:5.4.2
Complexity of B-tree OperationsUp:5.4
B-TreesPrevious:5.4
B-Trees
5.4.1 Definition of B-Trees
A B-tree of order m is an m-ary search tree
with the following properties:
(p1, k1, p2, k2,...,
km - 1, pm)
where
-
pi
-
is a pointer to the ith child, 1
i
m
-
ki
-
Key values, 1
i
m
- 1, which are in the sorted order, k1
< k2 < ... < km - 1,
such that
-
all keys in the subtree pointed to by p1 are less than
k1
-
For 2
i
m
- 1, all keys in the subtree pointed to by pi are greater
than or equal to ki - 1 and less than ki
-
All keys in the subtree pointed to by pm are greater
than (or equal to) km - 1
Figure 5.27: Insertion and deletion in B-trees: An example
![\begin{figure}\par\centerline{\psfig{figure=figures/Fbtree2.ps,height=6in}}\end{figure}](img274.gif) |
![next](http://lcm.csa.iisc.ernet.in/dsa/next_motif.gif)
![up](http://lcm.csa.iisc.ernet.in/dsa/up_motif.gif)
Next:5.4.2
Complexity of B-tree OperationsUp:5.4
B-TreesPrevious:5.4
B-Trees
eEL,CSA_Dept,IISc,Bangalore