Method and system for dynamically partitioning very large database indices on write-once tables

摘要

Methods and systems for partitioning and dynamically merging a database index are described. A database index includes a single first-level index partition stored in a data cache. As the first-level index partition in the data cache reaches a predetermined size, it is copied to secondary storage and a new index partition is generated in the data cache. When the number of index partitions in secondary storage reaches some predetermined number, the index partitions are merged to create a single index partition of a higher level in a hierarchy of index partitions having an exponentially increasing size with each increase in level within the hierarchy.

主权项

1. A processor-implemented method for processing a query using a database index, the method comprising:
partitioning a database index by determining that a first-level index partition stored in a data cache exceeds a threshold size, the database index structured as a hierarchy of index partitions having a plurality of levels with one index partition at a first-level residing in a data cache and all other index partitions residing in secondary storage, each index partition structured as a B-tree increasing exponentially in size with each increase in level within the hierarchy;
after determining that a first-level index partition stored in a data cache exceeds a threshold size, performing a first-level partitioning operation to write the first-level index partition stored in the data cache to a secondary storage, and generate a new first-level index partition in the data cache;performing a first-level merge operation, after determining that a number of first-level index partitions in the secondary storage has reached a predetermined number, the first-level merge operation merges the predetermined number of first-level index partitions into a single second-level index partition, and deletes the predetermined number of first-level index partitions from the secondary storage; receiving, at a processor-implemented query processing module, a query specifying data selection criterion; and utilizing the database index to process the query and to provide, from a database table, records satisfying the data selection criterion.