The system receives a request to write a first piece of data to a non-volatile memory. The system encodes, based on an error correction code (ECC), the first piece of data to obtain a first ECC codeword which includes a plurality of ordered parts and a first parity. The system writes the plurality of ordered parts in multiple rows. The system writes the first parity to a same row in which a starting ordered part is written. The system updates, in a data structure, entries associated with the ordered parts. A respective entry indicates: a virtual address associated with a respective ordered part, a physical address at which the respective ordered part is written, and an index corresponding to a virtual address associated with a next ordered part. A first entry associated with the starting ordered part further indicates a physical address at which the first parity is written.