Write optimization in transactional data management systems

A computing apparatus, the computing apparatus comprising:

• a processor;
• and
• a memory storing instructions that, when executed by the processor, configure the apparatus to:
• store a tree data structure that comprises a root, a plurality of internal nodes, and a plurality of leaf nodes, each internal node comprising a pivot key and a child pointer, each leaf node storing key-value pairs sorted by a corresponding key, wherein the tree data structure comprises an index nodes layer and a leaf nodes layer;
• form a hybrid nodes layer between the index nodes layer and the leaf nodes layer, the hybrid nodes layer comprising a plurality of hybrid nodes, the hybrid nodes comprising a layer of internal nodes that are immediate parents of the plurality of leaf nodes, the index nodes layer comprising the root that points to nodes of the hybrid nodes layer, each node of the hybrid nodes layer pointing to one of the plurality of leaf nodes, the hybrid nodes combining features of the plurality of internal nodes and the plurality of leaf nodes;
• and
• form a plurality of buffers for the plurality of hybrid nodes, each internal node of the plurality of hybrid nodes having a corresponding buffer, the buffer being used to store a message that encodes an operation, the message to be applied to the corresponding leaf nodes of the leaf nodes layer.

A non-transitory computer-readable storage medium, the computer-readable storage medium including instructions that when executed by a computer, cause the computer to:

• store a tree data structure that comprises a root, a plurality of internal nodes, and a plurality of leaf nodes, each internal node comprising a pivot key and a child pointer, each leaf node storing key-value pairs sorted by a corresponding key, wherein the tree data structure comprises an index nodes layer and a leaf nodes layer;
• form a hybrid nodes layer between the index nodes layer and the leaf nodes layer, the hybrid nodes layer comprising a plurality of hybrid nodes, the hybrid nodes comprising a layer of internal nodes that are immediate parents of the plurality of leaf nodes, the index nodes layer comprising the root that points to nodes of the hybrid nodes layer, each node of the hybrid nodes layer pointing to one of the plurality of leaf nodes, the hybrid nodes combining features of the plurality of internal nodes and the plurality of leaf nodes;
• and
• form a plurality of buffers for the plurality of hybrid nodes, each internal node of the plurality of hybrid nodes having a corresponding buffer, the buffer being used to store a message that encodes an operation, the message to be applied to the corresponding leaf nodes of the leaf nodes layer.