B樹（B-Tree）的由來、資料結構、基本操作以及資料庫索引的應用
B樹是為磁盤存儲而專門設計的一類平衡搜尋樹，B樹的高度僅随着它所包含的節點數按對數增長，不過因為單個節點可以包含多個關鍵字，是以對數的底數可以比較大，實際應用中一般是50~2000，給個直覺的數字，一棵分支因子為1001、高度為2（不包含根節點）的B樹，可以存儲超過10億個關鍵字！
1.從磁盤結構講起
計算機的機械磁盤，為了攤還機械移動花費的等待時間，磁盤會一次存取多個資料項而不是一個，這樣的一次讀取的資訊單元是page，我們可以用讀或寫的頁數作為磁盤存取總時間的主要近似值，在任何時刻，B樹算法都隻需在記憶體中保持一定數量的頁面。B樹的設計考慮磁盤預讀取這點，一個B樹的節點通常和一個完整磁盤頁（page）一樣大，并且磁盤頁的大小限制了一個B樹節點可以含有的孩子個數（分支因子），當然這個具體也需要取決于一個關鍵字相對一頁的大小。B+ Tree中内部節點隻存放關鍵字和孩子的指針，不存其他satellite information，是以最大化了内部節點的分支因子。
2.B樹的資料結構
typedef int KeyType;
#define m 3
struct Node{
int keynum; /* 結點中關鍵字的個數，即結點的大小*/
struct Node *parent; /*指向parent結點*/
KeyType key[m]; /*關鍵字向量*/
struct Node *ptr[m]; /*子樹指針向量*/
}; 
3.B樹的查找
搜尋一棵B樹和搜尋一棵二叉搜尋樹很相似，隻是在每個節點所做的不是二叉或者“兩路”分支選擇，而是根據根節點的孩子數做多路分支選擇。
4.B樹的插入
B樹插入的時候都是插入到葉節點上，插入的時候會從根節點開始順着葉節點的方向沿途，如果遇到一個滿節點（該節點上的關鍵字達到2t-1，t代表t階B樹），就會split該節點，分裂節點方式就是把滿節點上的中間關鍵字往根節點方向提，分裂是樹長高的唯一途徑。B樹的每個葉節點具有相同的高度，是以B樹高度的增加發生在頂部而不是底部。插入節點的時候，從根的方向往下判斷，如果不是葉子節點，則必須選擇适當的葉子節點插入，因為在沿途已經分裂了節點，是以保證不會在滿節點上再插入節點。
5.B樹的删除
和插入關鍵字類似，插入關鍵字的時候要保證節點不會太大，而且有可能會增高B樹。删除節點的時候要保證一個節點不會變得太小，因為B樹的節點上的關鍵字有下界要求（除了根節點以外的每個内部節點至少有t個孩子，如果樹非空，根節點上至少有一個關鍵字），删除關鍵字的時候如果在葉子節點，而且删除之後還滿足B樹的要求，那直接删除即可，不過如果是其他情況，比如在内部節點上删除關鍵字，那就有一系列的算法分支需要考慮，感興趣的讀者可以自行找資料慢慢琢磨了。不過在實際場景中，由于一棵B樹中大部分關鍵字都在葉節點中，删除操作最經常是從葉子節點中删除關鍵字。
6.B樹的應用場景
mysql的MyISAM和InnoDB兩個存儲引擎的索引實作方式：
- MyISAM引擎使用B+ Tree作為索引結構，葉節點存放的是資料記錄的位址。
- MyISAM引擎的輔助索引（二級索引）和主索引在結構上沒有差別，隻是輔助索引的key可以重複，葉節點上存放的也是資料記錄的位址。
- MyISAM索引檔案和資料檔案是分離的，索引檔案僅儲存資料記錄的位址。
- InnoDB中表資料本身就是按B+ Tree組織的一個索引結構，葉節點存放的就不是資料記錄的位址，而是完整的資料記錄。是以InnoDB這種存儲方式，又稱為聚集索引，使得按主鍵的搜尋十分高效，但二級索引搜尋需要檢索兩遍索引：首先二級索引獲得主鍵，然後用主鍵到主索引中檢索到資料記錄。
- 因為主鍵是InnoDB表記錄的”邏輯位址“，是以InnoDB要求表必須有主鍵，MyISAM可以沒有。
LSM樹由來、設計思想以及應用到HBase的索引
講LSM樹之前，需要提下三種基本的存儲引擎，這樣才能清楚LSM樹的由來：
- 哈希存儲引擎 是哈希表的持久化實作，支援增、删、改以及随機讀取操作，但不支援順序掃描，對應的存儲系統為key-value存儲系統。對于key-value的插入以及查詢，哈希表的複雜度都是O(1)，明顯比樹的操作O(n)快,如果不需要有序的周遊資料，哈希表就是your Mr.Right
- B樹存儲引擎是B樹的持久化實作，不僅支援單條記錄的增、删、讀、改操作，還支援順序掃描（B+樹的葉子節點之間的指針），對應的存儲系統就是關系資料庫（Mysql等）。
- LSM樹（Log-Structured Merge Tree）存儲引擎和B樹存儲引擎一樣，同樣支援增、删、讀、改、順序掃描操作。而且通過批量存儲技術規避磁盤随機寫入問題。當然凡事有利有弊，LSM樹和B+樹相比，LSM樹犧牲了部分讀性能，用來大幅提高寫性能。
通過以上的分析，應該知道LSM樹的由來了，LSM樹的設計思想非常樸素：将對資料的修改增量保持在記憶體中，達到指定的大小限制後将這些修改操作批量寫入磁盤，不過讀取的時候稍微麻煩，需要合并磁盤中曆史資料和記憶體中最近修改操作，是以寫入性能大大提升，讀取時可能需要先看是否命中記憶體，否則需要通路較多的磁盤檔案。極端的說，基于LSM樹實作的HBase的寫性能比Mysql高了一個數量級，讀性能低了一個數量級。
LSM樹原理把一棵大樹拆分成N棵小樹，它首先寫入記憶體中，随着小樹越來越大，記憶體中的小樹會flush到磁盤中，磁盤中的樹定期可以做merge操作，合并成一棵大樹，以優化讀性能。
以上這些大概就是HBase存儲的設計主要思想，這裡分别對應說明下：
- 因為小樹先寫到記憶體中，為了防止記憶體資料丢失，寫記憶體的同時需要暫時持久化到磁盤，對應了HBase的MemStore和HLog
- MemStore上的樹達到一定大小之後，需要flush到HRegion磁盤中（一般是Hadoop DataNode），這樣MemStore就變成了DataNode上的磁盤檔案StoreFile，定期HRegionServer對DataNode的資料做merge操作，徹底删除無效空間，多棵小樹在這個時機合并成大樹，來增強讀性能。
關于LSM Tree，對于最簡單的二層LSM Tree而言，記憶體中的資料和磁盤你中的資料merge操作，如下圖
圖來自lsm論文
lsm tree，理論上，可以是記憶體中樹的一部分和磁盤中第一層樹做merge，對于磁盤中的樹直接做update操作有可能會破壞實體block的連續性，但是實際應用中，一般lsm有多層，當磁盤中的小樹合并成一個大樹的時候，可以重新排好順序，使得block連續，優化讀性能。
hbase在實作中，是把整個記憶體在一定門檻值後，flush到disk中，形成一個file，這個file的存儲也就是一個小的B+樹，因為hbase一般是部署在hdfs上，hdfs不支援對檔案的update操作，是以hbase這麼整體記憶體flush，而不是和磁盤中的小樹merge update，這個設計也就能講通了。記憶體flush到磁盤上的小樹，定期也會合并成一個大樹。整體上hbase就是用了lsm tree的思路。