Method of generating secondary index and apparatus for storing secondary index

• US 10,061,693 B2
• Filed: 04/23/2015
• Issued: 08/28/2018
• Est. Priority Date: 04/23/2014
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Youn-woo
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US14/694,442
• Publication Number:
  US 20150310053A1
• Time in Patent Office: 1,223 Days
• Field of Search: 707741, 707609, 707696
• 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 comprising an index data table, the method comprising:

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

generating a metadata table corresponding to 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,

wherein performing the merge and sort comprises performing, in response to an index data table for which the merge and sort is not performed being greater than or equal to a preset number, a merge and sort for metadata tables of the index data table for which the merge and sort is not performed without performing the merge and sort for the index data table for which the merge sort is not performed.

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

3. The method of claim 2, 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.

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

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

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

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

8. The method of claim 4, wherein the root value is recorded via atomic writing.

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

10. An apparatus for storing a secondary index comprising an index data table, 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 the index data table including the index data and record the index data table in a memory, generate a metadata table corresponding to the index data table and record the metadata table in the memory, and perform a merge and sort regarding at least one of the index data table and the metadata table,

wherein the controller is further configured to perform, in response to an index data table for which the merge and sort is not performed being greater than or equal to a preset number, a merge and sort for metadata tables of the index data table for which the merge and sort is not performed without performing the merge and sort for the index data table for which the merge sort is not performed.

11. The apparatus of claim 10, 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.

12. The apparatus of claim 11, 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.

13. The apparatus of claim 10, 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.

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

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

16. The apparatus of claim 10, 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.