最近，TokuDB的創始人Dr. Bradley Kuzmaul發表了一篇文章:?[A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing](http://forms.tokutek.com/acton/attachment/6118/f-0039/1/-/-/-/-/lsm-vs-fractal.pdf)，從write amplification(WAMP), read amplification(RAMP), and space amplification三個方面對B-Trees，LSM-Trees(LSM)以及Fractal-Trees(FT)進行了詳細的分析和對比。 Dr. Bradley Kuzmaul的結果是(頁13):?  從結果來看： ~~~ 在WAMP上，FT跟LSM(leveled)是相同的 在RAMP(range)上，LSM(leveled)的復雜度明顯要高不少(FT的O(logN/B)倍) ~~~ 不過，RAMP這塊的分析有個小問題：? LSM(leveled)在實現上(比如LevelDB)，可以通過meta-info打＂錨點＂的方式，把RAMP(range)降低甚至做到跟FT一樣，如果是point queries的RAMP，則可以通過Bloom filter來降低。 具體的推導過程請閱讀原作，下面簡單分析下FT的RAMP為啥比LSM的要低。? FT的讀方式比較＂特殊＂，由于每個節點都有個message buffer，當有讀請求時，需要把inner node的message buffer數據（部分）推(apply)到leaf node，最后只在leaf node上做二分查找，所以RAMP基本就是樹的高度。 另外，在數據流向上(compaction過程中數據走向)，LSM強調"level"(橫向)，從level-L根據規則選取部分數據merge到level-(L+1)，如果選取數據的策略不好，會搶占磁盤帶寬，容易引起性能抖動，而FT強調"root-to-leaf"(縱向)，數據從root有序的逐層merge到leaf節點，每條數據的merge路徑是很明確的。