一 B樹
1.B樹的定義：B樹(B-tree)是一種樹狀資料結構，它能夠存儲資料、對其進行排序并允許以O(log n)的時間複雜度運作進行查找、順序讀取、插入和删除的資料結構。B樹，概括來說是一個節點可以擁有多于2個子節點的二叉查找樹。
2.B樹的特征：
- 根節點至少有兩個子節點
- 每個中間節點都包含k-1個元素和k個孩子，其中 m/2 ≤ k ≤ m (m為樹的階)
- 每個葉子節點都包含k-1個元素，其中 m/2 ≤ k ≤ m (m為樹的階)
- 每個節點中的元素從小到大排列，節點當中k-1個元素正好是k個孩子包含的元素的值域劃分(一個結點有k個孩子時，必有k-1個元素才能将子樹中所有元素劃分為k個子集)
3.B樹的操作
3.1 B樹的查找：如下圖，查詢元素8
第一次磁盤IO：把15所在節點讀到記憶體中，然後與8做比較，小于15，找到下一個節點(5和9對應的節點)
第二次磁盤IO：把5和9所在的節點讀到記憶體中，然後與8做比較，5<8<9，找到下一個節點(6和8對應的節點)
第三次磁盤IO：把6和8所在節點讀到記憶體中，然後與8做比較，找到了元素8
3.1 B樹的插入： 将元素7插入下圖中的B樹
步驟一：自頂向下查找元素7應該在的位置，即在6和8之間
步驟二：三階B樹中的節點最多有兩個元素，把6 7 8裡面的中間元素上移(中間元素上移是插入操作的關鍵)
步驟三：上移之後，上一層節點元素也超載了，5 7 9中間元素上移，現在根節點變為了 7 15
步驟四：要對B樹進行調整，使其滿足B樹的特性，最終如下圖：
二 B+樹
B+樹是B樹的一種變形體，它與B樹的差異在于：
- 有K個子節點的節點必然有K個關鍵碼
- 非葉節點僅具有索引作用，元素資訊均存放在葉節點中
- 樹的所有葉節點構成一個有序連結清單，可以按照關鍵碼排序的次序周遊全部記錄
B+樹的優勢：
- 由于B+樹在内部節點上不包含資料資訊，是以在記憶體頁中能夠存放更多的key。 資料存放的更加緊密，具有更好的空間局部性。是以通路葉子節點上關聯的資料也具有更好的緩存命中率。
- B+樹的葉子節點都是相連的，是以對整棵樹的周遊隻需要一次線性周遊葉子節點即可。而且由于資料順序排列并且相連，是以便于區間查找和搜尋。而B樹則需要進行每一層的遞歸周遊。相鄰的元素可能在記憶體中不相鄰，是以緩存命中性沒有B+樹好。
總結：我們知道二叉查找樹的時間複雜度是Ｏ(logN)，效率已經足夠高。為什麼出現B樹和B+樹呢？當大量資料存儲在磁盤上，進行查詢操作時，需要先将資料加載到記憶體中(磁盤IO操作)，而資料并不能一次性全部加載到記憶體中，隻能逐一加載每個磁盤頁(對應樹的一個節點)，并且磁盤IO操作很慢，平衡二叉樹由于樹深度過大而造成磁盤IO讀寫過于頻繁，進而導緻效率低下。為了減少磁盤IO的次數，就需要降低樹的深度，那麼就引出了B樹和B+樹：每個節點存儲多個元素，采用多叉樹結構。這樣就提高了效率，比如資料庫索引，就是存儲在磁盤上，采用的就是B+樹的資料結構。