TY - JOUR
T1 - Trie hashing with controlled load
JF - IEEE Transactions on Software Engineering
Y1 - 1991
A1 - Litwin,W. A
A1 - Roussopoulos, Nick
A1 - Levy,G.
A1 - Hong,W.
KW - B-tree file
KW - Computer science
KW - controlled load
KW - Databases
KW - disk access
KW - dynamic files
KW - file organisation
KW - high load factor
KW - information retrieval systems
KW - key search
KW - load factor
KW - Military computing
KW - ordered insertions
KW - Predictive models
KW - primary key access method
KW - Protocols
KW - random insertions
KW - TH file
KW - THCL
KW - Tree data structures
KW - trees (mathematics)
KW - trie hashing
AB - 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
VL - 17
SN - 0098-5589
CP - 7
M3 - 10.1109/32.83904
ER -