Databases Reference
In-Depth Information
Additional space is reserved for additional ''overflow'' records.
■
To determine where to insert a particular record of the file, the record's key value
is converted by a ''hashing routine'' into one of the reserved record locations on
the disk.
■
To subsequently find and retrieve the record, the same hashing routine is applied
to the key value during the search.
■
Say, for example, that our company has 50 salespersons and that we have
reserved enough space on the disk for their 50 records. There are many hashing
routines but the most common is the ''division-remainder method.'' In the division-
remainder method, we divide the key value of the record that we want to insert or
retrieve by the number of record locations that we have reserved. Remember long
division, with its ''quotient'' and ''remainder?'' We perform the division, discard
the quotient, and use the remainder to tell us where to locate the record. Why the
remainder? Because the remainder is tailor-made for pointing to one of the storage
locations. If, as in this example, we have 50 storage locations and divide a key value
by that number, 50, we will get a remainder that is a whole number between 0 and
49. The value of the quotient doesn't matter. If we number the 50 storage locations
0-49 and store a record at the location dictated by its ''hashed'' key value, we have
clearly developed a way to store and then locate the records, and a very fast way,
at that! There's only one problem. More than one key value can hash to the same
location. When this happens, we say that a ''
collision
'' has occurred, and the two
key values involved are known as ''synonyms.''
Figure 8.18 shows a storage area that can hold 50 salesperson records plus
space for
overflow records
. (We will not go into how to map this space onto the
cylinders and tracks of a disk, but it can be done easily.) The main record storage
locations are numbered 0-49; the overflow locations begin at position 50. An
Record
Location
Salesperson
Number
Salesperson
Name
Synonym
Pointer
0
11
361
Carlyle
36
186
Adams
50
49
50
51
52
53
54
436
236
James
Stein
51
-1
F I G U R E 8.18
The Salesperson file stored
as a hashed file
Search WWH ::
Custom Search