Provided is an operation method of a controller which controls a memory device. The operation method may include: determining a caching order of plural pieces of map data included in a request map segment including request map data; requesting the request map segment from the memory device; marking data in a marking region which is determined based on the caching order; caching, in the caching order, the plural pieces of map data read from the memory device; and acquiring the request map data from the cached data, depending on whether the data stored in the marking region is changed.