Method of building and appending data structures in a multi-host environment

A processor-based method of building and appending data structures in a multi-host environment, comprising:

• creating and storing data into a first data structure having a first root node, a first right leaf node and a plurality of other leaf nodes and non-leaf nodes defining multiple hierarchical levels:
• allowing a search of the first data structure to proceed while creating a second data structure that includes a second root node, a second left leaf node and a plurality of leaf nodes and non-leaf nodes defining multiple hierarchical levels;
• receiving a command to append the second data structure to the first data structure during searching the first data structure;
• creating a lock for all hosts in the multi-host environment to the first root node and the first right leaf node of the first data structure while allowing access to the plurality of other leaf nodes and non-leaf nodes of the first data structure;
• updating the first root node and the first right leaf node with intonation about the second data structure;
• committing the update of the first root node and the first right leaf node;
• releasing the lock to the first root node and the first right leaf node;
• sending updated copies of the first root node and the first right leaf node to other hosts in a multi-host environment;
• wherein the maximum database size and transaction rate is increased by allowing access by multi-hosts to all other nodes in the first data structure during appending the second data structure;
• and
• determining if the smallest value of the second left leaf node is greater than a largest value of the first right leaf node and, if not, stopping and issuing an error.