Structure of a B -Tree

1. A B -tree index is a multilevel index but is structured differently from that of multi-level index sequential files.
2. A typical node (Figure 11.6) contains up to n-1 search key values , and n pointers . Search key values in a node are kept in sorted order.

    
   Figure 11.6:   Typical node of a B+-tree.
   

3. For leaf nodes, ( ) points to either a file record with search key value , or a bucket of pointers to records with that search key value. Bucket structure is used if search key is not a primary key, and file is not sorted in search key order.

   Pointer (nth pointer in the leaf node) is used to chain leaf nodes together in linear order (search key order). This allows efficient sequential processing of the file.

   The range of values in each leaf do not overlap.

4. Non-leaf nodes form a multilevel index on leaf nodes.

   A non-leaf node may hold up to n pointers and must hold pointers. The number of pointers in a node is called the fan-out of the node.

   Consider a node containing m pointers. Pointer ( ) points to a subtree containing search key values and . Pointer points to a subtree containing search key values . Pointer points to a subtree containing search key values .

5. Figures 11.7 (textbook Fig. 11.8) and textbook Fig. 11.9 show B -trees for the deposit file with n=3 and n=5.

    
   Figure 11.7:   B+-tree for deposit file with n = 3.