Proactive splitting and merging of nodes in a b e-tree

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

• obtaining a lock on a first node in a tree structure;
• obtaining a lock on a second node, wherein the second node is a child node of the first node;
• determining a quantity of child nodes of the second node;
• in response to determining that the quantity of child nodes is within a first range, performing a splitting operation on the second node while holding the first lock and the second lock, wherein the first range is between a maximum number of child nodes and one half of the maximum number of child nodes;
• and
• in response to determining that the quantity of child nodes is within a second range, performing a merging operation on the second node while holding the first lock and the second lock, wherein the second range is between one quarter of the maximum number of child nodes and one eighth of the maximum number of child nodes.

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:
• obtain a lock on a first node in a tree structure;
• obtain a lock on a second node, wherein the second node is a child node of the first node;
• determine a quantity of child nodes of the second node;
• in response to determining that the quantity of child nodes is within a first range, perform a splitting operation on the second node while holding the first lock and the second lock, wherein the first range is between a maximum number of child nodes and one half of the maximum number of child nodes;
• and
• in response to determining that the quantity of child nodes is within a second range, perform a merging operation on the second node while holding the first lock and the second lock, wherein the second range is between one quarter of the maximum number of child nodes and one eighth of the maximum number of child nodes.