Data storage device that stores multiple values corresponding to multiple keys in a page

A data storage device comprising:

• a non-volatile memory including a first region and a second region different from the first region;
• and
• a controller which stores first, second, and third data in a first region of the non-volatile memory, wherein:
• the first region of the non-volatile memory includes a first storage region, a second storage region subsequent to the first storage region, and a third storage region subsequent to the second storage region,
• the second region of the non-volatile memory includes a spare region,
• a page of the non-volatile memory includes the second storage region and the spare region,
• a part of the first data is stored in the first storage region,
• another part of the first data is stored in the second storage region,
• the second data is stored in the second storage region,
• a part of the third data is stored in the second storage region,
• another part of the third data is stored in the third storage region,
• an offset value of the second storage region in which the second data is started is stored in the spare region of the non-volatile memory,
• no offset value of the second storage region in which the other part of the first data is started is stored in the spare region of the non-volatile memory, and
• no offset value of the second region in which the part of the third data is started is stored in the spare region of the non-volatile memory.

A data storage device comprising:

• a non-volatile memory which includes:
• a first page which includes:
• a first storage region in which first sub-data of first data is stored, and
• a first spare region in which a first offset associated with the first storage region is stored;
• a second page which includes:
• a second storage region in which:
• second sub-data of the first data is stored;
• second data is stored subsequent to the second sub-data;
• and
• third data is stored subsequent to the second data, and
• a second spare region storing:
• a second offset of the start of the second data within the second storage region, the second offset corresponding to a size of the second sub-data;
• and
• no offset value of the start of the third data within the second storage region;
• and
• a controller which reads the first sub-data stored in the first storage region and transmits the first sub-data to an external host, wherein:
• the second storage region is subsequent to the first storage region,
• when the controller reads the first sub-data, the controller refers to the first offset stored in the first spare region and scans the first storage region from the first offset to read the first sub-data, and
• when the controller reads the second sub-data, the controller does not refer to an offset stored in the first spare region.