Indexes and Reorganization - Relational Database Index Design and the Optimizers - page 208

Leaf Page

Index row

Space for
X new index rows

P% of leaf page

Figure 11.4 Leaf page
split—P and X.

X = number of new index rows that can be added to a leaf page after reor-

ganization; our recommendation, as we will see later, will be X

5.
If P = 10%, leaf page size = 4K and the index rows are 200 bytes in length,
18 index rows will fit above the P% line (90% of 4K) and so X will be 2.
In addition to P and X, we need two variables to describe the growth of an
index:

=

Y = number of index rows added since index reorganization
Z = number of leaf pages immediately after reorganization
The number of leaf page splits can now be predicted by a binomial distribu-
tion, assuming the inserts are random. The EXCEL function

BINOMDIST(X,Y,1/Z,TRUE)

determines the probability of a leaf page not being split.
For example, let us assume the following: An index, after reorganization, has
1,000,000 rows and 50,000 leaf pages (Z) with P = 20%; 10,000 new index rows
are added per day (a growth rate of 1% per day); the insert pattern is random;
old rows are not deleted in the foreseeable future.
As there are 20 index rows per leaf page when 80% full, there is room for
five new index rows per leaf page. Therefore X = 5.
Will there be any leaf page splits during the first 5 days following a reorga-
nization [50,000 inserts (Y)]?

BINOMDIST(5,50000,1/50000,TRUE) = 0.9994

This means that 0.06% of leaf pages will be split during the 5-day period.
The number of leaf page splits will be 0.06% of 50,000 leaf pages = 30. The
I/O time for an index slice scan will now become ( 1 + 0 . 06 ) × ORIG, with the
assumptions listed above. This appears to be acceptable.
After 10 days (100,000 inserts), the proportion of leaf pages that have not
been split becomes

BINOMDIST(5,100000,1/50000,TRUE) = 0.9834