| Previous | Table of Contents | Next |
We discussed the basic functions to commit or roll back changes to the database earlier in this chapter. The support for these functions exists at the MI and in the SLIC portion of the database. The MI system object that provides this support is the commit block. A commit block contains the changes made to an object under commitment control. Commit blocks are associated with processes.
Objects are added to or removed from the commit block. The commit block also holds the record locks. The COMMIT instruction at MI frees the locks. The DECOMMIT instruction, which nearly every HLL (including the OS/400 command set) calls ROLLBACK, backs out all changes made during the transaction, frees the locks, and repositions the cursor to the position at the start of the transaction.
The one final topic on the internal support for the AS/400 database is indexes. We have already seen two forms of an index. In Chapter 5, we introduced a system object called the independent index. In this chapter, we have discussed the data-space index. We said both of these system objects contain a binary radix tree.
An index provides a way to rapidly find an entry in a large table. A better definition of an index is an organized set of information to facilitate a fast search over a set of entities. An index is fundamental to many AS/400 components, or to those of any other system, for that matter. Because of this, the decision was made in the original System/38 design to create the most efficient index possible and build it into the part of the machine below the MI. In this way, all system components that need an index can use the one that is built in rather than having to create one of their own. This built-in index is called the machine index.
A machine index is useful in table searches, space addressing, and sorting. It is used in several places in the AS/400. In the database, a machine index is used in the data-space index, the journal transaction list, and the commit key list for a data-space index. Storage management uses machine indexes extensively for many of its directories. Machine indexes are also used in contexts and in authority searches. OS/400 uses the independent index object for several functions, including message handling, security, and spooling.
Some general characteristics of a machine index are that it
A simple way to understand a binary search is to think about a number-guessing game that most people have played at one time or another. The idea of the game is for one player to select a number within a range of numbers, say between one and 1,000. A second player attempts to guess the number in as few tries as possible. For each try, the second player is told whether the guess is high, low, or equal to the number.
A technique to quickly guess the number for this game is to use the binary number system. To guess a number between one and 1,000, our first guess would be 512 (29 = 512). If we are told our first guess is high, we know the number is greater than zero and less than 512, so our second guess would be 256 (28 = 256), the next lower power of 2. If our first guess was low, we know the number is greater than 512, so we select our second guess by adding 512 and 256 to get 768. The process to determine each guess is to add the next lower power of 2 to our previous guess. If the guess is high, we subtract out that power of 2 and add in the next lower one to form our new guess.
Let’s look at an example. Suppose the unknown number selected by the first player was 700. Our sequence of guesses would be 512, 768, 640, 704, 672, 688, 696, and finally 700. We would be told that our first guess was low, the second guess was high, the third guess was low, and so on. We would use this information each time to compute our next guess and eventually identify the number in eight tries.
If we look at the sequence of high and low responses from the first player in the example above, we get an interesting pattern. The sequence of responses is low, high, low, high, low, low, low, and equal. If we substitute a zero for every high response and a one for every low or equal response, we have created the value of the number in binary. Recognizing that it takes 10 bits to hold any number between one and 1,000, we can represent 700 as 1010111100. We guessed the number by working from left to right and using the high and low responses to tell us whether the bit positions contain zeros or ones.
We will always find the chosen number with this method in 10 or fewer tries. In our example, it took us only eight tries, because the number was divisible by 4, a power of 2. Notice that any odd number would always take 10 tries, one for each bit. We can calculate the maximum number of tries by computing the logarithm to the base 2 of 1,000. Another way to see this is to realize that 210 = 1024. To guess a number between one and a million using this technique requires only 20 or fewer tries.
This technique illustrates a binary search algorithm that can be used to find an entry in an index. For a balanced index with N entries, only log2 N entries must be compared during a search. A balanced structure is one where all the entries are filled in. Our number-guessing example was balanced, because all numbers are present in the series. Even for grossly unbalanced structures, the average number of comparisons is increased by less than 10 percent. A binary search algorithm works very well for a large number of entries, but it is generally not recommended for fewer than 50 entries.
| Previous | Table of Contents | Next |