Traditional indexing techniques are not well suited for complex data types such as spatial, spatio-temporal, and multimedia data types, where an instance is a composite of multiple components. In this paper we propose two indexing techniques that allow the parts of a composite object to be indexed separately, called multiple entry indexing and double indexing. We present the implementation of these approaches in the SECONDO extensible database system. The improvements in terms of performance of both approaches presented in this paper are shown in an experimental evaluation.