Distributed database management system with dynamically split b-tree indexes

A method of splitting a first index atom in a plurality of atoms in a distributed database, the distributed database being distributed over a plurality of nodes, each node in the plurality of nodes comprising a corresponding processor and a corresponding memory to store replicas of at least some atoms in the plurality of atoms, each atom in the plurality of atoms containing a specific fragment of data and/or metadata of the distributed database, the plurality of atoms collectively representing all the data and/or metadata in the distributed database, the method comprising:

• at a first node in the plurality of nodes, the first node comprising a first processor and a first memory:
• selecting a split key value that defines first and second portions of the first index atom, the first index atom including a first fragment of the data and/or metadata associated with an index of a first table in the distributed database,
• creating a second index atom as a sibling of the first index atom,
• transferring key values in the second portion of the first index atom to the second index atom, and
• sending an index split message to a second node in the plurality nodes, the index split message including the split key value, the second node comprising a second processor and a second memory;
• and
• in the second node:
• generating a replica of the second index atom in response to the index split message;
• responding to the index split message by moving key values from a replica of the first index atom to the replica of the second index atom, the key values corresponding to the key values in the second portion of the first index atom, and
• sending a split done message to the first node, the split done message indicating that the replica of the first index atom at the second node has been split.