In some examples, a method can involve generating data object records representing data objects in storage and storing, on a device, a lookup index including a plurality of index buckets, each index bucket being associated with a set of storage units on the device and including a respective index filter for each respective one of the set of storage units, the set of storage units containing a respective portion of the data object records, wherein each respective index filter includes at least one lookup entry for each data object record in the respective one of the set of storage units. The method can also involve receiving a data object request, and performing a lookup operation including identifying an index bucket for the data object and determining whether any of the set of storage units associated with the index bucket contains a data object record corresponding to the data object.