Technologies are provided for using an index in one region of a storage device to track modifications to data stored in another region of the storage device. The index can be stored in a first storage region using a first storage format, and data items can be stored in a second storage region using a second storage format. The index can map logical identifiers for data items to locations in the second storage region where the data items are stored. Instead of modifying a data item in the second storage device region, an entry in the index can be updated to mark the data item as deleted. Requests for data items can be reconciled using the index before returning the requested data items. Storage locations in the second region that are associated with index entries that are marked as deleted can be reclaimed and used to store additional data items.