A data storing method for a rewritable non-volatile memory module is provided. The method includes dividing logical addresses into a plurality of logical zones, and respectively establishing a plurality of logical address mapping tables for the logical zones. The method also includes writing data of a logical address into a physical program unit; and recording a mapping record indicating the logical address is mapped to the physical program unit in a temp mapping table. The method further includes: if the temp mapping table is full, updating the mapping relations between the logical addresses and the physical program units in the logical address mapping tables based on mapping records recorded in the temp mapping table, and deleting the mapping records in the temp mapping table.