METHOD FOR UPDATING INVERTED INDEX OF FLASH SSD

• US 20140351490A1
• Filed: 05/22/2014
• Published: 11/27/2014
• Est. Priority Date: 05/22/2013
• Status: Active Grant

• Current Assignee: Industry Academic Cooperation Foundation
• Original Assignee: Industry Academic Cooperation Foundation
• Inventors: PARK, Sang Hyun, JUNG, Won Mook, ROH, Hong Chan, SHIN, Min Cheol
• Granted Patent: US 9,715,446 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7202 Allocation control and policies

Abstract

Disclosed is a method for updating an inverted index of a flash solid state disk (SSD). The method including: storing postings of a term that is present in only an in-memory inverted index in a block of an output buffer and reading postings of a last block of each posting list to be updated from an on-disk inverted index to be stored in each block of an input buffer, by scanning the on-disk inverted index and the in-memory inverted index; moving postings of the input buffer to the blocks of the output buffer for each block and attaching new postings of the in-memory inverted index to the block corresponding to the output buffer; and updating the on-disk inverted index by using the postings of each block of the output buffer.

Claims

1. A method for updating an inverted index of a flash solid state disk (SSD),

wherein an on-disk inverted index is constituted by terms and a posting list which is a list of postings corresponding to the respective terms and at least one block which has a predetermined size and is used for containing the postings is provided in each term, and

an in-memory inverted index is constituted by input terms and postings corresponding to the respective terms, the method comprising:

storing postings of a term that is present in only the in-memory inverted index in a block of the output buffer and reading postings of a last block of each posting list to be updated from the on-disk inverted index to be stored in each block of the input buffer, by scanning the on-disk inverted index and the in-memory inverted index;

moving postings of the input buffer to the blocks of the output buffer for each block and attaching new postings of the in-memory inverted index to the block corresponding to the output buffer; and

updating the on-disk inverted index by using the postings of each block of the output buffer.

2. The method of claim 1, wherein the on-disk inverted index includes a posting list maintained in a plurality of non-contiguous blocks.

3. The method of claim 1, wherein the input buffer is constituted by blocks of a predetermined number, and

scanning the on-disk inverted index and the in-memory inverted index is performed until all of the blocks of the input buffer are filled.

4. The method of claim 1, wherein reading postings of a last block of each posting list to be updated from the on-disk inverted index is simultaneously reading the corresponding blocks.

5. The method of claim 1, wherein while the new postings of the in-memory inverted index are attached to the block corresponding to the output buffer, if the corresponding block does not have a sufficient space to house the new postings, postings which are not housed in the space of the corresponding block among the new postings are stored in another block of the output buffer.

6. The method of claim 1, wherein in the updating, the blocks of the output buffer to which the new postings are attached are overwritten to the block corresponding to the on-disk inverted index and the block of the output buffer storing postings of a term which is present in only the in-memory inverted index is written in a rear part of the on-disk inverted index.

7. The method of claim 5, wherein in the updating, the blocks of the output buffer to which the new postings are attached are overwritten in the block corresponding to the on-disk inverted index and the block of the output buffer storing postings of a term which is present in only the in-memory inverted index and the block of the output buffer storing the new postings that are not housed in the space of the corresponding block is written to the rear part of the on-disk inverted index.

8. The method of claim 6, wherein in the updating, writing and overwriting blocks is simultaneously writing and overwriting the corresponding blocks.

9. A computer-readable recording medium having a program for executing the method for updating an inverted index of a flash solid state disk (SSD) according to claim 1, which is recorded therein.