B*Tree—or what I call conventional—indexes are the most commonly used type of indexing structure in the database. They are similar in implementation to a binary search tree. Their goal is to minimize the amount of time Oracle spends searching for data. Loosely speaking, if you have an index on a number column, then the structure might conceptually look like Figure 11-1.
Figure 11-1. Typical B*Tree index layout
Note There are block-level optimizations and compression of data that take place that make the real block structure look different from Figure 11-1. Also, the index depicted in Figure 11-1 is a nonunique index (meaning it allows duplicate key values). For example, if you wanted to find the value of 11, there are two different index entries with the value of 11.
The lowest level blocks in the tree, called leaf nodes or leaf blocks, contain every indexed key and a rowid that points to the row it is indexing. The interior blocks, above the leaf nodes, are known as branch blocks. They are used to navigate through the structure. For example, if we wanted to find the value 42 in the index, we would start at the top of the tree and go to the left. We would inspect that block and discover we needed to go to the block in the range “42..50”. This block would be the leaf block and point us to the rows that contained the number 42.
It is interesting to note that the leaf nodes of the index are actually a doubly linked list. Once we find out where to start in the leaf nodes (i.e., once we have found that first value), doing an ordered scan of values (also known as an index range scan) is very easy. We don’t have to navigate the structure anymore; we just go forward or backward through the leaf nodes as needed. That makes satisfying a predicate, such as the following, pretty simple:
where x between 20 and 30
Oracle finds the first index leaf block that contains the lowest key value that is 20 or greater, and then it just walks horizontally through the linked list of leaf nodes until it finally hits a value that is greater than 30.
There really is no such thing as a nonunique entry in a B*Tree index. In a nonunique index, Oracle simply stores the rowid by appending it to the key as an extra column with a length byte to make the key unique. For example, an index such as CREATE INDEX I ON T(X,Y) is conceptually CREATE UNIQUE INDEX I ON T(X,Y,ROWID). In a unique index, as defined by you, Oracle does not add the rowid to the index key. In a nonunique index, you will find that the data is sorted first by index key values (in the order of the index key) and then by rowid ascending. In a unique index, the data is sorted only by the index key values.
One of the properties of a BTree is that all leaf blocks should be at the same level in the tree. This level is also known as the height of the index, meaning that any traversal from the root block of the index to a leaf block will visit the same number of blocks. That is, to get to the leaf block to retrieve the first row for a query of the form “SELECT INDEXED_COL FROM T WHERE INDEXED_COL = :X” will take the same number of I/Os regardless of the value of :X that is used. In other words, the index is height balanced. Most BTree indexes will have a height of 2 or 3, even for millions of records. This means that it will take, in general, two or three I/Os to find your key in the index—which is not too bad.
Note Oracle uses two terms with slightly different meanings when referring to the number of blocks involved in traversing from an index root block to a leaf block. The first is HEIGHT, which is the number of blocks required to go from the root block to the leaf block. The HEIGHT value can be found from the INDEX_STATS view after the index has been analyzed using the ANALYZE INDEX VALIDATE STRUCTURE command. The other is BLEVEL, which is the number of branch levels and differs from HEIGHT by one (it does not count the leaf blocks). The value of BLEVEL is found in the normal dictionary tables such as USER_INDEXES after statistics have been gathered.
For example, say we have a 10,000,000-row table (see the “Setting Up Your Environment” section at the beginning of this book for details on creating BIG_TABLE) with a primary key index on a number column:
$ sqlplus eoda/foo@PDB1
SQL> select index_name, blevel, num_rows from user_indexes
The BLEVEL is 2, meaning the HEIGHT is 3, and it will take two I/Os to find a leaf (resulting in a third I/O). So, we would expect three I/Os to retrieve any given key value from this index:
SQL> set autotrace on
SQL> select id from big_table where id = 42;
The B*Tree is an excellent general-purpose indexing mechanism that works well for large and small tables and experiences little, if any, degradation in retrieval performance as the size of the underlying table grows.