Trie Hashing with Controlled Load .

Abstract

Trie hashing is an access methods to primary key ordered dynamic files. The key address is computed through a trie. Key search needs usually one disk access since the trie may be in core and needs two accesses for very large files, when the trie has to be on the disk. We present a new variant of the method that allows to set up an arbitrary load factor for ordered insertions. In particular, one may create compact files, loaded up to 100%. We show that the capabilities of trie hashing make the method preferable to a B-tree by most of criteria that motivated the latter method supremacy over the database world.