2.9 Describe an index scan
NOTE: the shading on this picture may not be accurate. Please click on
the picture to obtain a larger image, which is accurate.
Key points
- At least one B-tree structure (index) must already exist on the table
because the B-tree contains the pointers needed for the scan. A B-tree
consists of a single root page and a number of leaf and non-leaf pages. Leaf
pages are used to store index entries. Each leaf page consists of an index key
value and the physical address of the row in the table which has that value in
its key columns. A non-leaf page is used to store pointers to other index
pages (either leaf pages or other non-leaf pages). Typically, the root page
contains pointers to non-leaf pages (which may contain pointers to other
non-leaf pages) that eventually contain pointers to leaf pages.
- The B-tree pages are also stored in the DBEFileSet which contains the
table. For simplicity, the above illustration does not attempt to show this.
- When an index scan is performed over a table, a B-tree is traversed from
the root page down to the appropriate leaf pages for index entries that have
matching keys. Every matching index entry also contains the physical address
of the row in the table, so the row can be accessed directly using the
physical address if necessary. There are times when the row does not need to
be accessed because the key values that are stored in the index itself are
sufficient to satisfy the needs of the query.
- The I/O cost for an index scan is equal to the I/O that is needed to
search the index, plus the I/O that is needed to access the rows that qualify
for the query.
- The optimizer might choose an index scan instead of a serial scan, even
though all or most rows in the table will qualify for the query. This action
is taken so that sorting can be avoided. The optimizer might choose an index
scan when processing an
ORDER BY, GROUP BY, DISTINCT, or
UNION clause in a
SELECT statement or when performing a sort/merge join.
Page last updated on November 29, 1995
|
Printable version
