Two excellent comments on Quora explaining the differences in the performance of write operation when using 3 different data structures: B+trees, Log-Structured Merge trees, and Fractal trees:
- B+Tree and LSM tree are mentioned in Why are the writes of Cassandra executed faster than MySQL’s. InnoDB is using B+trees, while Cassandra is using LSM trees (BigTable is using LSM trees too).
- LSM trees and Fractal trees are compared in What are the major differences between LSM trees (used in BigTable) and Fractal Tress (used in TokuDB)
If you want me to spoil the fun of going through those answers, then Fractal tress are faster than LSM trees which are faster than B+tress. Interestingly enough, Fractal trees have more similar features to B-tress than LSM trees have.
Original title and link: Writes Performance: B+Tree, LSM Tree, Fractal Tree (NoSQL databases © myNoSQL)