Requirements

The B+-tree node class is a supporting class for the B+-tree class. Each B+-tree node contains up to either a leaf node containing five pieces of data or is a 5-way tree containing four pieces of data and five child pointers.

For simplicity, we will use a Boolean flag to differentiate them. In reality, you would have one base class which has a derived leaf-node class and a derived internal m-way-tree class.

For generality, we make the value 5 a class variable N. This should, assuming you are programming this correctly, make it easy to turn this into a 10-way B+-tree, or a 512-way B+-tree.

Class Specification

UML Class Diagram

B_tree_node
`-`count:Integer `-`is_leaf:Boolean `-`elements[5]:Type `-`subtrees[5]:B_tree_node
`+` create( in lf::Boolean ):B_tree_node `+` create( in first::B_tree_node, in second::B_tree_node ):B_tree_node `+` size():Integer `+` leaf():Boolean `+` full():Boolean `+` empty():Boolean `+` retrieve( in n:Integer ):Type `+` subtree( in n:Integer ):B_tree_node `+` count( in obj:Type ):Integer `+` insert( in obj:Type ):B_tree_node `+` destroy()

Description

For simplicity, this class represents both leaf nodes and internal nodes of B+-trees. As a leaf node, it simply stores an array of up to five objects. As an internal node, it stores up to four objects together with up to five pointers to other B+-tree nodes.

Member Variables

The four member variable is

-count:Integer
-is_leaf:Boolean
-elements[5]:Type
-subtrees[5]:B_tree_node

The number of elements (count) stored in the array for leaf nodes or the number of next pointers for M-way trees.
A Boolean flag is_leaf which is true if it is a leaf node.
An array of five elements.
An array of five pointers to B_tree_node objects. This array is not used if the node is a leaf node.

Note that because the two arrays are explicitly declared in the class declaration, it is not necessary to call new[] or delete[].

Member Functions

Constructors

B_tree_node( bool lf = true )

This constructor creates a new B_tree_node containing no entries or pointers. The argument (default value of true) is assigned to the member variable is_leaf. All pointers should be set to zero.

B_tree_node( B_tree_node *first, B_tree_node *second )

This constructor creates a new internal B_tree_node containing two next pointers which are the two arguments. It is not a leaf node.

Destructor

The destructor must delete all subtrees, if any.

Copy Constructor

There is no copy constructor in this class.

Assignment Operator `=`

There is no assignment operator in this class.

Accessors

This class has four accessors:

int size() const;: Returns the number of items in the tree. If it is a leaf node, it returns the number of items in the node. If it is any other node, it sums all items in all leaf nodes descendant from the current node.
bool leaf() const;: Returns true if the node is a leaf node, false otherwise. (O(1))
bool full() const;: Returns true if the node is full, false otherwise. (O(1))
bool empty() const;: Returns true if the node is empty, false otherwise. (O(1))
Type retrieve( int n ) const;: Returns the nth object stored in the array of objects in this node, if it exists, and throws an out-of-range error otherwise. n is a value between 0 and count - 1.
B_tree_node *subtree( int n ) const;: Returns the nth sub-tree in the array of trees in this node, if it exists, and throws an out-of-range error otherwise. The exception is always thrown if it is a leaf node. n is a value between 0 and count - 1.
int count( Type const & ) const;: If the node is a leaf node, it scans the array to determine if the object is in the array and returns the appropriate value. If the node is not a leaf node, then it calls the appropriate sub-tree.

Mutators

This class has one mutator:

B_tree_node *insert( Type const & );

This attempts to insert a element into the B+-tree node:

If the node is a leaf node and the node is not full, it simply places it into the correct position in the array. If the node is full before insertion, then the node creates a new B_tree_node and copies the largest three elements into that new node while the smaller three elements are kept in the current node. The address of the new node is returned.
If the node is not a leaf node, it determines which of the sub-trees the new node should be inserted into and then calls insert on that sub-tree. It then checks the return value. If the return value is 0, then return 0. Otherwise, this indicates that the sub-tree split into two, and the address returned should appear to the right of the sub-tree into which the insertion occurred. In this case, if the internal node is not full, just manipulate the entries of the arrays to insert the new sub-tree and return 0. If the current tree is already full, create a new sub-tree and copy the three sub-trees which contain the largest entries into that tree. The current node should be reset to store only the three sub-trees containing the smallest three entries.

B-Tree Nodes