A mapping table accessing method for a rewritable non-volatile memory module is provided. The method includes: storing a mapping record corresponding to a first physical erasing unit into the first physical erasing unit, wherein the mapping record of the first physical erasing unit is a mapping relation of physical programming units in the first physical erasing unit. The method further includes: storing a mapping record corresponding to a second physical erasing unit into the second physical erasing unit, wherein the mapping record of the second physical erasing unit is a mapping relation of physical programming units in the second physical erasing unit. A size of the mapping record of the first physical erasing unit is different from a size of the mapping record of the second physical erasing unit.