Using Objects

B Trees

It is sometimes necessary to store a set of data so large that it cannot fit in memory. This section introduces B-trees (B for balanced), which are commonly used in database programs. A B-tree is similar to a red-black tree (Section 14.4), but it goes to great lengths to minimize the number of disk accesses needed to find, insert, or delete an element.

A typical B-tree is shown in Figure 17-34.

Figure 17-34. A B-tree.

A B-tree is defined as follows:

• A node can hold more than one element. There are upper and lower limits on the number of elements, to be explained shortly.
• The number of children that an internal node has is always one more than the number of elements it has.
• The children are interlaced with the elements. All of the elements in the subtree rooted at a child are greater than the element to the left of that child and less than the element to the right.
• All of the leaves are on the same level. This ensures that the tree is balanced.

The limit on node sizes depends on a constant m. In Figure 17-34, m is 2. No internal node has more than 2m children. No internal node (except possibly the root) has fewer than m children. The number of elements in a node (other than the root) is between m 1 and 2m 1. We define the size of a node to be one more than the number of elements it has. For an internal node, the size is the number of children. A node of size m is called minimal. A node of size 2m is called full.

We use m = 2 in our diagrams so that they'll fit on the page. In practice, m is much larger, perhaps 200. This is because it is not much more expensive to read (or write) a bunch of data than a single element. We'd like a node to be as large as possible, but still small enough that we can read it in one disk access.

Having large nodes also makes the tree extremely shallow. This reduces the number of nodes examined in a search, which in turn reduces the number of disk accesses. The number of elements on each level increases exponentially with depth (Figure 17-35). If m = 200, then level 2 alone could contain nearly 64 million elementsand we can find any of them in only three disk accesses! This fabulous performance justifies the complicated coding required for B-trees.

Each of the Set operations (search, insertion, and deletion) is accomplished in one downward pass through the tree. In the worst case, therefore, each operation makes a number of disk accesses proportional to the height of the tree. The height of a B-tree is proportional to logm n. When m is large, the tree is very short.

Search

Searching a B-tree is much like searching a binary search tree. We first examine the root to see if the element in question is there; if not, we descend to the appropriate child. This continues until either we find the target or we try to descend from a leaf (in which case we give up).

Insertion

As with a red-black tree, we have to do some acrobatics when inserting an element into a B-tree to make sure we still have a B-tree when we're done. Specifically, every node has to have an acceptable number of elements, and all of the leaves have to be at the same level.

In the simplest case, the tree consists of a single nonfull node. We just insert the new element in the right place (Figure 17-36).

Figure 17-36. When a B-tree consists of a single nonfull node (left), a new element can be inserted directly into this node.

In general, the root is not a leaf, so we have to descend to another node (Figure 17-37).

Figure 17-37. Inserting 6 in a B-tree. The target is not present in the root, we have to descend to a leaf.

What if we now want to insert 5? It belongs in the right leaf, but there's no room. In this case, we first split the leaf into two nodes, moving the middle element up into the parent (Figure 17-38). A full node has exactly enough elements to remove one and leave enough elements to make two minimal nodes.

Figure 17-38. Inserting 5 into a B-tree. The right leaf is full, so we have to split it (middle) before we can insert the target.

Notice that the parent node gains an element as a result of the splitting. To make sure that this does not cause a further overflow, we always split a full node before descending into it to insert. If the root splits, the tree becomes taller. Binary search trees, in contrast, become taller by adding new leaves.

Deletion

Removing an element from a leaf is trivial (Figure 17-39).

Figure 17-39. Deleting 2 from a leaf.

What if the leaf is minimal? This isn't a problem, because we always make sure a node is nonminimal before descending into it to delete. The root is an exception, because it is allowed to have fewer elements than other nodes.

Splicing an element out of an internal node is not so simple. Our first approach is similar to the deletion algorithm for binary search trees: we remove either the inorder successor or the inorder predecessor of the target and copy it into the target's old location (Figure 17-40).

Figure 17-40. Deleting 3 from a B-tree. The target is present in an internal node, so we replace it with (in this case) its inorder predecessor.

Sometimes it is not possible to remove a predecessor or successor, because they are both in minimal nodes. In this case, we have to merge the two children (Figure 17-41). Merging is like splitting in reverse.

