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:
• The root is either a leaf or has at least two children
• Each node, except for the root and the leaves, has between m/2 and m children
• Each path from the root to a leaf has the same length.
• The root, each internal node, and each leaf is typically a disk block.
• Each internal node has up to (m - 1) key values and up to m pointers (to children)
• The records are typically stored in leaves (in some organizations, they are also stored in internal nodes)

• Figure 5.26 shows a B-tree of order 5 in which at most 3 records fit into a leaf block .

• A B-tree can be viewed as a hierarchical index in which the root is the first level index.
• Each non-leaf node is of the form
(p1, k1, p2, k2,..., km - 1, pm)
where
pi
is a pointer to the ith child, i m
ki
Key values, 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 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

Next:5.4.2 Complexity of B-tree OperationsUp:5.4 B-TreesPrevious:5.4 B-Trees
eEL,CSA_Dept,IISc,Bangalore