A new retrieval method, called compact 0-complete trees or Co-trees, was first presented on VLDB'88 conference [OrP88]. In that paper we have described the basic algorithms (eg search, insertion and deletion operators) and emphasized the usefulness of the structure for searching large files. For example, compared with B-trees [BaM72] this organization reduces the size of secondary indices (50%-80%), and hugely increases branching factor of the index tree, thus providing a reduction of number of disk accesses per exact match query. In this paper we derive the expected values of those parameters which are critical for the performance of the structure.

The analysis of the expected performance of C0-trees can be enriched and often simplified by the ability to directly translate the results obtained by examining the conceptual structure, a special kind of a binary trie, into the statements about the actual representation. In the next section we give some preliminary remarks about the binary lries, which serve as the underlying concept upon which the final slxucture is based. Then we review the abstract model, called a 0-complete tree, and link it to the binary trie by the invariant property 2.2. Finally, we introduce the actual representation, which is a compact image of its conceptual 0-complete tree. In section 3 we derive the expected values of some of the parameters that govern the performance of C0-trees. The main results of that section, expressed by theorems 3.1 and 3.2, are related to binary tries. But, using the invariant property 2.2 and the relationship between the 0-complete trees and the C0-trees, these results are easily interpreted to obtain the desired values.