Fast multi-tier indexing supporting dynamic update

Patent metadata

Field	Value
Publication number	US-10831736-B2
Application number	US-201514671692-A
Country	US
Kind code	B2
Filing date	Mar 27, 2015
Priority date	Mar 27, 2015
Publication date	Nov 10, 2020
Grant date	Nov 10, 2020

Abstract

A method includes performing a lookup using a key into a root node of a multi-tier data structure, to find a partition for performing an insert. A lookup for the key is performed on a first level index that is part of a linked data structure. A payload or reference is added to the linked data structure based on data structure criterion, otherwise the key and the payload are added to the linked data structure if the key is not found. A new first level index is created and added to the linked data structure upon the linked data structure remaining unchanged. The key and the payload or reference are added to the new index. Based on merge criterion, a new second level index is created and a portion of content from selected first level and second level indexes are merged for combining into the new second level index.

First claim

What is claimed is:

1. A method for inserting an entry into a multi-tier data structure comprising:
creating, by a data structure processor, a multi-tier data structure that includes an upper tier comprising a first level that is an extendible hashing dictionary data structure and a second level that is a fixed-size dictionary data structure, and a lower tier comprising an immutable dictionary structure including a concise hash table (CHT) that includes a first level comprising a bitmap array with bitmap pages and a second level comprising leaf pages, wherein leaf page pointers are interleaved within the bitmap array;
performing, by a hashing processor, a first lookup process using a key of the entry into a root node of the multi-tier data structure that determines a partition for performing an insert operation, wherein the extendible hashing dictionary data structure provides lookups using a number of hash bits used as an index into the fixed-size dictionary data structure;
performing a second lookup process for the key, by the hashing processor, on a first level index that is part of a linked data structure holding entries for the found partition;
based on data structure criterion, adding, by the hashing processor, a payload or reference to the payload to the linked data structure upon finding the key, otherwise if the key is not found, adding the key and the payload to the linked data structure;
based on data structure criterion, creating, by the data structure processor, a new first level index and adding the new first level index to the linked data structure upon the linked data structure remaining unchanged since starting the second lookup process for the key, and adding the key and the payload or the reference to payload to the new first level index;
based on a merge criterion, creating, by the data structure processor, a new second level index and merging a portion of content from selected first level and second level indexes into the new second level index, and
using the lower tier of the multi-tier data structure instead of the upper tier upon the first level index exceeding a size for the upper tier.

2. The method of claim 1 , further comprising:
updating, by an update processor, the linked data structure by replacing indexes with content that has been fully merged with the one or more new second level indexes, wherein the selection of first level and second level indexes for merging into a new second level index also marks the selected first level and second level indexes as not accepting further inserts.

3. The method of claim 1 , wherein the data structure criterion comprises one or more of sufficient space in an index of the linked data structure, the index being able to accept additional inserts, the index having an imbalanced structure, or lookup efficiency.

4. The method of claim 1 , wherein the merge criterion comprises one or more of:
no on-going merge operation exists on the partition,
determining that a merge operation is warranted due to significant content present in the selected first level and second level indexes, or
lookup efficiency.

5. The method of claim 2 , wherein:
the upper tier of the multi-tier data structure comprises a single node containing a mutable dictionary data structure that maps indicator values derived from keys onto pointers to nodes in the lower tier of the multi-tier data structure;
the mutable dictionary structure is efficient for performing individual insert operations; and
the mutable dictionary data structure comprises a data structure without storing keys or attributes, and the mutable dictionary data structure stores hash values of keys and maps hash values to a set of tuple sequence numbers.

6. The method of claim 5 , wherein:
each node in the lower tier of the multi-tier data structure has one immutable index data structure that is efficient for performing lookup operations and bulk loading;
inserts into the multi-tier data structure comprise performing a lookup operation into the mutable index data structure to select a lower tier node to insert into;
inserts into the lower tier nodes are made into a most recently added mutable dictionary data structure at that node;
the mutable dictionary data structures are periodically merged into the immutable index data structure, producing a new immutable index data structure; and
the immutable dictionary structure does not support insert operations or delete operations.

7. The method of claim 1 , wherein the first lookup process uses a hash value, a result buffer and maximum size as input parameters, and returns as value a number of record identifiers found for a desired hash key, and places as many result payloads that fit within the maximum size into the result buffer.

8. A computer program product for inserting an entry into a multi-tier data structure, the computer program product comprising a non-transitory computer readable storage medium having program code embodied therewith, the program code executable by a processor to:
create, by a data structure processor, the multi-tier data structure that includes an upper tier comprising a first level that is an extendible hashing dictionary data structure and a second level that is a fixed-size dictionary data structure, and a lower tier comprising an immutable dictionary structure including a concise hash table (CHT) that includes a first level comprising a bitmap array with bitmap pages and a second level comprising leaf pages, wherein leaf page pointers are interleaved within the bitmap array;
perform, by the processor, a first lookup process using a key of the entry into a root node of the multi-tier data structure that determines partition for performing an insert operation, wherein the extendible hashing dictionary data structure provides lookups using a number of hash bits used as an index into the fixed-size dictionary data structure;
perform a second lookup process, by the processor, for the key on a first level index that is part of a linked data structure holding entries for the found partition;
based on data structure criterion, add, by the processor, a payload or reference to the payload to the linked data structure upon finding the key, otherwise upon the key not being found, adding the key and the payload to the linked data structure;
based on data structure criterion, create, by the data structure processor, a new first level index and adding the new first level index to the linked data structure upon the linked data structure remaining unchanged since starting the second lookup process for the key, and adding the key and the payload or the reference to the payload to the new first level index;
based on a merge criterion, create, by the data structure processor, a new second level index and merging a portion of content from selected first level and second level indexes into the new second level index, and
using the lower tier of the multi-tier data structure instead of the upper tier upon the first level index exceeding a size for the upper tier.

9. The computer program product of claim 8 , further comprising program code executable by the processor to:
update, by an update processor, the linked data structure by replacing indexes with content that has been fully merged with the one or more new second level indexes, wherein the selection of first level and second level indexes for merging into a new second level index also marks the selected first level and second level indexes as not accepting further inserts.

10. The computer program product of claim 9 , wherein the data structure criterion comprises one or more of sufficient space in an index of the linked data structure, the index being able to accept additional inserts, th

Assignees

• IBM

Inventors

• Barber Ronald J
• Leis Viktor
• Lohman Guy M
• Raman Vijayshankar
• Sidle Richard S

Classifications

• G06F16/2272 Primary

  Management thereof · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title