A storage device includes multiple memory devices and a memory controller. The memory controller receives, from a host, values corresponding to data stored in the memory devices and keys for identifying the values, generates parities for inspecting the data for any errors based on the values, and manages key-value mapping information regarding a correspondence between the values and the keys. The memory devices include a first memory device and a second memory device, which store the values and the keys, and a third memory device, which stores parity values calculated from the values and a parity value header for managing the parity values.