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

1
3
7

Add key 10
Add key 9

Le af page split

8
9

7
10
20

10

Next leaf page
split will create
two new
non-leaf pages

39

21

33

39

12

20

Figure 11.2 Leaf page split is a fast operation.

because otherwise this would mean updating the pointers in all the indexes that
have been built on the table. When many table rows have been misplaced, the
table needs to be reorganized if the table row order is important, which is often
the case for massive batch jobs that process several large tables.
As shown in Figure 11.2, the DBMS tries to add the index row for an inserted
table row in the leaf page to which it belongs, according to the index key value.
This index page may not have sufficient free space, however, in which case the
DBMS will split the leaf page; half of the index rows will be moved to a new
leaf page, as close as possible to the page being split, but in the worst case at
the end of the index. In addition to the percentage of free space left in each leaf
page, it may be possible to leave every

n

th page empty when the index is created
or reorganized, a good idea if leaf page splits are unavoidable.
When an index has an ever-increasing key value, new index rows are added
to the last leaf page, which is probably never split. Such an index may not need
any free space.
Figure 11.2 shows the index after two additional table rows have been added.
The first of these, key 10, was placed in the appropriate leaf page, free space
being available. The second, key 9, caused a leaf page split. Any further leaf
page splits would require a second nonleaf page to be created, which in turn
would require a third-level page to be built.

ARE LEAF PAGE SPLITS SERIOUS?

Splitting a leaf page requires only one extra synchronous read, 10 ms. In addition
to the two leaf pages, the DBMS must normally update only one nonleaf page,
which is probably already in memory or in the read cache.