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 . <EOS>