Enhanced B-Trees with Record Merging

摘要

In some implementations, a B+tree (b plus tree) can provide concurrent access to data while modifying nodes of the B+tree. In some implementations, a top-down B+tree can be provided where nodes of the B+tree can be proactively merged, rebalanced and split to prevent recursive operations moving up the B+tree. In some implementations, node (or page) record data can be merged to consolidate record entries within nodes of the B+tree while only locking 1-3 nodes of the tree at the same time. In some implementations, record data can be merged across multiple nodes of the B+tree. In some implementations, ranges of data can be removed from the tree while only locking 1-3 nodes of the tree at the same time. In some implementations, range of data can be replaced with new data while only locking 1-3 nodes of the tree at the same time.

主权项

1. A method comprising:
storing records in a B-tree data structure; receiving a new record for insertion into the B-tree data structure; in response to receiving the new record for insertion,
traversing the B-tree based on a value of a key in the new record;proactively merging, rebalancing, and splitting nodes while traversing the B-tree; andinserting the new record in a leaf node of the B-tree by
determining that the new record corresponds to the first or last record in the leaf node;identifying an adjacent node;determining that the new record can be merged with an existing record in the adjacent node;identifying the closest common ancestor node of the leaf node and the adjacent node;obtaining an exclusive lock on the closest common ancestor node, and the path of nodes leading to and including the leaf node, the adjacent node; andmerging the new record with the existing record.