3 ms·
This is not completely true. LSM does not just convert random write into sequential write. It also reduce the number of write IO when the dataset is larger tha
by skyde 5y ago
This is not completely true.
LSM does not just convert random write into sequential write.
It also reduce the number of write IO when the dataset is larger than memory.
With B-tree inserting a random entry require reading all b-tree page from disk until the right page is found then writing the updated page (4KB) back to disk.
While in LSM if you are trying to add a new entry that is 300byte you only need to append 300 bytes to the top level file on disk.
- vlovich123 5y agoRight. So it's more a problem of data dependency than it is with the access being random/sequential. Eg. if LSM needed to do 1 large sequential read & then jump around in RAM the same way, it would still largely have the same basic problem, no?
- skyde 5y agoWith LSM (leveldb, rocksdb) its just a different tradeoff. LSM Write are faster than b-tree (half write amplification) while B-tree read are faster than LSM. Reason is because with a warm cache B-tree requires at most one disk read per query since internal nodes will be in cache but for LSM you need one Read per Level. This advantage disappear if you don't have enough memory to cache all internal nodes. Another advantage with LSM is it only does half the space amplification as a B-tree. This is because all level except the top level contain long run of sorted data that compress very well. In a b-tree page are small and most page are not full and you need to store metadata in each page.