A technique is configured to reduce an amount of memory (i.e., memory footprint) usage by each storage node of a cluster needed to store metadata while providing fast and efficient servicing of data in accordance with storage requests issued by a client of the cluster. Illustratively, a block identifier (ID) is used to identify a block of data serviced by the storage node. Metadata embodied as mappings between block IDs and locations of data blocks in the cluster are illustratively maintained in map fragments. A map fragment may be embodied as “active” map fragment or a “frozen” map fragment. An active map fragment refers to a map fragment that has space available to store a mapping, whereas a frozen map fragment refers to a map fragment that is full, i.e., has no available space for storing a mapping. In order to reduce the memory footprint of each storage node, yet still provide fast and efficient servicing of data by the node, the active map fragments are preferably maintained in memory as “in-core” data structures, whereas the frozen map fragments are paged-out and stored on storage devices of the cluster as “on-disk” map fragment structures.