A system for managing storage of data units, the system including: a data storage system configured to store multiple data blocks, at least some of the data blocks containing multiple data units and at least some of the data blocks being compressed data blocks, with at least a group of the data blocks being stored contiguously, thereby supporting a first read operation that retrieves data units from at least two adjacent data blocks in the group, the data storage system further including a compressed data store which stores data in a storage format in which the compressed data blocks are each formed by compressing multiple data units; and an interface, including at least one processor, coupled to the data storage system, and configured to perform one or more operations with respect to data units; characterised in that the operations include a delete operation that enables a specified data unit to be removed from a first compressed data block in the compressed data store by replacing the first compressed data block containing a data unit to be deleted with a second compressed data block that does not contain the deleted data unit, and stores, within the second compressed data block, information about the deleted data unit and overhead information in historical information associated with the second compressed data block, without requiring any other portions of the compressed data store to be modified, such that both the information about the deleted data unit and the overhead information are stored within the second compressed data block using storage space previously occupied by the deleted data unit so that the second compressed data block has the same size as the first compressed data block after the information about the deleted data unit and the overhead information are stored within the second compressed data block, wherein the overhead information forms part of the data block but is not the compressed data itself, with the historical information used to access other data units which remain in the compressed data block, using information interpreted according to the historical information to take into account any shifts due to any deleted data units. a data storage system configured to store multiple data blocks, at least some of the data blocks containing multiple data units and at least some of the data blocks being compressed data blocks, with at least a group of the data blocks being stored contiguously, thereby supporting a first read operation that retrieves data units from at least two adjacent data blocks in the group, the data storage system further including a compressed data store which stores data in a storage format in which the compressed data blocks are each formed by compressing multiple data units; and an interface, including at least one processor, coupled to the data storage system, and configured to perform one or more operations with respect to data units; characterised in that the operations include a delete operation that enables a specified data unit to be removed from a first compressed data block in the compressed data store by replacing the first compressed data block containing a data unit to be deleted with a second compressed data block that does not contain the deleted data unit, and stores, within the second compressed data block, information about the deleted data unit and overhead information in historical information associated with the second compressed data block, without requiring any other portions of the compressed data store to be modified, such that both the information about the deleted data unit and the overhead information are stored within the second compressed data block using storage space previously occupied by the deleted data unit so that the second compressed data block has the same size as the first compressed data block after the information about the deleted data unit and the overhead information are stored within the second compressed data block, wherein the overhead information forms part of the data block but is not the compressed data itself, with the historical information used to access other data units which remain in the compressed data block, using information interpreted according to the historical information to take into account any shifts due to any deleted data units. enables a specified data unit to be removed from a first compressed data block in the compressed data store by replacing the first compressed data block containing a data unit to be deleted with a second compressed data block that does not contain the deleted data unit, and stores, within the second compressed data block, information about the deleted data unit and overhead information in historical information associated with the second compressed data block, without requiring any other portions of the compressed data store to be modified, such that both the information about the deleted data unit and the overhead information are stored within the second compressed data block using storage space previously occupied by the deleted data unit so that the second compressed data block has the same size as the first compressed data block after the information about the deleted data unit and the overhead information are stored within the second compressed data block, wherein the overhead information forms part of the data block but is not the compressed data itself, with the historical information used to access other data units which remain in the compressed data block, using information interpreted according to the historical information to take into account any shifts due to any deleted data units.