A memory system includes a memory device including a plurality of non-volatile memory cells; and a controller configured to program data input from an external device in the memory device, generate a map data item corresponding to the data, perform a compression operation on second map data when the second map data includes no empty area for the map data item. A timing of updating first map data stored in the memory device based on the second map data is determined according to whether the second map data is compressed or not.