Range lookup operations for b e-trees using update messages

A non-transitory computer-readable medium storing instructions, which when executed by a processing device, cause the processing device to perform a method comprising:

• inserting a first key and a first value into a first tree, wherein the first key corresponds to the first value and wherein the first key and the first value are a first key/value pair;
• inserting a second key and a second value into the first tree, wherein the second key is a duplicate of the first key and wherein the second value is an operation to be applied to the first value and wherein the second key and the second value are a second key/value pair;
• in response to a request for a range of key/value pairs following a third key/value pair:
• reading the second key/value pair from the first tree;
• inserting the second key/value pair into a second tree;
• reading the first key/value pair from the first tree;
• determining, while inserting the first key/value pair into the second tree, that the second key is a duplicate of the first key;
• determining an updated value for the first key/value pair, wherein the determining includes the first key, the first value, and the second value, and wherein the updated value is the result of applying the operation in the second value to the first value;
• updating, in response to receiving the updated value, the second key/value pair within the second tree to replace the second value with the updated value;
• returning the range of key/value pairs from the second tree, wherein the range includes a key/value pair containing the second key and the updated value.

An apparatus comprising:

• a processing device;
• and
• a memory coupled to the processing device, the memory storing instructions which, when executed by the processing device, cause the apparatus to:
• insert a first key and a first value into a first tree, wherein the first key corresponds to the first value and wherein the first key and the first value are a first key/value pair;
• insert a second key and a second value into the first tree, wherein the second key is a duplicate of the first key and wherein the second value is an operation to be applied to the first value and wherein the second key and the second value are a second key/value pair;
• in response to a request for a range of key/value pairs following a third key/value pair:
• read the second key/value pair from the first tree;
• insert the second key/value pair into a second tree;
• read the first key/value pair from the first tree;
• determine, while inserting the first key/value pair into the second tree, that the second key is a duplicate of the first key;
• determine an updated value for the first key/value pair, wherein the determining includes the first key, the first value, and the second value, and wherein the updated value is the result of applying the operation in the second value to the first value;
• update, in response to receiving the updated value, the second key/value pair within the second tree to replace the second value with the updated value;
• return the range of key/value pairs from the second tree, wherein the range includes a key/value pair containing the second key and the updated value.