10.5* B+ trees in more detail

If we want to be able to search in a collection of records that will never change, then a linear index is a very simple and efficient data structure. This is simply a sorted array of search keys with pointers to the actual records. To search in a linear index we can simply perform a standard binary search (recall Section 1.3).

The problem is how to handle insertion into and deletion from our database. We could try to keep the core idea of storing a sorted array-based list, but make it more flexible by breaking the list into manageable chunks that are more easily updated.

• How might we do that? First, we need to decide how big the chunks should be. Since the data are on disk, it seems reasonable to store a chunk that is the size of a disk block, or a small multiple of the disk block size. If the next record to be inserted belongs to a chunk that hasn’t filled its block then we can just insert it there. The fact that this might cause other records in that chunk to move a little bit in the array is not important, since this does not cause any extra disk accesses so long as we move data within that chunk.

• But what if the chunk fills up the entire block that contains it? We could just split it in half.

• What if we want to delete a record? We could just take the deleted record out of the chunk, but we might not want a lot of near-empty chunks. So we could put adjacent chunks together if they have only a small amount of data between them. Or we could shuffle data between adjacent chunks that together contain more data.

The big problem would be how to find the desired chunk when processing a record with a given key. Perhaps some sort of tree-like structure could be used to locate the appropriate chunk? These ideas are exactly what motivate the B+ tree. The B+ tree is essentially a mechanism for managing a sorted array-based list, where the list is broken into chunks.

The most significant difference between the B+ tree and the BST or the standard B-tree is that the B+ tree stores records only at the leaf nodes. Internal nodes store key values, but these are used solely as placeholders to guide the search. This means that internal nodes are significantly different in structure from leaf nodes. Internal nodes store keys to guide the search, associating each key with a pointer to a child B+ tree node. Leaf nodes store the actual records, where the main requirement is that the leaf nodes store enough records to remain at least half full. The leaf nodes of a B+ tree are normally linked together to form a doubly linked list. Thus, the entire collection of records can be traversed in sorted order by visiting all the leaf nodes on the linked list.

Each internal node should be assumed to hold in the leftmost position an additional key that is less than or equal to any possible key value in the node’s leftmost subtree. B+ tree implementations typically store an additional dummy record in the leftmost leaf node whose key value is less than any legal key value.

Let’s see in some detail how the simplest B+ tree works. This would be the “2-3+ tree”, or a B+ tree of order 3.

Next, let’s see how to search.

Finally, let’s see an example of deleting from the “2-3+ tree”.

Now, let’s extend these ideas to a B+ tree of higher order.

B+ trees are exceptionally good for range queries. Once the first record in the range has been found, the rest of the records with keys in the range can be accessed by sequential processing of the remaining records in the first node, and then continuing down the linked list of leaf nodes as far as necessary. Search in a B+ tree is nearly identical to search in a regular B-tree, except that the search must always continue to the proper leaf node. Even if the search-key value is found in an internal node, this is only a placeholder and does not provide access to the actual record. The following visualisation illustrates how to to this for a B+ tree.

B+ tree insertion is similar to B-tree insertion. First, the leaf L that should contain the record is found. If L is not full, then the new record is added, and no other B+ tree nodes are affected. If L is already full, split it in two (dividing the records evenly among the two nodes) and promote a copy of the smallest-valued key in the newly formed right node. As with the 2-3 tree, promotion might cause the parent to split in turn, perhaps eventually leading to splitting the root and causing the B+ tree to gain a new level. B+ tree insertion keeps all leaf nodes at equal depth. The following figure illustrates the insertion process through several examples.

To delete a record R from a B+ tree, first locate the leaf L that contains R. If L is more than half full, then we need only remove R, leaving L still at least half full. This is demonstrated by the following visualisation.

If deleting a record reduces the number of records in the node below the minimum threshold (called an underflow), then we must do something to keep the node sufficiently full. The first choice is to look at the node’s adjacent siblings to determine if they have a spare record that can be used to fill the gap. If so, then enough records are transferred from the sibling so that both nodes have about the same number of records. This is done so as to delay as long as possible the next time when a delete causes this node to underflow again. This process might require that the parent node has its placeholder key value revised to reflect the true first key value in each node.

If neither sibling can lend a record to the under-full node (call it N), then N must give its records to a sibling and be removed from the tree. There is certainly room to do this, because the sibling is at most half full (remember that it had no records to contribute to the current node), and N has become less than half full because it is under-flowing. This merge process combines two subtrees of the parent, which might cause it to underflow in turn. If the last two children of the root merge together, then the tree loses a level.

The B+ tree requires that all nodes be at least half full (except for the root). Thus, the storage utilisation must be at least 50%. This is satisfactory for many implementations, but note that keeping nodes fuller will result both in less space required (because there is less empty space in the disk file) and in more efficient processing (fewer blocks on average will be read into memory because the amount of information in each block is greater).

Finally, here is an example of building a B+ tree of order five. You can compare this to the example above of building a tree of order four with the same records.