總結一下B樹和B+樹在不同是資料庫系統中的應用。
一、B樹和B+樹
1.1 B樹
B-Tree，即B樹或者B-樹。
一棵 m 階的 B 樹，需要滿足下列條件：
1. 定義任意非葉子結點最多隻有M個兒子，且M>2；
2. 根結點的兒子數為[2, M]；
3. 除根結點以外的非葉子結點的兒子數為[M/2, M]，向上取整；
4. 非葉子結點的關鍵字個數=兒子數-1；
5. 所有葉子結點位于同一層；
6. k個關鍵字把節點拆成k+1段，分别指向k+1個兒子，同時滿足查找樹的大小關系。 B樹的一些特點：
1. 關鍵字集合分布在整顆樹中；
2. 任何一個關鍵字出現且隻出現在一個結點中；
3. 搜尋有可能在非葉子結點結束；
4. 其搜尋性能等價于在關鍵字全集内做一次二分查找；
從上圖可以看出，key 為 50 的節點就在第一層，B-樹隻需要一次磁盤 IO 即可完成查找。是以說B-樹的查詢最好時間複雜度是 O(1)。
1.2 B+樹
m階的b+樹的特征：
1. 有n棵子樹的非葉子結點中含有n個關鍵字（b樹是n-1個），這些關鍵字不儲存資料，隻用來索引，所有資料都儲存在葉子節點（b樹是每個關鍵字都儲存資料）;
2. 所有的葉子結點中包含了全部關鍵字的資訊，及指向含這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序連結;
3. 所有的非葉子結點可以看成是索引部分，結點中僅含其子樹中的最大（或最小）關鍵字;
4. 通常在b+樹上有兩個頭指針，一個指向根結點，一個指向關鍵字最小的葉子結點;
5. 同一個數字會在不同節點中重複出現，根節點的最大元素就是b+樹的最大元素。
由于B+樹所有的 data 域都在根節點，是以查詢 key 為 50的節點必須從根節點索引到葉節點，時間複雜度固定為 O(log n)。
1.3 總結
通過以上的叙述和上面這張圖，基本可以知道B樹和B+樹的差別：
- B+ 樹中的節點不存儲資料，隻是索引，而 B 樹中的節點存儲資料；
- B 樹中的葉子節點并不需要連結清單來串聯。
從定義上來說，B+樹葉節點兩兩相連可大大增加區間通路性，可使用在範圍查詢等，而B-樹每個節點 key 和 data 在一起，無法區間查找。
事實上，例如oracle、MongoDB這樣使用B樹的資料，肯定是可以範圍查詢的，因為他們使用的B樹也是在葉子節點存儲行的位置資訊，資料在邏輯上是連續的。其實，B+樹就是 B樹的改進版。
二、Oracle裡的B樹
上圖顯示了oracle裡的單個索引。底部的空框表示索引指針指向的關聯表的塊
上圖DBA是：
database block address，是索引所在的實體檔案位置。DBAs包含檔案和塊。檔案是實體資料庫檔案，塊是資料所在的塊。使用DBA_EXTENTS視圖，您可以看到DBA位址與哪個對象相關聯。 上圖ROWID：
ROWID包含object＃，file＃，block＃和row＃，其中file＃是實體資料庫檔案，block＃是資料所在的塊，row＃是指向塊的指針。ROWID表示行所在塊中的唯一實體位置。
三、MongoDB裡的B樹
葉塊包含鍵值清單和指向磁盤上文檔位置的指針。
可以發現的是，MongoDB的B樹索引很大程度上和oracle類似。
例如，如果需要通路“BAKER”的記錄，我們首先會查詢标題塊。标題塊将告訴我們以A到K開頭的鍵值存儲在最左邊的分支塊中。通路此分支塊，我們發現以A到D開頭的鍵值存儲在最左邊的葉塊中。通路這個葉塊，我們找到值“BAKER”及其相關的磁盤位置，然後我們将使用它來擷取相關文檔。
四、MySQL裡的B+樹
2.1 MyISAM引擎索引實作
在MyISAM中，主索引和輔助索引（Secondary key）在結構上沒有任何差別，隻是主索引要求key是唯一的，而輔助索引的key可以重複。
2.1.1 主鍵索引
MyISAM引擎使用B+樹作為索引結構，葉節點的data域存放的是資料記錄的位址。
2.1.2 輔助索引
上圖是在Col2上建立一個二級索引。
同樣也是一棵B+樹，data域儲存資料記錄的位址。是以，MyISAM中索引檢索的算法為首先按照B+樹搜尋算法搜尋索引，如果指定的Key存在，則取出其data域的值，然後以data域的值為位址，讀取相應資料記錄。
MyISAM的索引方式也叫做“非聚集”的，之是以這麼稱呼是為了與InnoDB的聚集索引區分（可以發現和Oracle的B樹類似）
2.2 InnoDB引擎索引實作
Innodb是索引組織表。在InnoDB中，表資料檔案本身就是按B+樹組織的一個索引結構（就是索引組織表），這棵樹的葉節點data域儲存了完整的資料記錄。
2.2.1 主鍵索引
因為InnoDB的資料檔案本身要按主鍵聚集（聚集索引），是以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL會自動選擇一個可以唯一辨別資料記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隐含字段作為主鍵，這個字段長度為6個位元組，類型為長整型。
2.2.2 輔助索引
首先檢索輔助索引獲得主鍵，然後用主鍵到主索引中檢索獲得記錄。
參考：
https://blog.toadworld.com/2017/05/08/how-oracle-b-tree-indexes-work https://www.cnblogs.com/boothsun/p/8970952.html https://blog.csdn.net/login_sonata/article/details/75268075 https://dzone.com/articles/effective-mongodb-indexing-part-1