Techniques are disclosed relating to index metadata that is usable for accessing multi-level data structures. A computer system may operate a database, including maintaining a set of records having a set of corresponding keys. The computer system may create multi-level data structures that facilitate key range lookups against those records. A given multi-level data structure may store key information indicative of a subset of the corresponding keys. The computer system may create separate index metadata that is usable for accessing the multi-level data structures. The index metadata may specify indications of key information that is stored in the multi-level data structures and locations of the multi-level data structures. The computer system may perform a key range lookup that includes using the index metadata to determine a particular set of the multi-level data structures whose key information corresponds to a key range of the key range lookup.