Did you consider using an B-epsilon-tree [1] ? This is a B-tree, but each node has a staging area for new writes. In practice, incoming writes get added to the

Did you consider using an B-epsilon-tree [1] ? This is a B-tree, but each node has a staging area for new writes. In practice, incoming writes get added to the staging area of the root node, and once a staging area is full, it gets propagated down. This results in write performance that is similar to append-only. For reads, you get the performance of a regular B-tree. Sounds like a good match for your use case. [1] http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf