B+樹 vs LSM樹
前言：
在前面我們介紹到，性能優化之存儲性能優化有将（1）機械硬碟改成固态硬碟，（2）磁盤陣列方式RAID vs HDFS ，今天小編和大家分享一個在存儲過程，從資料結構方面來提升系統的性能，從資料結構B+樹 vs LSM樹來對比了解。
什麼是B+樹？
B+ 樹是一種專門針對磁盤存儲而優化的N叉排序樹， 一樹節點為機關存儲在磁盤中。從根開始查找所需要資料所在的節點編号和磁盤位置，将其加載到記憶體張然後繼續查找，直到找到所需要的資料。
什麼是LSM樹？
LSM樹原理把一棵大樹拆分成N棵小樹，它首先寫入記憶體中，随着小樹越來越大，記憶體中的小樹會flush到磁盤中，磁盤中的樹定期可以做merge操作，合并成一棵大樹，以優化讀性能。
特點：将對資料的修改增量保持在記憶體中，達到指定的大小限制後将這些修改操作批量寫入磁盤
B+樹原理：
對于傳統的極限磁盤有快速的順序讀寫、慢速的随機讀寫的通路特性，這個特性對磁盤存儲結構和算法的選擇影響較大，為了改善資料通路特性，檔案系統通常會對資料排序後進行存儲，加快資料的檢索速度，這就是要保證資料不斷更新、插入、删除後依然有序，傳統關系資料庫的做法就是使用B+數：
目前資料庫多是采用兩級索引的B+數，最多三層。是以可能需要5次磁盤通路才能更新一次記錄（3 次磁盤通路獲得資料索引行及ID，然後1 資料庫讀取操作及一次資料檔案寫操作）。但是由于每次磁盤通路都是随機的，而傳統機械磁盤在資料随機通路時性能較差，每次資料通路都需要多次通路磁盤，這就影響資料通路的性能，是以就有人改進了用NoSQL産品的LSM樹如下：
LSM樹可以看作是一個N階合并樹。資料寫操作（包括插入、修改、删除）都在記憶體中進行，并且都會建立一個新記錄（修改會記錄新的資料值，而删除會記錄一個删除标志），這些資料在記憶體中仍然還是一棵排序樹，當資料量超過設定的記憶體l閡值後，會将這棵排序樹和磁盤上最新的排序樹合并。當這棵排序樹的資料量也超過設定l閡值後，和磁盤＿L下一級的排序樹合并。合并過程中，會用最新更新的資料覆寫舊的資料（或者記錄為不同版本）。
LSM樹查找原理：
在需要進行讀操作時，LSM樹總是從記憶體中的排序樹開始搜尋，如果沒有找到，就從磁盤上的排序樹順序查找。
對比：
1，在LSM樹上進行一次資料更新不需要磁盤通路，在記憶體即可完成，速度遠快于B+樹。當資料通路以寫操作為主，而讀操作則集中在最近寫入的資料上時，使用LSM樹可以極大程度地減少磁盤的通路次數，加快通路速度。
2，當然凡事有利有弊，LSM樹和B+樹相比，LSM樹犧牲了部分讀性能，用來大幅提高寫性能。
作為存儲結構，B＋樹不是關系資料庫所獨有的，NoSQL資料庫也可以使用B＋樹。同理，關系資料庫也可以使用LSM，而且随着SSD硬碟的日趨成熟及大容帶持久存儲的記憶體技術的出現，相信B＋樹這一“古老”的存儲結構會再次煥發青春。