Database Reference
In-Depth Information
of branch and leaf nodes. Figure 21.2 shows a conceptual view of a
BTree index. When Oracle Database 10
searches a BTree index, it
travels from the top node, through the branches, to the leaf node in
three or four quick steps. Why three or four quick steps? From top
node to leaf nodes implies what is called a
g
. Oracle
Database BTree indexes are generally built such that there are
between 0 and 2 branch levels with a single leaf node level. In other
words, a depth-first search on a single row will read between one and
three blocks, no matter how many rows are in the index. BTree
indexes are efficient even when the number of rows indexed is in the
millions, if used correctly.
depth-first search
Bitmap Index
. A bitmap contains binary representations for each
row. A 0 bitmap value implies that a row does not have a specified
value, and a bitmap value of 1 denotes a row having the value. Bit-
maps are very likely susceptible to overflow over long periods of use
in OLTP systems and are probably best used for read-only data such
as in data warehouses. They are best suited to indexing columns that
have a small number of distinct values, such as days of the week, gen-
der, and similar columns. However, bitmap indexes have been known
to be relatively successful in large data warehouse tables with up to
thousands of distinct values.
Function-Based Index
. Contains the result of an expression precal-
culated on each row in a table and stored as the expression result in a
BTree index structure. This type of index makes queries with an
indexed expression in the WHERE clause much faster. Often, func-
tions in the WHERE clause cause the Optimizer to ignore indexes. A
function-based index provides with the Optimizer the ability to use
an index in queries that otherwise would require full table scans.
Index-Organized Table (IOT)
. Physical clustering of index and data
spaces together for a single table, in the order of the index, usually the
primary key. An IOT is a table as well as an index; the table and the
index are merged. This works better for tables that are static and fre-
quently queried on the indexed columns. However, large OLTP sys-
tems do use IOTs with some success, and these IOTs are likely to be
for tables with a small number of columns or short row length (see
Chapter 18).
Cluster
. A clustered index contains values from joined tables rather
than a single table. A cluster is a partial merge of index and data
spaces, ordered by an index, not necessarily the primary key. A cluster
is similar to an IOT except that it can be built on a join of two or
