Trie hashing with controlled load

Author

Litwin, Witold A. ; Roussopoulos, Nick ; Levy, Gerald ; Hong, Wang

Author_Institution

Dept. of Comput. Sci., Maryland Univ., College Park, MD, USA

Volume

17

Issue

7

fYear

1991

fDate

7/1/1991 12:00:00 AM

Firstpage

678

Lastpage

691

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

file organisation; information retrieval systems; trees (mathematics); B-tree file; TH file; THCL; controlled load; disk access; dynamic files; high load factor; key search; load factor; ordered insertions; primary key access method; random insertions; trie hashing; Computer science; Databases; Military computing; Predictive models; Protocols; Tree data structures;

fLanguage

English

Journal_Title

Software Engineering, IEEE Transactions on

Publisher

ieee

ISSN

0098-5589

Type

jour

DOI

10.1109/32.83904

Filename

83904