Trie hashing with controlled load |
| |
| Authors: | Litwin WA Roussopoulos N Levy G Hong W |
| |
| Affiliation: | Dept. of Comput. Sci., Maryland Univ., College Park, MD; |
| |
| Abstract: | Trie hashing (TH), a primary key access method for storing and accessing records of dynamic files, is discussed. The key address is computed through a trie. A key search usually requires only one disk access when the trie is in core and two disk accesses for very large files when the trie must be on disk. A refinement to trie hashing, trie hashing with controlled load (THCL), is presented. It is designed to control the load factor of a TH file as tightly as that of a B-tree file, allows high load factor of up to 100% for ordered insertions, and increases the load factor for random insertions from 70% to over 85%. It is shown that these properties make trie hashing preferable to a B-tree |
| |
| Keywords: | |
|
|