Figure 17-41. Deleting 2 from a B-tree. It cannot be replaced by a predecessor or successor, so its children are merged.

When two siblings are merged, their parent loses an element. The elements from the two minimal siblings, plus one element from their parent, just barely fit into a full node. If (as in Figure 17-41) the root loses its last element, the tree becomes shorter.

There are still more cases to handle. If the target is not present in the current node, we have to descend to a child. If that child is minimal, we have to make it larger before descending. If the child has a nonminimal sibling, we can enlarge the child with a rotation (Figure 17-42), which is similar to the rotations used in red-black trees (Section 14.4).

Figure 17-42. Deleting 4 from a B-tree. The node containing the target is minimal, so we can't descend into it (left). We make it larger by performing a right rotation, moving 2 up into the parent and 3 down into the right child (middle). Now we can descend into the node and delete 4 (right).

If the child has no nonminimal siblings, we can't rotate in another element. In this case, we merge the child with one of its siblings.

Implementation

We now provide a working implementation of B-trees storing ints. This code demonstrates the key ideas and complexities of B-trees. A professional implementation would store more general objects, such as employee records.

We begin with the BTreeNode class. Each node has elements and (unless it is a leaf) children. In any other data structure, we would have references to child objects. We don't want to do that here, because we want each BTreeNode stored in a separate file. We keep an id number for each node. The node with id 37, for example, is stored in the file b37.node. Each node knows its own id and the ids of its children.

In our representation, each BTreeNode contains an int id and two ArrayLists, data and children (Figure 17-43). In a leaf, children is null.

Figure 17-43. A B-tree node (top) is represented by an instance of the BTreeNode class (bottom). This node has size 3. Note the indices of the arrays.

(This item is displayed on page 499 in the print version)

Before we get to the code for the BTreeNode class, we have to address the question of how we will generate these id numbers. It seems clear that we want a counter that keeps track of the next available id. Whenever we get a new id, we increment the counter. If this counter is a variable in a method, we'll get the same id every time we run the method, which is no good. A nonstatic field isn't much better, because each instance will generate its own sequence of ids. A static field almost does the trick, but it will start from scratch every time we start the program, causing us to overwrite files we saved previously.

The only way we can make this work is to save the counter in a file. This way, when the program starts, it can read the value of the counter from the file and pick up where we left off. The class IdGenerator (Figure 17-44) uses a tiny file id to store this single int. The constant BTree.DIR specifies the directory where all of the files will live.

Figure 17-44. Every time we invoke IdGenerator.nextId(), we get a new id number, even if we have restarted our program since the last time we invoked it.

Now we can get started on the BTreeNode class (Figure 17-45). Since we'll be writing BTreeNodes to disk, the class implements Serializable. The constant HALF_MAX is the number m mentioned previously. There is no field for size; the size of a node is computed by invoking size() on data and adding one (line 32).

Figure 17-45. Beginning of the BTreeNode class. We use the version of ArrayList from java.util because we need its constructor accepting a capacity (lines 24 and 26) and one of its add() methods (used later in this section).

The methods for reading and writing BTreeNodes to disk are given in Figure 17-46. Because they involve the disk, these methods (and any others that invoke them) are extremely expensive. If any exception occurs, we catch it and crash, because it's almost certainly an IOException about which we can't do anything.

Figure 17-46. BTreeNode methods for disk access.

Some additional convenience methods are given in Figure 17-47.

Figure 17-47. More methods from the BTreeNode class.

We will need more methods in BTreeNode, but let's look at the BTree class (Figure 17-48). A BTree has only one field: the id of the root node. The BTree object is stored in the file btree. Our implementation supports only a single B-tree at any one time, although it could be easily modified to store each tree in a different directory.

Figure 17-48. Easy parts of the BTree class.

There are two parts to searching. We have to be able to find an element within a node, and we have to be able to find an element within an entire tree.

To search for an element within a node, we use the indexOf() method from the BTreeNode class (Figure 17-49). If target is present in the node, indexOf() returns its index in the node's data ArrayList. If not, indexOf() returns a noninteger indicating which subtree to search next. For example, if target belongs in subtree 1, indexOf() returns 1.5.

