File organization using composite perfect hashing
1989; Association for Computing Machinery; Volume: 14; Issue: 2 Linguagem: Inglês
10.1145/63500.63521
ISSN1557-4644
AutoresM. Ramakrishna, Per-Åke Larson,
Tópico(s)Caching and Content Delivery
ResumoPerfect hashing refers to hashing with no overflows. We propose and analyze a composite perfect hashing scheme for large external files. The scheme guarantees retrieval of any record in a single disk access. Insertions and deletions are simple, and the file size may vary considerably without adversely affecting the performance. A simple variant of the scheme supports efficient range searches in addition to being a completely dynamic file organization scheme. These advantages are achieved at the cost of a small amount of additional internal storage and increased cost of insertions.
Referência(s)