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

up. Therefore, DBMS does linear probing and sequentially searches for the next
available empty block. That happens to be Block 36, and the employee record for
352-11-3421 is stored there. In the same way, when employee 246-15-4721 joins the
company, her record gets stored in the next available empty block, namely, Block
63. Instead of linear probing, another method for resolving collisions is to find
the appropriate address by means of applying multiple hash functions. The data
records that hash to the same storage address are known as synonyms in direct file
organization.
Now imagine that you want to retrieve the record for employee 246-15-4721. You
apply the hash function and determine that the record must be found at address 21.
However, the record is not in that block; the block contains record for employee
352-11-3421. So how does the DBMS find the record for 246-15-4721? Does it have
to search through all blocks sequentially? That would be very inefficient. The DBMS
maintains a synonym chain to link all the records that hash to the same block
address. This is a list of pointers linking the blocks in which the synonyms are stored.
Therefore, when record for 246-15-4721 is not found at address 21, the DBMS
follows the synonym chain and locates the record at address 63.
Linking of Related Data Elements
In the previous section, we mentioned pointers and linking of storage units. The
storage blocks where synonyms are stored need to be linked together by physical
addresses. Frequently in physical implementation of databases, you will come across
the need to link records by means of physical addresses or pointers. You will observe
the need for physical pointers when we discuss indexes a little later in this chapter.
Therefore, let us briefly discuss how related data elements are linked together in
physical storage.
You link two records by placing the physical address of one record as part of the
other record itself. These addresses placed in records to connect other records are
known as pointers. The list of records linked together forms a linked list. You may
link records within the same file through intrafile pointers; similarly, you may link
records in more than one file through interfile pointers.
Figure 12-9 shows a file in which the records are connected to form a linked list.
In the example illustrated in the figure, the file consists of 10 records apparently
stored in a random sequence. How can you arrange the records in the sequence of
serial numbers without moving the records? You can accomplish this by forming a
linked list of the records connecting the records in serial number sequence. Note
that the address in each record points to the next record in serial number sequence.
Also, observe the arrows pointing to the consecutive records in the linked list. The
last record in the sequence does not have to point anywhere and therefore contains
a null address in the pointer field.
What types of addresses are the addresses shown in the above figure? Are these
the actual addresses of the physical storage locations? The addresses may be of one
of two types.
Absolute addresses. Each record in the linked list contains the actual physical
address to point to the next record.