天天看點

MySQL核心月報 2014.08-TokuDB· 資料結構·Fractal-Trees與LSM-Trees對比

dr. bradley kuzmaul的結果是(頁13):

MySQL核心月報 2014.08-TokuDB· 資料結構·Fractal-Trees與LSM-Trees對比

從結果來看:

不過,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路徑是很明确的。

繼續閱讀