Storage device and method of operating the storage device

A storage device comprising:

• a non-volatile memory device including a non-volatile storage area configured to store a plurality of map entries and a page buffer group configured to sense data stored in the non-volatile storage area or temporality store data to be stored in the non-volatile storage area;
• a volatile memory device including a map cache buffer configured to store part of map entries among the plurality of the map entries;
• and
• a memory controller configured receive a read request and a logical address from an external host, translate the logical address to a physical address and obtain read data correspond to the read request;
• wherein the page buffer group comprising:
• a first volatile storage area configured to store first map entries different from map entries stored in the map cache buffer;
• and
• a second volatile storage area configured to store second map entries including a plurality of map entries among the first map entries and a hit count corresponds to each second map entry;
• and
• wherein the memory controller searches the physical address in response to the read request in an order of the second volatile storage area, the first volatile storage area and the map cache buffer.