Database Reference
In-Depth Information
1
3
7
8
7
20
39
12
Add levels
until last level
is one page
(root page)
20
21
33
39
Nonleaf pages
Leaf pages
Figure 11.1 B-tree index with two levels.
useful when evaluating an index by counting touches. However, now is the time
to discuss the actual physical structure of a B-tree index.
As far back as the sixties, the indexes of file and database systems were
built as balanced trees . The small tree in Figure 11.1 has been chopped down,
the root being placed on the left, the leaves on the right.
Index rows are stored in leaf pages. Today, the typical index page size is
4 or 8 kb. The length of an index row is usually the sum of the length of the
index columns plus about 10 bytes of control information. If the total length
of an index row is 200 bytes, about 40 index rows will fit in an 8K leaf page
if the index is unique. In a nonunique index, several pointers may follow each
key value; in many DBMS products, these pointers are stored in pointer value
sequence. This is to enable the DBMS to quickly find a pointer to be deleted,
even if there are a million pointers chained to one key value. We mention this
because for historical reasons, some DBAs are worried about the impact of the
maximum pointer chain length on delete performance.
HOW THE DBMS FINDS AN INDEX ROW
Assume the optimizer decides to use the index shown in Figure 11.1 for the
SELECT shown in SQL 11.1.
SQL 11.1
SELECT
COLX
FROM
TABLE
WHERE
COLI = 12
Search WWH ::




Custom Search