A storage device includes a controller configured to: receive, from a host, a plurality of key-value pairs, separate a key from each of the plurality of key-value pairs and a value therefrom, and generate a first key stream by merging a plurality of keys separated from the plurality of key-value pairs, and non-volatile memory configured to store the first key stream. The first key stream is stored, separately from the value separated from each of the plurality of key-value pairs, in the non-volatile memory.