Trie hashing with controlled load
| Title | Trie hashing with controlled load |
| Publication Type | Journal Articles |
| Year of Publication | 1991 |
| Authors | Litwin WA, Roussopoulos N, Levy G, Hong W |
| Journal | IEEE Transactions on Software Engineering |
| Volume | 17 |
| Issue | 7 |
| Pagination | 678 - 691 |
| Date Published | 1991/07// |
| ISBN Number | 0098-5589 |
| Keywords | B-tree file, Computer science, controlled load, Databases, disk access, dynamic files, file organisation, high load factor, information retrieval systems, key search, load factor, Military computing, ordered insertions, Predictive models, primary key access method, Protocols, random insertions, TH file, THCL, Tree data structures, trees (mathematics), trie hashing |
| 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 |
| DOI | 10.1109/32.83904 |