Comment Comment by leif > In that case all you've got is an in-memory queue that evaporates on a system crash.https://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf> Remember that merge operations are O(N). Then remember that there are N of them to do. O(N^2) is a horrible algorithmic complexity.No. Mountains of actual math refute this. LSM-tree merges are O(N log N). This is an Actual Fact.Read more, kids. parent leif 11 years ago
https://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf
> Remember that merge operations are O(N). Then remember that there are N of them to do. O(N^2) is a horrible algorithmic complexity.
No. Mountains of actual math refute this. LSM-tree merges are O(N log N). This is an Actual Fact.
Read more, kids.