A host command to deallocate a memory device is received. A logical-to-physical (L2P) status data structure associated with a logical-to-physical (L2P) data structure is invalidated. The L2P mapping data structure includes a plurality of regions. Each region comprises a set of L2P address mappings and a region identifier identifying a respective region. The L2P status data structure includes a plurality of L2P status entries. An L2P status entry comprises a region identifier identifying a region of the plurality of regions of the L2P mapping data structure and a physical address identifying a location of the region of the L2P mapping data structure stored on the memory device. A host is notified that deallocation of the memory device is completed. Invalidation of the L2P mapping data structure is initiated.