A system for managing storage of compressed data units, the system including: a data storage system configured to store multiple data blocks containing multiple data units, with at least a group of the data blocks being stored contiguously, thereby supporting a first read operation that retrieves and decompresses data units from at least two adjacent data blocks in the group; and an interface, including at least one processor, coupled to the data storage system, and configured to perform: deleting a data unit by performing a delete operation that replaces a first data block containing the data unit to be deleted with a second data block that does not contain the deleted data unit, the delete operation comprising decompressing the data block into an address space, deleting the record at an address offset from the start of the data block, computing historical information that encodes the address offset and, after the record has been deleted, writing a new set of records into a portion of the memory space in which the remaining records are adjacent, without any gaps where omitted records used to be, compressing the new set of records and writing the resulting compressed data into the compressed data store; storing the historical information associated with the second data block that does not contain the deleted data unit, the historical information including the offset of the deleted data unit relative to a common reference storage location; retrieving a remaining data unit using a second read operation, different from the first read operation, by retrieving and decompressing the data unit to be read using an address of a data block containing the data unit to be read and address information interpreted based on the historical information. a data storage system configured to store multiple data blocks containing multiple data units, with at least a group of the data blocks being stored contiguously, thereby supporting a first read operation that retrieves and decompresses data units from at least two adjacent data blocks in the group; and an interface, including at least one processor, coupled to the data storage system, and configured to perform: deleting a data unit by performing a delete operation that replaces a first data block containing the data unit to be deleted with a second data block that does not contain the deleted data unit, the delete operation comprising decompressing the data block into an address space, deleting the record at an address offset from the start of the data block, computing historical information that encodes the address offset and, after the record has been deleted, writing a new set of records into a portion of the memory space in which the remaining records are adjacent, without any gaps where omitted records used to be, compressing the new set of records and writing the resulting compressed data into the compressed data store; storing the historical information associated with the second data block that does not contain the deleted data unit, the historical information including the offset of the deleted data unit relative to a common reference storage location; retrieving a remaining data unit using a second read operation, different from the first read operation, by retrieving and decompressing the data unit to be read using an address of a data block containing the data unit to be read and address information interpreted based on the historical information. deleting a data unit by performing a delete operation that replaces a first data block containing the data unit to be deleted with a second data block that does not contain the deleted data unit, the delete operation comprising decompressing the data block into an address space, deleting the record at an address offset from the start of the data block, computing historical information that encodes the address offset and, after the record has been deleted, writing a new set of records into a portion of the memory space in which the remaining records are adjacent, without any gaps where omitted records used to be, compressing the new set of records and writing the resulting compressed data into the compressed data store; storing the historical information associated with the second data block that does not contain the deleted data unit, the historical information including the offset of the deleted data unit relative to a common reference storage location; retrieving a remaining data unit using a second read operation, different from the first read operation, by retrieving and decompressing the data unit to be read using an address of a data block containing the data unit to be read and address information interpreted based on the historical information.