Data storage device and method of operating the same using primary and secondary indexes
A data storage device includes: a memory device including a plurality of first storage areas and a plurality of second storage areas, each of which stores a primary index corresponding to a primary key provided from a host and a primary value corresponding to the primary index, and a memory controller for controlling the memory device. The memory controller is configured to generate, according to a request from the host, the primary index including the primary key and address information of a target second storage area in which a primary value corresponding to the primary key is stored, among the plurality of second storage areas, generate, according to an additional request from the host, a secondary key corresponding to a secondary value including a portion of the primary value, and generate a secondary index including the secondary key and the address information of the target second storage area.
1 . A data storage device comprising:
a memory device including a plurality of first storage areas and a plurality of second storage areas, the plurality of first storage areas storing a primary index corresponding to a primary key provided from a host, and the plurality of second storage areas storing a primary value corresponding to the primary index; and
a memory controller configured to control the memory device,
wherein the memory controller is configured to:
generate, according to a request from the host, the primary index including the primary key and address information of a target second storage area in which the primary value corresponding to the primary key is stored, among the plurality of second storage areas;
generate, according to an additional request from the host, a secondary key corresponding to a secondary value including a portion of the primary value;
generate a secondary index including the secondary key and the address information of the target second storage area;
generate secondary index meta data including information of a maximum secondary key having a maximum value among secondary keys included in the secondary index; and
identify a target secondary index including a request key of a read command from the host, based on the maximum secondary key included in the secondary index meta data, and
wherein, when a number of primary indexes generated according to the request from the host reaches a first threshold value, the memory controller is configured to sort generated primary indexes based on primary keys included in the generated primary indexes.
2 . The data storage device of claim 1 , wherein the address information of the target second storage area includes first offset information and first length information, which indicate a position at which the primary value is stored in the target second storage area.
3 . The data storage device of claim 1 , wherein the memory controller is configured to control the memory device to store sorted primary indexes in a target first storage area among the plurality of first storage areas.
4 . The data storage device of claim 1 , wherein the memory controller is configured to sort primary values to correspond to sorted primary indexes.
5 . The data storage device of claim 4 , wherein the memory controller is configured to control the memory device to store sorted primary values in the target second storage area.
6 . The data storage device of claim 3 , wherein the memory controller is configured to generate primary index meta data including address information of the target first storage area.
7 . The data storage device of claim 6 , wherein the primary index meta data includes information of a maximum primary key having a maximum value, among the primary keys included in the sorted primary indexes stored in the target first storage area.
8 . The data storage device of claim 1 , wherein the memory controller is configured to generate the secondary key by selecting the secondary value among the primary values, using second offset information and second length information, which correspond to the additional request from the host.
9 . The data storage device of claim 1 , wherein the secondary index includes third offset information and third length information, which indicate a position at which the secondary value is stored in the target second storage area.
10 . The data storage device of claim 1 , wherein, when a number of secondary indexes generated according to the additional request from the host reaches a second threshold value, the memory controller is configured to sort generated secondary indexes based on the secondary keys included in the generated secondary indexes.
11 . The data storage device of claim 10 ,
wherein the memory device includes a plurality of third storage areas, and
wherein the memory controller is configured to control the memory device to store sorted secondary indexes in a target third storage area among the plurality of third storage areas.
12 . The data storage device of claim 11 , wherein the memory controller is configured to generate the secondary index meta data including address information of the target third storage area.
13 . The data storage device of claim 12 , wherein the secondary index meta data further includes information of the maximum secondary key having the maximum value, among the secondary keys included in the sorted secondary indexes stored in the target third storage area.
14 . The data storage device of claim 13 , wherein the secondary index meta data includes duplication key information indicating whether a duplication key secondary index including same secondary key as the maximum secondary key exists in a third storage area except the target third storage area among the plurality of third storage areas.
15 . A method of operating a data storage device for controlling a memory device including a first storage area and a second storage area, the first storage area storing a primary index corresponding to a primary key, and the second storage area storing a primary value corresponding to the primary index, the method comprising:
generating the primary index including the primary key and address information of the second storage area in which the primary value corresponding to the primary key is stored;
generating a secondary key corresponding to a secondary value including a portion of the primary value;
generating a secondary index including the secondary key and the address information of the second storage area;
generating secondary index meta data including information of a maximum secondary key having a maximum value among secondary keys included in the secondary index; and
in response to receiving a read command including a request key from the host, identifying a target secondary index that includes the request key based on the maximum secondary key included in the secondary index meta data,
wherein generating the primary index comprises, when a number of primary indexes generated according to the request from the host reaches a first threshold value, sorting generated primary indexes based on primary keys included in the generated primary indexes.
16 . The method of claim 15 , wherein the primary index includes first offset information and first length information, which indicate a position at which the primary value is stored in the second storage area.
17 . The method of claim 15 , wherein the portion of the primary value is specified as the secondary value according to second offset information and second length information, which are received from a host.
18 . The method of claim 15 , wherein the secondary index includes third offset information and third length information, which indicate a position at which the secondary value is stored in the second storage area.
19 . The method of claim 15 , further comprising:
storing the secondary index in a third storage area of the memory device; and
generating the secondary index meta data including address information of the third storage area.