Static sorted index replication

A method, comprising:

• performing, by one or more computers:
• receiving data to store in a distributed data store, wherein the distributed data store includes a plurality of tree-based replicas, wherein individual ones of the tree-based replicas are implemented as respective data structures in a memory tree that refers to leaf nodes of data stored in a fragmented form, and wherein the fragmentation changes in response to write requests;
• storing the received data in a respective memory tree of one of the plurality of tree-based replicas, wherein the received data is stored in leaf nodes of the memory tree in the fragmented form;
• generating a static sorted index from the respective memory tree, wherein the static sorted index is generated so that the received data is stored in a sorted order and in a non-fragmented form in the static sorted index, and wherein the static sorted index is made read only after it is generated;
• based at least in part on a determination that a first query to the distributed data store is a range query, performing the first query using the static sorted index;
• and
• based at least in part on a determination that a second query to the distributed data store is other than a range query, performing the second query using one of the plurality of tree-based replicas.

A non-transitory computer-readable storage medium storing program instructions, wherein the program instructions are computer-executable to implement:

• receiving data to store in a distributed data store, wherein the distributed data store includes a plurality of tree-based replicas, wherein individual ones of the tree-based replicas are implemented as respective data structures in a memory tree that refers to leaf nodes of data stored in a fragmented form, and wherein the fragmentation changes in response to write requests;
• storing the received data in a respective memory tree of one of the plurality of tree-based replicas, wherein the received data is stored in leaf nodes of the memory tree in the fragmented form;
• generating a static sorted index from the respective memory tree, wherein the static sorted index is generated so that the received data is stored in a sorted order and in a non-fragmented form in the static sorted index, and wherein the static sorted index is made read only after it is generated;
• based at least in part on a determination that a first query to the distributed data store is a range query, performing the first query using the static sorted index;
• and
• based at least in part on a determination that a second query to the distributed data store is other than a range query, performing the second query using one of the plurality of tree-based replicas.