A pruned TRIE to index a sorted file and its evaluation

摘要

One of the main performance criteria in a data base management system is data access speed. This speed depends on many factors such as technology, memory organization, access paths… Among those problems, we are interested in indexing a sorted file. An important improvement of the system performance is expected if the index is resident in main memory. We present a TRIE structure [Knuth], the main feature of which is compactness. An analysis of this structure average size is proposed, under different assumptions. Placing this work in the framework of the data base machine VERSO [VERSO], we show that we can maintain the index resident in main memory.