Implement a proper b-tree #596
Assignees
Milestone
Comments
This was referenced Sep 29, 2021
arv
added a commit
that referenced
this issue
Oct 26, 2021
This adds a B+Tree that we use instead of the prolly tree. The old prolly tree was not actually using a prolly tree but a flat array of entries. That meant that we read and wrote all the data on every transaction which of course is not very fast. With a B+Tree we only load the parts of the Map that you are interested in. The current target chunk size is 8kb (min is 8kb and max is 16kb) Fixes #596
arv
added a commit
to arv/replicache
that referenced
this issue
Nov 1, 2021
arv
added a commit
that referenced
this issue
Nov 2, 2021
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Replicache was designed from the beginning to utilize an append-only/immutable tree data structure internally for good performance.
In our early prototyping and discovery phase we skipped implementing this to focus more on the product and to give time to think about exactly what the right data structure was. Right now Replicache simply copies its entire internal dataset on every mutation. This works kind of surprisingly well, given how absurdly inefficient it is, but obviously can't stand.
Now that we have lots of customer feedback and know where we're going, it's time to do this properly so that we can hit our local perf goals (see rocicorp/mono#134).
Thinking on the right data structure has converged on a merkle b+ tree. See design doc for details: https://docs.google.com/document/d/1RCsz5cBxaD4Xny5Pda5ONkdujxcUJfcfTrWF--yx744/edit?usp=sharing
The text was updated successfully, but these errors were encountered: