1. A B+-tree index is a multilevel index but is structured di erently from that of multi-level index sequential files.

2. A typical node (Figure 11.6) contains up to n - 1 search key values K1,K2,...,Kn -1, and n pointers P1, P2,...,Pn. Search key values in a node are kept in sorted order.

3. For leaf nodes, Pi (i = 1,..., n-1) points to either a file record with search key value Ki, 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 Pn (nth pointer in the leaf node) is used to chain leaf nodes together in linear order (search key order). This allows effcient 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 dn=2e pointers. The number of pointers in a node is called the fan-out of the node.

Consider a node containing m pointers. Pointer Pi (i = 2,...,m) points to a subtree containing search key values ≥ Ki-1 and < Ki. Pointer Pm points to a subtree containing search key values ≥ Km-1. Pointer P1 points to a subtree containing search key values < K1.

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.