Provided are a computer program product, system, and method for managing data in a storage. Each index entry in and index identifies a log address in the log of one of the records. Each record in the log includes a key and value, and the log addresses map to physical addresses in the storage. A plurality of processed log addresses in the log are processed by determining whether the index indicates that the processed log address includes a current version of the record in the log; adding the record at the processed log address to a selected log address in the log in response to determining that the index indicates that the processed log address comprises the current version of the record; and deleting a record at the physical address in the storage to which the processed log address maps.