Method of generating secondary index and apparatus for storing secondary index

Patent metadata

Field	Value
Publication number	US-10061693-B2
Application number	US-201514694442-A
Country	US
Kind code	B2
Filing date	Apr 23, 2015
Priority date	Apr 23, 2014
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

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.

First claim

What is claimed is:

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.

Assignees

• Samsung Electronics Co Ltd
• Samsung Electronics Co Ltd

Inventors

• Kim Youn-Woo

Classifications

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F2212/1016

  Performance improvement · CPC title

• G06F2212/214

  Solid state disk · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title