Analysis of compact 0-complete trees: A new access method to large databases.

摘要

Computer representations often lack those ''nice properties'' which make proofs of correctness and thorough analysis possible. Compact 0-complete trees are among the rare exceptions. They maintain a strong tie with their conceptual counterpart, a special kind of binary trie, which mirrors their properties and behavior. The ability to shift the focus of analysis, as needed, between the conceptual trie structure and the actual representation enables a more flexible and more powerful set of analytical tools. We have used this paradigm in our investigation of compact 0-complete trees, and here we present some results of that research. In particular, we demonstrate correctness of some operations defined on the structure and derive the expected values of those parameters which are critical for the performance of the structure. 4 refs., 7 figs.