首先，b樹和b-樹是一種東西，不存在什么“b減樹”。
“B-tree，B即Balanced，平衡的意思。因為B樹的原英文名稱為B-tree，而國內(nèi)很多人喜歡把B-tree譯作B-樹，其實，這是個非常不好的直譯，很容易讓人產(chǎn)生誤解，可能會以為B-樹是一種樹，而B樹又是另一種樹。而事實上是，B-tree就是指的B樹。特此說明。”

b樹

概述：
b-樹是一種多叉平衡查找樹，一個結(jié)點可以存放多個關(guān)鍵字（從小到大排序），每個關(guān)鍵字有左右兩個指針分別指向子節(jié)點，左子樹中的所有關(guān)鍵字小于它，右子樹中的所有關(guān)鍵字大于它。

對于一個m階b樹需要滿足以下條件：

• 樹中的節(jié)點最多可以有m個子節(jié)點；且M>2
• 每個內(nèi)部節(jié)點（非葉和非根）的子節(jié)點數(shù)目[(M/2)(向上舍入), M]，根的子節(jié)點數(shù)目[2, M]
• 具有k個子節(jié)點的非葉節(jié)點應(yīng)具有k-1鍵（這一點可以推出，每個結(jié)點存放至少M/2-1（取上整）和至多M-1個關(guān)鍵字）
• 所有葉子結(jié)點位于同一層
• (大小關(guān)系)非葉子結(jié)點的指針：P[1], P[2], …, P[M]；其中P[1]指向關(guān)鍵字小于K[1]的子樹，P[M]指向關(guān)鍵字大于K[M-1]的子樹，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹。簡要理解就是，左指針指向小的，右指針指向大的。

下圖中的左右白色長方形，就分別代表左右指針，葉子節(jié)點的指針為空

b樹的構(gòu)建，其實是一個不斷插入結(jié)點并根據(jù)以上條件調(diào)整結(jié)構(gòu)的過程。具體過程此處不再贅述，可以簡略看一下這一篇文章，The Difference Between B-trees and B+trees。

b樹的查找。簡要來說，搜索當(dāng)前結(jié)點的所有Key，找到第一個大于等于target的key，如果key==target就可以返回value，否則說明要去查找子節(jié)點。如果當(dāng)前結(jié)點是葉子結(jié)點，沒有子節(jié)點，則查找失敗，返回null。否則遞歸查找第i個子節(jié)點。
注意，下面的圖中，再單個結(jié)點的搜索用的是線性查找，可以使用二分查找進(jìn)一步提高效率。

Search Algorithm

時間復(fù)雜度
B樹查找的時間復(fù)雜度為O(Log2-N)，N為關(guān)鍵字總數(shù)。具體可以參考Best case and worst case heights與二叉樹學(xué)習(xí)筆記之B樹、B+樹、B*樹。
思路是：
B-樹上的查找有兩個基本步驟：
1.在B-樹中查找結(jié)點，該查找涉及讀盤DiskRead操作，屬外查找；
2.在結(jié)點內(nèi)查找，該查找屬內(nèi)查找。
查找操作的時間為：
1.外查找的讀盤次數(shù)不超過樹高h(yuǎn)，故其時間是O(h)；
2.內(nèi)查找中，每個結(jié)點內(nèi)的關(guān)鍵字?jǐn)?shù)目keynum<= m - 1(m是B-樹的階數(shù))，如果算二分查找，時間是O(log2 m)

b+樹

b+樹是b樹最著名的版本。具有兩個b樹不具備的特征：

• 葉子結(jié)點使用雙向指針相互連接

• 數(shù)據(jù)僅存儲在葉節(jié)點上。內(nèi)部節(jié)點僅持有key并充當(dāng)一種路由作用

  
  

b+樹的插入、查找、刪除等操作，具體可以看B+-trees。這里簡要提一下它的查找操作，由于b+樹的具體數(shù)據(jù)都儲存在葉子結(jié)點，它的查找過程必須從根節(jié)點一直查到葉子。具體算法過程為：

• 更適合范圍查詢
  對于范圍查詢，只需要精確查找到范圍中最小的key，然后跟著雙指針直到查找到了最大的key
• B+-tree的磁盤讀寫代價更低
  B+-tree的內(nèi)部結(jié)點并沒有指向關(guān)鍵字具體信息的指針。因此其內(nèi)部結(jié)點相對B 樹更小。
  如果把所有同一內(nèi)部結(jié)點的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。
  一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對來說IO讀寫次數(shù)也就降低了。
  舉個例子，假設(shè)磁盤中的一個盤塊容納16bytes，而一個關(guān)鍵字2bytes，一個關(guān)鍵字具體信息指針2bytes。
  一棵9階B-tree(一個結(jié)點最多8個關(guān)鍵字)的內(nèi)部結(jié)點需要2個盤快。而B+ 樹內(nèi)部結(jié)點只需要1個盤快。當(dāng)需要把內(nèi)部結(jié)點讀入內(nèi)存中的時候，B 樹就比B+ 樹多一次盤塊查找時間(在磁盤中就是盤片旋轉(zhuǎn)的時間)。
• B+-tree的查詢效率更加穩(wěn)定
  由于非終結(jié)點并不是最終指向文件內(nèi)容的結(jié)點，而只是葉子結(jié)點中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點到葉子結(jié)點的路。所有關(guān)鍵字查詢的路徑長度相同，導(dǎo)致每一個數(shù)據(jù)的查詢效率相當(dāng)。
• B+樹支持存儲重復(fù)數(shù)據(jù)，且由于數(shù)據(jù)都存儲在葉子結(jié)點，更加容易進(jìn)行刪除操作

參考

https://www.baeldung.com/cs/b-trees-vs-btrees
https://www.cnblogs.com/myseries/p/12532919.html
https://blog.csdn.net/weixin_42462202/article/details/104335419