Database Reference
In-Depth Information
The technique is applied as follows:
When a record is first written, its address is determined and
logged into the index (lookup) table.
When a record is to be retrieved, the index is consulted for its
exact location.
The technique has three significant advantages: Table lookup is a very efficient way
of storing small to medium sized files. Additionally, the technique is simple and easy
to implement. Finally, the technique avoids the problem of collision (by presumably
addressing it up front). For these reasons, the technique is widely used in database
management system (DBMS) suites and operating systems.
The approach has two problems: Firstly, storing a data file requires management of
two separate physical files on the storage medium. Secondly, as the size of the data file
grows, so does the size of the index (table lookup) file.
A2.2.3 Division-Remainder
The division-remainder technique prescribes that you divide the key value by an
appropriate number, then use the remainder of the division as the address for the record.
In computer science, we refer to the operation that yields the remainder of an integer
division as the modulus (commonly abbreviated as mod). Thus,
Note:
If the divisor is N, then address space must be of minimum size N
(that is 0 to N-1).
To minimize the number of collisions, the divisor is typically a
large number that does not contain any prime factors less than 20.
For example, 997 or 1011 is preferred to 1024.
The technique is applied as follows: When a record is to be stored or retrieved,
its address is first determined via the hash function.
The technique has three significant advantages:
It is simple and easy to implement.
It is very efficient for small files.
It avoids using two physical files for a single data file.
 
Search WWH ::




Custom Search