Microsoft Corporation
MULTI-RECORD INDEX STRUCTURE FOR KEY-VALUE STORES

Abstract:

A method of maintaining a key-value store comprising a first record structure in which each key comprises an index and each value comprises a respective set of item IDs, and a second record structure in which each key comprises an item ID and each value comprises a respective item of data. Each new item ID of a group is added, starting at the root level of a tree structure: I) determining whether the current record will exceed a maximum size limit if the new item ID is included therein, and if not, including the new item ID, but II) if so, identifying a number of records at the next level of the tree structure, and applying a deterministic transformation to the item ID of the new item to determine one of the identified number of records, and repeating from I) with the determined record now as the current record.