A storage device includes two flash memories of different flash memory types, and respectively including multiple data blocks. Each data block corresponds to a physical and a logical block address. The storage device further includes a processing module including a controller, which is capable of accessing two mapping tables respectively corresponding to the two flash memories and respectively recording the physical block addresses and the logical block addresses that correspond to the data blocks of the two flash memories. The controller is configured to determine, upon receipt of a command that contains a target logical block address therein, a selected one of the flash memories according to the target logical block address, and to locate a selected one of the physical block addresses by searching one of the mapping tables that corresponds to the selected one of the flash memories with reference to the target logical block address.