A data storage device includes a memory device and a memory controller. The memory controller selects a predetermined memory block to receive data and records multiple logical addresses in a first mapping table. When the predetermined memory block is full, the memory controller edits a second mapping table based on the first mapping table. When editing the second mapping table, the memory controller determines whether M consecutive logical addresses have been recorded in the first mapping table. When the memory controller determines that M consecutive logical addresses have been recorded in the first mapping table, the memory controller edits the second mapping table according to a data compression rate (R), such that one or more fields, which correspond to one or more logical addresses recorded in the first mapping table, of the second mapping table are skipped and not edited. M and R are positive integers greater than 1.