While flash memory has been widely adopted for various embedded systems, space efficiency with reasonable performance has become a critical issue for the design of the flash-memory translation layer. The target of this paper is to improve the performance of existing designs by proposing a search-tree-like caching mechanism for efficient address translation. A replacement strategy with a low time complexity is presented to monitor the access status of recently used LBA?s. The proposed caching mechanism and replacement strategy were shown being highly effective in the reducing of the address translation time over popular translation layer designs, such as NAND, where realistic workloads were used for experiments.