Apparatus for storing received data blocks as deduplicated data blocks, the apparatus being configured to maintain a plurality of containers, wherein a reference to a container is unique within the apparatus and each container includes one or more data segments and segment metadata for each data segment, the segment metadata including a segment identifier and a segment reference, wherein the segment identifier is unique within the container and the segment reference is unique within the apparatus, maintain a plurality of deduplicated data blocks storing received data blocks, wherein each deduplicated data block includes a plurality of identified container references, and an ordered list of one or more segment indicators, wherein each segment indicator includes a segment identifier and a container reference identifier of the container reference of the container that contains the identified data segment, the order thereof being the same as data segments of the received data block, wherein the container reference identifier is unique within the deduplicated data block, and maintain a deduplication index including a plurality of segment references, wherein each segment reference is calculated from a data segment from a received data block and is associated at least with a container reference referenced by the deduplicated data block and one unique block reference to a deduplicated data block, the apparatus being further configured to, for deleting a data block, retrieve the deduplicated data block related to the data block to be deleted, retrieve, for each container referenced by a container reference in the retrieved deduplicated data block, the segment identifiers and segment references, and search for each segment reference included in the retrieved deduplicated data block in the deduplication index, in order to retrieve its associated at least one container reference and block reference, delete the retrieved deduplicated date block and delete each container reference and block reference that matches the container reference in the data block to be deleted and a block reference of the data block to be deleted, respectively, from the deduplication index. maintain a plurality of deduplicated data blocks storing received data blocks, wherein each deduplicated data block includes a plurality of identified container references, and an ordered list of one or more segment indicators, wherein each segment indicator includes a segment identifier and a container reference identifier of the container reference of the container that contains the identified data segment, the order thereof being the same as data segments of the received data block, wherein the container reference identifier is unique within the deduplicated data block, and maintain a deduplication index including a plurality of segment references, wherein each segment reference is calculated from a data segment from a received data block and is associated at least with a container reference referenced by the deduplicated data block and one unique block reference to a deduplicated data block, the apparatus being further configured to, for deleting a data block, retrieve the deduplicated data block related to the data block to be deleted, retrieve, for each container referenced by a container reference in the retrieved deduplicated data block, the segment identifiers and segment references, and search for each segment reference included in the retrieved deduplicated data block in the deduplication index, in order to retrieve its associated at least one container reference and block reference, delete the retrieved deduplicated date block and delete each container reference and block reference that matches the container reference in the data block to be deleted and a block reference of the data block to be deleted, respectively, from the deduplication index.