B+ Tree Design Requirements

Like the binomial trees of Part 1, the degree of the root of a member of a B tree family is often used structures in the B tree family based on the degree of the root. A B+ tree of order m is typically implemented as an m-ary tree, where the degree of the root of any subtree is m, and leaf nodes do not have any space reserved for children.

To facilitate exhaustive testing, you will implement a B+ of order $order$, where the parameter $order$ represents the degree of each node. Your B+ trees must be constructed using the following rules and conventions; no exceptions can or will be made.

• Internal nodes: must always contain between floor($(order-1)/2$) and $order-1$ (non-null) guides, inclusive, with exactly one more child than the number of guides at all times. This implies between ceiling($order/2$) and $order$ non-empty child subtrees per node, inclusive.

• Leaf nodes: must always contain between ceiling($(order-1)/2$) and $order-1$ (non-null) keys, inclusive. A leaf must not contain $order$ keys!

• Remember the root is an exception, in that it never has a lower bound on the number of guides or keys it contains. Furthermore, the root node is defined to be either a leaf or an internal node that has at least two (2) non-empty subtrees.

• Actual search keys (leaf data values) must be unique. However, no such restriction exists within the set of acceptable guide values, and guide values may match keys. So, to accommodate such data value replication, we adopt the convention that a guide (internal node data value) must be less that or equal to the data values (guide or key) in the to the right of it and below it. There are no other rules regarding the selection of guide values (!).

These rules ARE mandatory, meaning that no credit will be given for the B+ tree if these rules are not observed Just like the f-heap, there can be multiple B+ trees of a given order that are correct; so, we will exploit your adherence to the above criteria to grade your B+ tree, since grading by diff-ing with a sample output is impossible.

Web Accessibility