B-Tree Indexes
A b-tree (balanced-tree structured object) index is the default indexing method of Oracle8i. Oracle adapted this indexing method from the start. The index structure resembles a tree in that the top block is read first, then a block in the next layer—which is known as a branch block—is read, and so on, until the index block (known as a leaf block) that contains the actual ROWID is retrieved.
This balancing-structure approach helps minimize I/O. Oracle9i keeps this type of index in order by the assigned key value or values, splitting the blocks if necessary, to keep the structure in sequence. The b-tree structure is stable in that it will take the same number of read operations to retrieve any table row, whatever the size of the table structure. Figure 13.2 illustrates how these branch blocks and leaf blocks might look using the EMP table. Notice that the branch blocks simply point to other blocks associated with this same index, in which the leaf blocks (along the bottom) contain an actual ROWID. Larger indexes have many rows or levels of branch blocks. The example in Figure 13.2 would have three levels, and each level could represent an I/O to the database.
Figure 13.2. B-tree index illustration on the EMP.ENAME column.
TIP
If the tables being accessed by indexes contain gigabytes of data, you might want to consider using a larger default block size when creating the database. The larger the block size, the more of these index pointers can be read into the SGA with a single read operation. The more quickly these index pointers are read into memory, the more quickly the row(s) can be located for the application.
Oracle always traverses the index from left to right. A branch block will always point to the left-most leaf (or next level of branch blocks) block that contains the key value. This allows for Oracle to easily range-scan across several blocks with a minimal amount of I/O.
The PCTFREE parameter helps Oracle manage index space by leaving a percentage of space behind when it is known that additional rows may be added in the middle of the index. This helps Oracle because it does not have to split blocks as often, a time-consuming process for Oracle that can attribute to wasted space and Oracle having to add another level to maintain the balance. This is discussed later in this chapter in the “Tips and Techniques” section.
B-tree indexes can be based on a single column of a table or on multiple columns of a table. A key comprised of multiple columns of a table is a composite key. If the data requirements for a SQL statement are satisfied from information in an associated index, the table structure is not accessed. This is where the idea of an index-organized table (IOT) originated.