Controller including map cache and memory system including controller

A memory system comprising:

• a memory device including memory blocks, each storing physical addresses;
• and
• a controller configured to communicate with the memory device using a physical address among the physical addresses and communicate with a host using a logical address corresponding to the physical address, the controller including a map cache,
• wherein the controller is configured to generate descriptors by mapping logical addresses and physical addresses, respectively, store the descriptors in the map cache in a linear structure and a binary tree structure, and search for a descriptor corresponding to the logical address by selectively performing a linear search method or a binary search method or simultaneously performing both the linear search method and the binary search method, according to a status of the map cache when receiving a read request for the logical address from the host.

A memory system comprising:

• a memory device including a plurality of memory blocks, each memory block having physical addresses;
• and
• a controller including a first queue and a second queue, configured to:
• generate descriptors, each descriptor indicating a mapping relationship between a logical address and a physical address;
• sequentially store the descriptors in the first queue in a linear structure and then store the descriptors in the second queue in a binary tree structure;
• generate status information indicating statuses of the first queue and the second queue;
• receive a target logical address from a host;
• and
• search for a descriptor associated with the target logical address in at least one of the first queue and the second queue based on the status information by performing a linear search on the first queue, performing a binary search on the second queue, or performing the linear search on the first queue and the binary search on the second queue.