A storage system efficiently allocates storage space for data backup. An illustrative storage system comprises a storage and backup logic that manages data backup in the storage and converts a file to a hash-based directed acyclic graph (HDAG) so that a hierarchy of nodes of the HDAGs contain a hash of child nodes. The backup logic creates multiple HDAGs for one or more of a plurality of retention policies and represents directories by a first node containing a payload of metadata and weak references to roots of child nodes, and a second node containing references to the first node and to any HDAGs corresponding to files and/or directories governed by an active policy of the plurality of retention policies.