Database Reference
In-Depth Information
■
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.
Note
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 B*Tree 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 B*Tree 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.
■
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 <name> 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.
Note
