A data storage device is disclosed comprising a non-volatile memory. A write command is received comprising a first logical block address (LBA) and first user data, and a second LBA and second user data. The first LBA is mapped to a first physical block address (PBA) for addressing a first memory segment. The second LBA is mapped to a second PBA for addressing a second memory segment. First redundancy is generated in response to the first user data, second redundancy in generated in response to the second user data, and parity data is generated in response to the first and second user data. Third redundancy is generated in response to the parity data and in response to at least one of the first LBA and the first PBA and at least one of the second LBA and the second PBA.