A data storage device includes a nonvolatile memory device including an address mapping table; a memory including a sequential map table in which sequential map entries for consecutive logical block addresses among logical block addresses are stored, the logical block addresses being received with write requests from a host device; and a processor configured to read one or more map segments, including logical block addresses of which mapping information is to be updated, from the address mapping table when a map update operation is triggered, store the read one or more map segments in the memory, sequentially change physical block addresses mapped to the respective logical block addresses to be updated, using a first sequential map entry including the logical block addresses to be updated which are stored in the sequential map table, and store the changed physical block addresses in the memory.