Tutorial Online

• B⁺ tree is a variation of B-tree data structure. In a B⁺ tree, data pointers are stored only at the leaf nodes of the tree. In a B⁺ tree structure of a leaf node differ from the structure of internal nodes.
• The leaf nodes have an entry for every value of the search field, along with a data pointer to the record (or to the block that contains this record).
• The leaf nodes of the B⁺ tree are linked together to provide ordered access on the search field to the records.
• Internal nodes of a B⁺ tree are used to guide the search.
• Some search field values from the leaf nodes are repeated in the internal nodes of the B⁺ tree.

Structure of Internal node

• Each internal node is of the form < P₁, K₁, P₂, K₂ . . . P_n-1, K_n-1, P_n > where K_i is the key and P_i is a tree pointer
• Within each internal node, K₁ < K₂, . . . < K_n-1
• For all search field value x in the subtree pointed at by P_i, we have K_i-1 x <= K_i.
• Each internal node has at most p tree pointers.
• Each internal node, except the root, has at least ⌈(P/2)⌉ tree pointers.

The structure of a leaf node of a B⁺ tree is shown below:

• Each leaf node is of the form <<K₁, P₁>, <K₂, P₂> . . . <K_n-1, P_n-1>, P_next>
• Within each leaf node, K₁ < K₂ . . . < K_n-1.
• P_i is a data pointer that points to the record whose search field value is K_i.
• Each leaf node has at least ⌈(P/2)⌉ values.
• All leaf nodes are at the same level.