Write-optimized nested trees

A non-transitory computer-readable storage medium having stored thereon computer executable instructions, which when executed by a processor, cause the processor to:

• receive an insert operation comprising a key and a value to be stored in a tree data structure of the file system, the tree data structure comprising a plurality of nodes organized in a hierarchy, each node having a buffer to store key-value pairs in a B+-tree data structure comprising disk blocks allocated from the storage volume and characterized by a predetermined maximum buffer size;
• add the received key and value as a key-value pair to the B+-tree in a root node of the tree data structure;
• and
• move one or more key-value pairs from the B+-tree in the root node to a B+-tree in a child node of the root node when an amount of data stored in the B+-tree of the root node is greater than the predetermined maximum buffer size, including allocating one or more disk blocks to the buffer of the child node as needed to store the one or more key-value pairs in the B+-tree of the child node,
• wherein moving the one or more key-value pairs from the B+-tree in the root node to the B+-tree in the child node comprises:
• producing a combined list of key-value pairs comprising the one or more key-value pairs from the B+-tree in the root node and key-value pairs in the B+-tree of the child node;
• and
• rebuilding the B+-tree in the child node using the combined list of key-value pairs.

An apparatus comprising:

• one or more computer processors;
• and
• a computer-readable storage medium comprising instructions for controlling the one or more computer processors to be operable to:
• receive an insert operation comprising a key and a value to be stored in a tree data structure of the file system, the tree data structure comprising a plurality of nodes organized in a hierarchy, each node having a buffer to store key-value pairs in a B+-tree data structure comprising disk blocks allocated from the storage volume and characterized by a predetermined maximum buffer size;
• add the received key and value as a key-value pair to the B+-tree in a root node of the tree data structure;
• and
• move one or more key-value pairs from the B+-tree in the root node to a B+-tree in a child node of the root node when an amount of data stored in the B+-tree of the root node is greater than the predetermined maximum buffer size, including allocating one or more disk blocks to the buffer of the child node as needed to store the one or more key-value pairs in the B+-tree of the child node,
• wherein moving the one or more key-value pairs from the B+-tree in the root node to the B+-tree in the child node comprises:
• producing a combined list of key-value pairs comprising the one or more key-value pairs from the B+-tree in the root node and key-value pairs in the B+-tree of the child node;
• and
• rebuilding the B+-tree in the child node using the combined list of key-value pairs.