Embodiments are provided that include receiving a search query that represents a particular table of a plurality of tables contained in a database and that includes an additional criterion. Records are contained within the tables, which are organized in a tree structure. An index of the database contains a plurality of entries, each corresponding to a respective record in the plurality of tables. A particular entry in the index includes a path string that is indicative of a location, within the tree structure, of a table that contains a record that corresponds to the particular entry. The embodiments also include determining whether the entries in the index satisfy the search query by: (i) determining that the path string of the particular entry begins with a further path string of the particular table, and (ii) responsively determining whether a particular record that corresponds to the particular entry satisfies the additional criterion.