A memory controller, an operating method of the memory controller, and a storage device including the memory controller are disclosed. The memory controller includes: a memory configured to store an address mapping table and a segment mapping table; and a mapping data management module configured to select at least two updated segments among a plurality of segments included in the address mapping table as page data to be stored in one page of a nonvolatile memory, wherein each of the plurality of segments includes a plurality of mapping entries representing mapping information between logical addresses and physical addresses, and wherein the segment mapping table includes physical addresses representing areas in which each of the plurality of segments is stored in the nonvolatile memory.