Figure 17-49. The indexOf() method from the BTreeNode class returns a double.

To search the entire tree, we use the contains() method in the BTree class (Figure 17-50), which invokes indexOf(). On line 6, the result d is converted to an int i. If d is an integer, i is the index of target in data. Otherwise, i is the index of the child to which we want to descend.

Figure 17-50. The contains() method from the BTree class.

For insertion, we begin with the add() method from the BTree class (Figure 17-51).

Figure 17-51. The add() method from the BTree class.

If the root is full, add() invokes a second constructor for BTreeNode, which splits the root and returns the new parent (Figure 17-52). Recall that the statement this(false), on line 6, invokes the constructor from Figure 17-45.

Figure 17-52. A second constructor for the BTreeNode class.

We now look at our first complicated method, add() from BTreeNode (Figure 17-53). This method descends to the proper node and adds target locally to that node. On lines 34 and 36, addToLocally() invokes a version of the add() method from the java.util.ArrayList class that inserts an element at a particular location, shifting all subsequent elements to the right.

Figure 17-53. The add() and addLocally() methods from BTreeNode.

Splitting a child is handled by the splitChild() method (Figure 17-54). On line 7, this method removes the middle element from child (shifting all subsequent elements to the left) and adds it to the parent.

Figure 17-54. The splitChild() and createRightSibling() methods from BTreeNode.

The two loops on lines 1921 and 2325 of createRightSibling() are not as efficient as they could be. Since each invocation of remove() on an ArrayList takes linear time, the total time for each of these lists is quadratic. This is not too big a problem, because it is quadratic in the size of a node (which is limited to 2 * HALF_MAX) rather than the number of elements in the B-tree. More importantly, this work is all being done in memory, so it is dwarfed by the cost of a disk access. A professional implementation would probably improve the efficiency of this method at the expense of code clarity.

Finally, we turn to the really nasty part: deletion. The remove() method from BTree (Figure 17-55) seems innocent enough.

Figure 17-55. The remove() method from BTree.

This invokes the remove() method from BTreeNode (Figure 17-56). There are three possibilities here: this is a leaf (lines 812), target is present but this is not a leaf (lines 1314), or target belongs in a subtree (lines 1516). The first case is trivial; we just have to remove target from data. The other two cases are somewhat hairier, so they are delegated to other methods.

We have to make sure every node is nonminimal before we descend into it. This is accomplished with rotation and merging. These operations are complicated, because there are so many special cases. To find a sibling from which we can rotate an element, we have to examine the left and right siblings; if they are both minimal, we have to merge. Worse yet, the leftmost child has no left sibling and the rightmost child has no right sibling, so we need special code to avoid ArrayIndexOutOfBoundsExceptions in these cases.

Figure 17-56. The remove() method from BTreeNode.

We first address removeFromInternalNode() (Figure 17-57). As in a binary search tree, our plan is to replace target with its inorder predecessor or successor. We'd like to take something from a subtree with a nonminimal root, which might be to the left or to the right of target. If both of the children next to target are minimal, we have to merge them.

Figure 17-57. The removeFromInternalNode() and mergeChildren() methods from BTreeNode.

Removing the leftmost element in a subtree sounds easy enough, so the length of the method (Figure 17-58) may be surprising. The problem is that we might encounter a minimal node on the way down. If so, we make it larger by rotating in an element from its sibling (line 14) or, if the sibling is also minimal, merging it with its sibling (line 12).

Figure 17-58. The removeLeftmost() and rotateLeft() methods from BTreeNode.

Removing the rightmost element involves the same issues (Figure 17-59).

Figure 17-59. The removeRightmost() and rotateRight() methods from BTreeNode.

Good news: now that we've laid all the groundwork for rotation and merging, only the removeFromChild() method (Figure 17-60) remains. This one is so long because we have to handle the special cases where target belongs in the first child, the last child, or one in between. In any case, we might be able to rotate an element in from a sibling, or we might have to merge.

It goes without saying that B-trees are difficult to implement and debug. Their ability to find any element in a database of billions with a handful of disk accesses justifies this effort.

Figure 17-60. The removeFromChild() method from BTreeNode.

Exercises