A data storage device includes a write protection data structure that includes a first set of entries corresponding to a first set of ranges of memory addresses. A first indication stored in an entry, in the first set of entries, corresponds to an absence of write-protected data between a lowest address of the range of addresses corresponding to the entry and a highest address of a memory. A second indication stored in the entry corresponds to write-protected data within the range of addresses. The data storage device also includes a write protection map that includes a second set of entries corresponding to a second set of ranges of the memory addresses. The device is configured to locate, in the write protection data structure, an entry corresponding to a range of memory addresses.