B+ Tree、LSM、Fractal tree index 讀寫放大分析
最近剛看完一個還不錯的基于B+ Tree實作的kv引擎，借着這股勁兒剛好補充了一下相關理論知識，對比着看其他資料（資料1、資料2、資料3、資料4）看了下《A Comparison of Fractal Trees to Log-Structured Merge (LSM) Trees》論文，我比較願意扣細節，是以看得那叫一個費勁，不過裡面的分析還挺有意思，是以這裡寫篇部落格，套着論文的結論，按着自己的了解總結一下
相關定義
1. RAM、DAM
RAM（Random Access Machine model）假設計算機有無窮大小的記憶體，并且通路記憶體任何位址都用相同的機關時間。當機器實際記憶體滿足某個算法理論需要的記憶體時，RAM可以很好的描述該算法的複雜度。然而假設機器實際記憶體不夠時，作業系統将部分記憶體換出到磁盤并在需要時重新換回記憶體，雖然這對程式自身來說可以無感覺，不過客觀來看，還是不得不面對此刻的兩種“記憶體”（記憶體+磁盤），他們的通路時間是100ns和10ms的差別，如此大的差距如果繼續使用RAM一視同仁，那麼此時對複雜度的分析是不準确的。
DAM（Disk-Access model也叫Standard External-Memory model)有如下定義：
1. 一台機器有一個處理器、一個可以包含M個objects的記憶體以及無窮大小的外存
2. 在一次I/O操作中，計算機可以在記憶體和外存之間傳輸包含B objects的block，其中1 < B < M
3. 一個算法的Running Time可以定義為在算法執行期間I/O的次數、隻用記憶體資料進行的計算可以認為是沒有代價的
4. 一個資料結構的大小可以定義成可以包含它的blocks數的大小
對于外存結構來說，無疑使用DAM來分析不同資料結構的優劣更為合适，隻需要分析每種資料結構在各種操作中所涉及的I/O次數即可
2. 讀放大、寫放大
寫放大：Write amplification is the amount of data written to storage compared to the amount of data that the application wrote，也就是說實際寫入磁盤的資料大小和程式要求寫入資料大小之比
讀放大：Read amplification is the number of I/O’s required to satisfy a particular query，也就是一次查詢所需要的I/O數
分析
1. B+ Tree
為了友善分析，我們進行相關約定，B+ Tree的block size為B，故每個内部節點包含O(B)個子節點，葉子節點包含O(B)條資料，假設資料集大小為N，則B+ Tree的高度為O((log N/B)/(log B))
寫放大：B+ Tree的每次insert都會在葉子節點寫入資料，不論資料實際大小，每次都需要寫入B，是以寫放大是B
讀放大：B+ Tree的一次查詢需要從根節點一路查到具體的某個葉子節點，是以需要等于層數大小的I/O，也就是O((log N/B)/(log B))， 即寫放大為O((log N/B)/(log B))
2. Factal Tree Index
與B+ Tree稍有不同，FTI将每個block從中分一部分用作buffer，假設每個block size 為B，現在每個内部節點擁有K個子節點（k可以等于根号下B），則FTI的高度為O((log N/B)/(log K))
寫放大：當root的buffer滿了之後，需要将buffer中的records推到子節點的buffer中，一般情況下，每個子節點收到B/K個records，也就是說每B/K個records産生一次I/O，也就是寫入B，那麼每一個record産生K/B次I/O，也就是寫入K，同樣一條record，每往下推一層就産生K/B次I/O，寫入K，是以一共寫入O(K(log N/B)/(log K))，即寫放大為O(K(log N/B)/(log K))
讀放大：同B+ Tree一樣，和樹的高度相關，不過此時的高度為O((log N/B)/(log K))，即讀放大為O((log N/B)/(log K))
3. LSM Tree
Leveld LSM Tree
假設資料集大小為N，放大因子為k，最小層一個檔案大小為B，每層檔案的單個檔案大小相同都為B，不過每層檔案個數不同
寫放大：同一個record，會在本層寫k次之後才會被compact到下一層，也就是說每次層會放大k，一共有層數O((log N/B)/(log B))，故寫放大為O(k(log N/B)/(log B))
讀放大：依次在每一層進行二分查找，直到在最後一層找到，即： R = (log N/B) + (log N/Bk) + (log N/Bkk) + … + 1 = (log N/B) + (log N/B) - (log k) + (log N/B) - 2(log k) +… + 1 會有R次I/O，故讀放大為R，即O((log N/B)*(log N/B)/(log k))
Size-tired LSM Tree
假設資料集大小為N，放大因子為k，最大層有k個大小為N/k個檔案，倒數第二層有k個N/kk個檔案…那麼一共有O((log N/B)/(log k))層
寫放大：同一個record，在每一層隻會寫一次，是以寫放大等于層數，即O((log N/B)/(log k))
讀放大：每一層讀k個檔案，一共O((log N/B)/(log k))層，故一共需要讀O(k(log N/B)/(log k))個檔案，不同于Leveld LSM Tree，一個檔案不隻是一個block B，而是有很多blocks，近似O(N/B)個，在檔案内部二分查找找到對應的block需要O(log N/B)，故整體需要O(k(log N/B)(log N/B)/(log k))次I/O，即讀放大為O(k(log N/B)(log N/B)/(log k))
總結
- Fractal Tree Index 在寫放大和讀放大友善表現的都很不錯
- Leveld LSM Tree 在寫放大方面和FTI差不多，但是讀放大方面比FTI要差
- Size-tired LSM Tree 在寫放大方面優于FTI和Leveld LSM Tree，但讀放大方面表現最差，一般少讀多寫并對寫性能有較高要求的場景下考慮使用Size-tired LSM Tree
- B+ Tree 有較高的寫放大，但是在讀放大方面不錯