1. A method comprising: receiving a plurality of record identifiers with each record identifier uniquely identifying a record in a database; performing cluster analysis on the records corresponding to the plurality of record identifiers to yield a plurality of clusters, with each cluster including at least one record; and constructing a database index data structure where: (i) each record identifier is represented as a leaf node; (ii) each cluster is represented as a non-leaf node; and (iii) each leaf node is related to at least one non-leaf node based upon which record identifiers belong to which clusters.