A data storage device includes a memory device and a memory controller. The memory controller is coupled to the memory device and configured to access the memory device and establish a physical to logical address mapping table and a logical address section table. The logical address section table records statuses of a plurality of logical address sections. Each status is utilized to indicate whether the physical to logical address mapping table records any logical address that belongs to the corresponding logical address section. The logical address section table includes a plurality of section bits in a plurality of dimensions. When the memory controller receives a write command to write data of a first predetermined logical address, the memory controller determines the section bit of each dimension corresponding to the first predetermined logical address, and accordingly sets a corresponding digital value for each section bit.