Additional Estimation Considerations - Relational Database Index Design and the Optimizers - page 266

7. Row length not much more than 500 bytes.
8. Nonsequential touches are considered to be random.
Although we have discussed these assumptions throughout this topic, we will
now consider the ones shown in italics in further detail.

NONLEAF INDEX PAGES IN MEMORY

So far, we have been concerned only with the lowest level of a B-tree index,
the leaf pages. We have assumed that the read time for nonleaf pages can be
ignored with current hardware, but is this a realistic assumption? Let us consider
an example with a typical fat index.

Example

Figure 15.1 shows a fat index in an operational database. The table contains
information about the policy claims made on an insurance company. How many
levels will this index have and how much space will the nonleaf pages require?

Assumptions

ž The total length of an index row, 10 columns plus system overhead, is 80
bytes.
ž All index pages, leaf as well as nonleaf, contain 10% free space after
reorganization.
ž No leaf pages are left empty at reorganization.
ž The index page size is 4 kb; if the pages are larger than this, the calculation
below can be redone—the number of levels may be less but the space
taken by the nonleaf pages will not be essentially different.
ž The DBMS does not truncate the keys stored in nonleaf pages.

BO, TYPE,
STATUS, CNO,
LNO, CNAME,
WSNO, DNO,
DATE1, DATE2

1 GB

Nonleaf 20 MB Leaf 1 GB

LETTER

2 GB

Figure 15.1 There are many
nonleaf pages in a fat index.

10,000,000 rows