Recursive hash trees

As long as there have been computers, there has also been data sets to store in those computers. Data storage and retrieval is an important responsibility of computer scientists. Sometimes a specific framework must be constructed around the unique requirements of a particular application. There is seldom a single best solution for any given data storage and search problem yet often there are many suitable existing solutions that can be integrated with any given implementation.

Despite all attempts at generalizing data management systems (DMS), many such systems lend themselves well to only a limited class of applications. Hash tables are one such DMS. This paper presents a series of assumptions that bound the applicability of hash tables and similar DMS. The chief focus of this paper is a particular variation of the standard hash table, the Recursive Hash Tree. The Recursive Hash Tree and its associated extensions are fully detailed herein.

The use of the these hash tree extensions can reduce the two most significant problems facing hash tables: scalability and data ignorance. The extensions detailed herein can increase performance in existing hash table applications. Empirical results are given in order to compose a clear image of the relative performance that can be expected from the Recursive Hash Tree. These extensions do not, however, broaden the class applicability of hash tables.