We can find any name that is in the tree by the method we have already described. But what about a name that is not in the tree? Suppose we try to find the name Soltis in the tree. We would test the third bit of the first byte and find it is a one. We then test the sixth bit of the first byte and find it is a zero. This takes us to the terminal node for Smith. The reason for keeping the text in the terminal node is because multiple names can map to the same terminal node. When we reach a terminal node, we have to compare the stored text with the rest of the name being searched. If there is a match, we have the correct terminal node. If not, the name being searched is not in the tree.
Another characteristic of the tree comes about because of the way we add entries to the tree. We always search the bit string for each new entry from left to right to find the first bit that differs in the new key from all other keys currently in the tree. By doing so, we assure that any path through the tree always tests bits from left to right. A test node never requires us to back up in the name: We always move forward.
The method used to insert entries also assures the tree will always have the same configuration, no matter what ordering is used to insert the entries. Further, the terminal nodes are always in keyed sequence from left to right. In our example, all the terminal nodes are in alphabetical order by the name in the key field. This is not a coincidence; it is part of the tree structure. The tree itself provides the logical keyed sequence, so the physical entries never have to be sorted.
In addition to finding and inserting entries in a tree, we also can remove an entry. This is an easy operation, because a terminal node can be pointed to by one and only one test node. Specifically, take the name to be removed, search the tree to find the terminal node, delete the terminal node, back up one test node, and delete the test node. The entry now has been removed from the tree.
Internals of a Binary Radix Tree
Internally, a binary radix tree is stored in a form that optimizes both performance and space. Phil Howard, an engineer, originally created the basic structure for the binary radix tree in the 1970s. The design he used had both the left and right child of a test node, along with possible common text, packaged together in a cluster. These clusters were arranged sequentially in memory and were referenced by their position number in the string. This eliminated the need to have addresses pointing from one node to the next.
Phil invented a very elegant mechanism to allow movement from node to node in the tree. The cluster does not contain the actual position of either the next or the previous node. Instead, the determination of the next node position or the previous node position uses an XOR operation. This allows bidirectional movement through the tree without requiring the additional space for both forward and backward linkages.
To find the position of the next node in the tree, a value stored in the current node is XORed with the position of the previous node. Obviously, the value stored in the current node is the XOR of the previous and next node positions. In this way, the next position can always be re-created if only this value and the previous node position are known. Suppose we want to move backward in the tree. By XORing the value in the current node with the position of the next node, we re-create the position of the previous node. Thus, at any point in the tree, by knowing the previous, current, and next positions, along with the contents of the current node, we can move up and down without the need to store forward and backward linkages. A simple three-entry push-down stack can store the three position values as we move through a tree.
The implementation of the binary radix tree minimizes page faults by partitioning the tree into subtrees. Formally, we should call this structure a partitioned binary radix tree. When a page becomes full, a split is made high up in the tree and new subtrees are added to the index.
Suppose, in our example, we wanted to subdivide our tree. Referring to Figure 6.7, we could put all the terminal nodes from Baker through Peters, along with their test nodes, on one page. A second page could contain the terminal nodes for Smith and Wu and the one test node that points to them.
However, we have a problem. None of the nodes contains addresses to link them to other nodes — they use relative position numbers. To go to another page in memory, we need an address. The solution is to create another type of node that contains an address and allows us to reference another page of entries. If we put the top node in our example, the root node, on a third page and let it point to the other two pages, we have partitioned our tree. The top nodes on all three pages are now root nodes for their page, and we have greatly expanded the amount of storage available for this tree.
Another advantage of this partitioning scheme is that once we enter a page while searching for a particular entry, we stay on that page through all its levels of testing (we do not bounce from page to page while doing a search). We exhaust the test nodes in our path on the page before falling through to another page. Also, because very large indexes can be searched with relatively few tests (recall that a million-entry index takes, on average, only 20 tests), it is rare to touch more that one or two pages. As a result, this scheme provides better performance than just about any other indexing scheme known.
Conclusions
An integrated database provides many benefits for the AS/400 — there is no other way to provide an equivalent level of efficiency and performance. We have discussed a number of these benefits in this chapter. Because the AS/400 database does not sit on top of the operating system, all system components can use the database facilities. The AS/400 database is not isolated in the same manner that a database is in a conventional system.
The AS/400’s database design allows applications written for different interfaces to coexist and operate using the same data. This characteristic allows the external interfaces and tool sets from other industry standard databases to be implemented directly on the AS/400. Applications written to this other database can then run directly on the AS/400, sharing data with everyone else. This is already happening, and it will become even more important in the future.
The integrated security of the AS/400 protects the database and other components in the system from unauthorized access and possible data corruption. In the next chapter, we examine this integrated security, as well as SLIC’s authorization management component.