Provided are a storage device storing data on the basis of key-value and an operating method thereof, wherein the storage device separates and manages a plurality of keys and a plurality of values respectively corresponding to the plurality of keys, and includes a first controller processing a first key and a first value corresponding to the first key, a second controller processing a second key and a second value corresponding to the second key, and a nonvolatile memory storing the first key, the second key, the first value, and the second value, wherein the first key includes information about the second controller regarding a processing core for the second value processed next to the first value.