Binary Radix Trees
We can generalize the binary search method described above as a tree structure. The tree will contain two types of nodes: test nodes and terminal nodes. Each test node in the tree tests one bit in the number. Whether the bit is a zero or a one determines which of two lower-level nodes is selected as the next node. Starting at the top of the tree, the first node tests the first bit in the number (the leftmost bit). The second layer in the tree has two test nodes, one of which is selected if the first bit was a zero and the other if it was a one. The third layer has four nodes, the fourth layer has eight nodes, and so on, until the tenth layer has 512 test nodes. The eleventh layer is the last layer in this tree and has 1,024 terminal entries. The terminal node uniquely identifies the value of the unknown number.
To find a number, we start at the top of the tree and test the bits from left to right. Each level in the tree tests one of the bits. After 10 tests, we are at one of the terminal nodes and have uniquely identified the number. We have just described a binary tree. It is a balanced tree, because all nodes are present. In a table search, not all nodes need be present, because not all entities in the table are present. In fact, not all the bits in the number need to be tested, meaning some of the levels need not be present. Such a tree would be called a binary radix tree to distinguish it from a binary tree, which has all levels. An example will illustrate how the AS/400 uses binary radix trees to implement the machine indexes.
Figure 6.4 shows a simple file with nine records. The ordering of this file is by arrival sequence. Each record has several fields, only a few of which are shown. One of the fields, the name field, is to be used as the key for this file. An index over this file has been built and is also shown in the figure. Each entry in the index has only two fields: the key field and the logical record address. The nine entries in the index are sorted in key sequence. In this example, the keys are sorted alphabetically, with Baker as the first entry and Wu as the last entry. The logical record address field indicates the relative position of the corresponding record in the original file. The relative position always starts with zero for the first record. The entry for Baker identifies Baker’s record as the seventh record in the file.
Figure 6.4 Example of a Simple File and Index
The exact form of this logical record address varies in an AS/400 depending on how the index is being used. For example, in an earlier discussion we saw that each entry in a data-space index segment has a key and a relative address. That relative address contains the data-space number, the identification of the data-space records segment, and the ordinal number for the entry. This relative address uniquely identifies the record associated with the key. Other uses of an index have other forms of relative addresses.
Let’s use this index to create a binary radix tree. Figure 6.5 shows the index from Figure 6.4 with the key field expanded in EBCDIC. The index is shown both in hexadecimal and in binary form. For example, the first letter in the name Baker has the hexadecimal representation of C2. C2 in binary is 11000010. The second letter in the name Baker has the hexadecimal representation C1 (11000001 in binary). Each key is laid out in memory as a string of ones and zeros as shown in the figure.
Figure 6.5 Binary Representation of Key Fields
We can now use the binary representations of the keys in memory to create a binary radix tree. The technique used to build the tree is to add one key at a time. We first search the bit string for each new entry from left to right to find the first bit that differs in the new key from other keys currently in the tree. Suppose Baker is the only entry in the tree and we want to add Barns. From Figure 6.5, we can see that the first bit (always scanning from left to right) that differs is the fifth bit of the third byte. If we had only the two entries Baker and Barns in the tree, we could distinguish one from the other by just testing the fifth bit of the third byte. If this bit is a zero, the entry is for Baker. If the bit is a one, the entry is for Barns. In a similar way, if we now want to add Carson to the tree, the first bit from the left that differs from either Baker or Barns is the eighth bit of the first byte.
Figure 6.6 shows the sequence for building the tree. Step 1 has only a terminal node for Baker in the tree. A terminal node contains some text (BAKER in this case) and the logical record address of 006. Step 2 puts Barns into the tree. Here a test node has been added just above Baker in the tree to test bit 5 of the third byte. A test node contains common text (BA) from the keys and the identification of the bit to test in the next byte. In our example with two bytes of common text (BA), we know the bit to be tested is in the next, or the third, byte, without having to explicitly identify the byte. The pattern for selecting the next node is always to take the left node if the tested bit is a zero and take the right node if the bit is a one. A second terminal node for Barns has been added to the right of the first terminal node with the logical record address 007. Note that with the common text removed, these terminal nodes now contain only the remaining text in the names (KER and RNS for Baker and Barns, respectively).
Figure 6.6 Building a Binary Radix Tree
Step 3 puts Carson into the tree. A new test node has been added to test the eighth bit of the first byte. This new test node has no common text. If the test shows the eighth bit of the first byte is a zero, then the Baker/Barns test node on the left is the next node to be checked. If the eighth bit of the first byte is a one, then the terminal node on the right for Carson is the next node. Again, this terminal node contains text (CARSON) and the logical record address 008.
Figure 6.7 shows the whole tree with all nine keys included. The test node at the top of the tree is called the root node.4 Although this is an example of a relatively small index, it illustrates many of the characteristics of a binary radix tree.
4Computer science trees always seem to grow upside down. Who else would put the root at the top with the branches spreading down?
Figure 6.7 Binary Radix Tree Example
)
)
)
)
){kind=link}
){kind=link}
){kind=link}
){kind=link}