Trie hashing
Witold Litwin · 1981
We propose a new algorithm for hashing. Contrary to the usual hashing, ours stores the records in order. Furthermore, the file may be highly dynamic, even may be constituted entirely with insertions. The load factor is typically about 70 %. The search for a record is performed in only one disk access, for files attaining millions of records. No other algorithms providing such a fast search in an ordered file are known.