A data storage device includes a nonvolatile memory device including a plurality of memory blocks each of which includes a plurality of pages; and a controller suitable for obtain block physical to logical (P2L) data corresponding to a first memory block among the plurality of memory blocks, determine first and second target logical to physical (L2P) pages, one or more first target L2P segments stored in the first target L2P page and one or more second target L2P segments stored in the second target L2P page, based on the block P2L data and an L2P segment position table, obtain the first target L2P segments, and verify validity for one or more first P2L data included in the block P2L data, based on the first target L2P segments, wherein the controller obtains the second target L2P segments while verifying the validity for the first P2L data.