US-12625621-B2 - Data storage device and method of operating the same using primary and secondary indexes

Abstract

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.

Inventors

• In Hyuk Park

Assignees

• SK Hynix Inc.

Dates

Publication Date

20260512

Application Date

20240205

Priority Date

20230829

Claims (19)

1. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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.

Description

CROSS-REFERENCE TO RELATED APPLICATION The present application claims priority under 35 U.S.C. § 119 (a) to Korean patent application number 10-2023-0113499 filed on Aug. 29, 2023, the entire disclosure of which is incorporated by reference herein. BACKGROUND 1. Field of Invention Various embodiment of the present disclosure generally relate to an electronic device, and more particularly, to a data storage device and a method of operating the same. 2. Description of Related Art A data storage device is a device which stores data under the control of a host device such as a computer or a smart phone. The data storage device may include a memory device in which data is stored and a memory controller which controls the memory device. The memory device may be a volatile memory device or a nonvolatile memory device. The volatile memory device is a memory device in which data is stored only when power is supplied, and the stored data is lost when the supply of power is interrupted. The volatile memory device may be a Static Random Access Memory (SRAM), a Dynamic Random Access Memory (DRAM), or the like. The nonvolatile memory device is a memory device in which data stored therein is retained even when the supply of power is interrupted. The nonvolatile memory device may be a Read Only Memory (ROM), a Programmable ROM (PROM), an Electrically Programmable ROM (EPROM), an Electrically Erasable ROM (EEROM), a flash memory, or the like. SUMMARY Embodiments of the present disclosure provide a data storage device capable of increasing a speed at which a specific value is searched, and a method of operating the same. In accordance with an embodiment of the present disclosure, there is provided a data storage device including: 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 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. In accordance with another embodiment of the present disclosure, there is provided a data storage device including: a memory device including a plurality of storage areas in which primary values corresponding to primary keys, primary indexes including the primary keys, and secondary indexes including secondary keys respectively corresponding to secondary values respectively including portions of the primary values are stored; and a memory controller configured to control, according to a read request from a host, the memory device to read target indexes including secondary keys corresponding to request keys included in the read request, among the secondary indexes, and read secondary values corresponding to the request keys, based on the target indexes. The memory controller may provide the host with the secondary values corresponding to the request keys or primary keys corresponding to the request keys. The request keys may include a start key and an end key, and the memory controller may control the memory device to read secondary values corresponding to secondary keys corresponding to the request keys between the start key and the end key. When the secondary values corresponding to the request keys is greater than a predetermined size, the memory controller may provide the host with some secondary values corresponding to some request keys among the request keys and offset information of remaining request keys among the request keys. The memory controller may provide, according to a subsequent read request received after the read request from the host, the host with remaining secondary values corresponding to the remaining request keys, based on the offset information. The memory controller may read the target indexes, based on second index meta data including address information of a first storage area in which the secondary indexes are stored, among the plurality of storage areas. The memory controller may control the memory device to read a second target index including a maximum secondary key among the target indexes, based on duplication key information indicating whether a same secondary key as the maximum secondary key included in a first target index among the target indexes is included. The secondary values may correspond to specified values