THE PHYSICAL DESIGN PROCESS - Database Design and Development: An Essential Guide for IT Professionals - page 354

Block Addressing Block addressing is the general technique for database
records. Suppose that a file of data is allocated n blocks and that each block can
hold up to m records. That means the file may contain up to a maximum of ( m

n )
records. Each record gets placed in a specific block. To read or write to a specific
record, the DBMS addresses the block in which the record must reside. This is deter-
mined according to the way the file is organized. When a record is deleted from a
block, the space occupied by the record in the block is freed up. As more and more
records are deleted, the block may contain a number of fragmented empty spaces.
Figure 12-7 indicates the contents of a storage block.
Let us review the figure. Note the block header and the important information
the header holds. The holes shown in the figure are empty spaces resulting from
deletion of records from the block. The holes are chained together by physical
addresses so that the system software can look for appropriate contiguous empty
space for inserting a new record in a block.
Note the size of each hole. Let us say that a new record of size 1.3K has to be
inserted in the block. The system software searches for an empty space large enough
in the block to store this record. Now the first hole has enough space, and so the
record gets stored there. Let us now say that another record of size 1.8K has to be
inserted in the block. Neither of the two remaining holes has contiguous space large
enough for this second record. Where will the system software insert the block?
The system software chooses one of the two predefined options:

¥

1. Because there is no single hole large enough, place the entire new record in
the overflow block. Therefore, when the need to retrieve the record arises, the
system software will first look for it in the original block and then proceed to
the overflow block.

PAGE /
BLOCK
HEADER

Page/Block Number Overflow Page/Block

First Hole Size of largest hole

Size of this hole

Size of this hole

Size of this hole

Figure 12-7 Contents of a storage block.