PERFORMANCE IMPLICATIONS OF REVERSE CHAINS WITH CHAINED PROGRESSIVE OVERFLOW FILES
Abstract
The conventional method of loading overflow records in a hash file
employing chained progressive overflow requires that the overflow
records be loaded as a linked list, with the pointers pointing to the
next record of the list. The paper deals with a variation, called
reverse chaining, where records are loaded in the normal sequence but
each record except the home address record points to the prior record of
the chain. The home address record points only to the most distant
record of the chain,
so that performance is improved for record insertion since
the entire chain does not have to be scanned. Other aspects of
performance are not affected. An analysis of the performance implications
shows that the improvement is significant.
Description
Keywords
Computer Science