next up previous
Next: Queries on B-Trees Up: B-Tree Index Files Previous: B-Tree Index Files

Structure of a B tex2html_wrap_inline829 -Tree

  1. A B tex2html_wrap_inline829 -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 tex2html_wrap_inline879 , and n pointers tex2html_wrap_inline883 . Search key values in a node are kept in sorted order.

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

  3. For leaf nodes, tex2html_wrap_inline901 ( tex2html_wrap_inline903 ) points to either a file record with search key value tex2html_wrap_inline905 , 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 tex2html_wrap_inline907 (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 tex2html_wrap_inline867 pointers. The number of pointers in a node is called the fan-out of the node.

    Consider a node containing m pointers. Pointer tex2html_wrap_inline901 ( tex2html_wrap_inline919 ) points to a subtree containing search key values tex2html_wrap_inline921 and tex2html_wrap_inline923 . Pointer tex2html_wrap_inline925 points to a subtree containing search key values tex2html_wrap_inline927 . Pointer tex2html_wrap_inline929 points to a subtree containing search key values tex2html_wrap_inline931 .

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

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

Osmar Zaiane
Mon Jul 13 13:28:03 PDT 1998