METHOD OF GENERATING SECONDARY INDEX AND APPARATUS FOR STORINGSECONDARY INDEX

• US 20150310053A1
• Filed: 04/23/2015
• Published: 10/29/2015
• Est. Priority Date: 04/23/2014
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Original Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Inventors: KIM, Youn-woo
• Granted Patent: US 10,061,693 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/214 Solid state disk
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method and apparatus for generating and storing a secondary index. The method includes generating, in response to a size of an index data being greater than a size of a memory block, an index data table including the index data and recording the index data table in a memory, generating a metadata table of the index data table and recording the metadata table in the memory, and performing a merge and sort regarding at least one of the index data table and the metadata table. The apparatus includes a memory; and a controller configured to, in response to a size of index data being greater than a size of a memory block, generate an index data table including the index data and record the index data table in a memory, and perform a merge and sort regarding at least one of the index data table and the metadata table.

Claims

1. A method of generating a secondary index, the method comprising:

generating, in response to a size of an index data being greater than a size of a memory block, an index data table including the index data and recording the index data table in a memory;

generating a metadata table of the index data table and recording the metadata table in the memory; and

performing a merge and sort regarding at least one of the index data table and the metadata table.

2. The method of claim 1, wherein performing merge and sort comprises, in response to an index data table for which the merge and sort is not performed being greater than a preset number, performing the merge and sort for at least one of an index data table for which the merge sort is not performed and a metadata table of an index data table for which the merge sort is not performed.

3. The method of claim 2, wherein performing merge and sort comprises performing the merge and sort only for metadata tables of the index data table for which the merge and sort is not performed.

4. The method of claim 1, wherein performing merge and sort comprises performing range compaction for an index data table for which failure of reading occurs at least a preset number of times.

5. The method of claim 4, further comprising:

generating a metadata table of the index data table for which the range compaction is performed and recording the metadata table in the memory.

6. The method of claim 1, wherein the metadata table includes at least one of page information of the index data, a first key value of the index data table, and a root value indicating a range of a page of the index data.

7. The method of claim 1, wherein the index data table for which the merge sort is performed is recorded in at least one memory block.

8. The method of claim 7, wherein only one index data table is recorded in a memory block.

9. The method of claim 1, further comprising:

performing the merge and sort for at least one of the index data table and the metadata table for which the merge sort is not performed.

10. The method of claim 6, wherein the root value is recorded via atomic writing.

11. The method of claim 1, wherein the memory is a solid state drive (SSD).

12. An apparatus for storing a secondary index, the apparatus comprising:

a memory; and

a controller configured to, in response to a size of index data being greater than a size of a memory block, generate an index data table including the index data and record the index data table in a memory, and perform a merge and sort regarding at least one of the index data table and the metadata table.

13. The apparatus of claim 12, wherein the controller, in response to an index data table for which merge and sort is not performed being greater than a preset number, is further configured to perform merge and sort for at least one of an index data table for which the merge sort is not performed and a metadata table of an index data table for which merge and sort is not performed.

14. The apparatus of claim 13, wherein the controller is further configured to perform merge and sort only for metadata tables of the index data table for which merge and sort is not performed.

15. The apparatus of claim 12, wherein the controller is further configured to perform range merge and sort or range compaction for an index data table for which failure of reading occurs for at least a preset number of times.

16. The apparatus of claim 15, wherein the controller is further configured to generate a metadata table of the index data table for which the range compaction is performed and record the metadata table in the memory.

17. The apparatus of claim 12, wherein the metadata table includes at least one of page information of the index data, a first key value of the index data table and a root value indicating a range of a page of the index data.

18. The apparatus of claim 12, wherein the index table for which merge and sort is performed is recorded in at least one memory block.

19. The apparatus of claim 18, wherein only one index data table is recorded in a memory block.

20. The apparatus of claim 12, wherein the controller is further configured to perform merge and sort for at least one of the index data table and the metadata table for which merge and sort is not performed.