Introduction - Relational Database Index Design and the Optimizers - page 5

of thousands of pages, one gigabyte (GB) or more; the read caches of disk
servers are typically even larger—64 GB, for instance. Although databases have
grown as disk storage has become cheaper, it is now realistic to assume that all
the nonleaf pages of a B-tree index will usually remain in memory or the read
cache. Only the leaf pages will normally need to be read from a disk drive; this,
of course, makes index maintenance much faster.
The assumption only root pages stay in memory leads to many obsolete and
dangerous recommendations, of which the following are just a few examples.

Myth 1: No More Than Five Index Levels

This recommendation is often made in relational literature, usually based on the
assumption that only root pages stay in memory . With current processors even
when all nonleaf pages are in the database buffer pool, each index level could
add as much as 50 microseconds ( µ s) of central processing unit (CPU) time to
an index scan. If a nonleaf page is not in the database buffer pool, but is found
in the read cache of the disk server, the elapsed time for reading the page may be
about 1 millisecond (ms). These values should be contrasted with the time taken
by a random read from a disk drive, perhaps 10 ms. To see what this effectively
means, we will take a simple illustration.
The index shown in Figure 1.1 corresponds to a 100-million-row table. There
are 100 million index rows with an average length of 100 bytes. Taking the
distributed free space into account, there are 35 index rows per leaf page. If the
DBMS does not truncate the index keys in the nonleaf pages, the number of
index entries in these pages is also 35.
The probable distribution of these pages as shown in Figure 1.1, together
with their size, can be deduced as follows:

2 entries 1 page

70 entries 2 pages

85,500
nonleaf pages

2400 entries 70 pages

83,000 entries 2,400 pages

2,900,000 entries 83,000 pages

2,900,000
leaf pages

100,000,000 index rows

Leaf

Figure 1.1 Largeindexwithsixlevels.