Although object-oriented database systems offer more powerful modeling capability than relational database systems, their performance suffers from the increased complexity in the data model. Recently, a lot of research has focused on mitigating this problem by building indexes over single classes, class hierarchies, or nested object hierarchies. In this paper, we pro?pose a new indexing method. It is based on the technique that employs signature files, but dif?fers from the existing methods in two aspects: (1) all the signature files are organized into a hierarchy to filter irrelevant data as early as possible; (2) a signature file itself is stored as a tree structure (called a signature tree) to speed up signature scanning. Together with the concept of query signature hierarchies, this technique reduces the search space dramatically and, therefore, improves significantly the time complexity of query evaluation.