Physical Database Design

20 CHAPTER 2 Basic Indexing Methods

Deletions may result in emptying a data block or index node, which necessitates

the consolidation of two nodes into one. This may require a rewrite of the leaf index

node to reset its pointers. The empty data node can be either left alone or rewritten with

nulls, depending on the implementation. We will assume that the node where data is

deleted need not be rewritten. Occasionally the leaf or nonleaf nodes become empty

and need consolidation as well. Thus, we obtain the cost of deletion:

Delete cost for a single row (B+tree)

= search cost + rewrite data block + rewrite index block

= (h + 1) + 1 + 1

= h + 3 block accesses, 2.6

plus additional writes, if necessary, for consolidation.

Example: Cost Computation

As an ...