1. A device, comprising: data storage comprising a plurality of physical data blocks organized into a plurality of logical data blocks, wherein each of the plurality of physical data blocks comprises a plurality of physical pages and wherein each of the plurality of logical data blocks comprises a plurality of logical pages; and control circuitry for writing data to a physical page of the data storage in response to a write command associated with an address of a particular logical page of a particular logical data block; wherein the control circuitry is configured to write the data to the physical page having a particular data structure; wherein, when more than one physical page of the data storage stores valid data corresponding to the particular logical data block, the particular data structure of the physical page to which the data is to be written in response to the write command comprises user data to be received from an external device and a plurality of addresses, each address of the plurality of addresses corresponding to a physical page of the data storage storing valid data corresponding to the particular logical data block; wherein the control circuitry is further configured to write at least a portion of the user data to the physical page concurrently with writing at least a portion of the plurality of addresses to the physical page; and wherein a first address of the at least a portion of the plurality of addresses is different than a second address of the at least a portion of the plurality of addresses.