The multikey type index for persistent object sets

Multikey index structures for type hierarchies are a recently discussed alternative to traditional B⁺-tree indexing schemes. We describe an efficient implementation of this alternative called the multikey type index (MT-index). A prerequisite for our approach is an optimal linearization of the type hierarchy that allows us to map queries in object type hierarchies to minimal-volume range queries in multi-attribute search structures. This provides access to an already-existing large and versatile tool-box. The outline of an index implementation by means of a multi-attribute search structure (e.g. the hB-tree or any other structure with comparable performance) is followed by an analytical performance evaluation. Selected performance figures are compared to previous approaches, in particular to the H-tree and the class hierarchy tree. The comparison results allow for practically relevant conclusions with respect to index selection based on query profiles