動态查找樹主要有二叉查找樹（binary search tree），平衡二叉查找樹（balanced binary search tree）， 紅黑樹 (red-black tree )，
都是典型的二叉查找樹結構，查找的時間複雜度 o(log2-n) 與樹的深度相關，降低樹的深度會提高查找效率，于是有了多路的b-tree/b+-tree/ b*-tree (b~tree)。
關于這b樹以及b樹的兩種變體，其實很好區分，
相比b樹，b+樹不維護關鍵字具體資訊，不考慮value的存儲，所有的我們需要的資訊都在葉子節點上，
b*樹在b+樹的基礎上增加了非葉子節點兄弟間的指針，在某些場景效率更高，
主要掌握b樹的操作，也就掌握了這兩種變體樹的操作。
注意b樹也就是b-樹，b樹的英文是b-tree，很多地方直譯成了b-樹，其實b-樹和b樹是同一種樹。
b樹是為了磁盤或其它儲存設備而設計的一種多叉平衡查找樹。
（1）b-tree的接點結構
b-tree中，每個結點包含：
本結點所含關鍵字的個數；
指向父結點的指針；
關鍵字；
指向子結點的指針數組；
1
2
3
4
5
6
7
8
9
10
<code>#define max l000 //結點中關鍵字的最大數目：max=m-1，m是b-樹的階</code>
<code>#define min 500 //非根結點中關鍵字的最小數目：min=m/2-1</code>
<code>typedef</code> <code>int</code> <code>keytype； </code><code>//keytype關鍵字類型由使用者定義</code>
<code>typedef</code> <code>struct</code> <code>node{ </code><code>//結點定義中省略了指向關鍵字代表的記錄的指針</code>
<code> </code><code> </code><code>int</code> <code>keynum； </code><code>//結點中目前擁有的關鍵字的個數，keynum<<max</code>
<code> </code><code> keytype key[max+1]； </code><code>//關鍵字向量為key[1..keynum]，key[0]不用。</code>
<code> </code><code> </code><code>struct</code> <code>node *parent； </code><code>//指向雙親結點</code>
<code> </code><code> </code><code>struct</code> <code>node *son[max+1]；</code><code>//指向孩子結點的指針數組，孩子指針向量為son[0..keynum]</code>
<code> </code><code>}btreenode；</code>
<code>typedef</code> <code>btreenode *btree；</code>
（2）b-tree的特點
b-tree是一種多路搜尋樹（并不是二叉的），對于一棵m階樹：
定義任意非葉子結點最多隻有m個孩子；且m>2；
根結點的孩子數為[2, m]，除非根結點為葉子節點；
除根結點以外的非葉子結點的兒子數為[m/2, m]；
非葉子結點的關鍵字個數=指向兒子的指針個數-1；
每個非葉子結點存放至少m/2-1（取上整）和至多m-1個關鍵字；
非葉子結點的關鍵字：k[1], k[2], …, k[m-1]；且k[i] < k[i+1]；
非葉子結點的指針：p[1], p[2], …, p[m]；其中p[1]指向關鍵字小于k[1]的子樹，p[m]指向關鍵字大于k[m-1]的子樹，其它p[i]指向關鍵字屬于(k[i-1], k[i])的子樹；
所有葉子結點位于同一層；
以m=3的一棵3階b樹為例：
一棵包含了24個英文字母的5階b樹的結構：
（3）b-tree高度與複雜度
b樹的高度是
，而不是其它幾種樹的h=log2n，其中t為度數（每個節點包含的元素個數），即所謂的階數，n為總元素個數或總關鍵字數。
b樹查找的時間複雜度為o(log2-n)，下面是參考推導過程：
其中m為設定的非葉子結點最多子樹個數，n為關鍵字總數；是以b-樹的性能總是等價于二分查找（與m值無關），也就沒有avl樹平衡的問題。
（1）查找操作
在b-樹中查找給定關鍵字的方法類似于二叉排序樹上的查找。不同的是在每個結點上确定向下查找的路徑不一定是二路而是keynum+1路的。
對結點内的存放有序關鍵字序列的向量key[l..keynum] 用順序查找或折半查找方法查找。若在某結點内找到待查的關鍵字k，則傳回該結點的位址及k在key[1..keynum]中的位置；否則，确定k在某個key[i]和key[i+1]之間結點後，從磁盤中讀son[i]所指的結點繼續查找。直到在某結點中查找成功；或直至找到葉結點且葉結點中的查找仍不成功時，查找過程失敗。
11
12
13
14
15
16
17
<code>btreenode *searchbtree(btree t，keytype k，</code><code>int</code> <code>*pos)</code>
<code> </code><code>{ </code><code>//在b-樹t中查找關鍵字k，成功時傳回找到的結點的位址及k在其中的位置*pos</code>
<code>//失敗則傳回null，且*pos無定義</code>
<code> </code><code>int</code> <code>i；</code>
<code> </code><code>t→key[0]=k; </code><code>//設哨兵．下面用順序查找key[1..keynum]</code>
<code> </code><code>for</code><code>(i=t->keynum；k<t->key[i];i--)； </code><code>//從後向前找第1個小于等于k的關鍵字</code>
<code> </code><code>if</code><code>(i>0 && t->key[i]==1){ </code><code>//查找成功，傳回t及i</code>
<code> </code><code>*pos=i；</code>
<code> </code><code>return</code> <code>t；</code>
<code> </code><code>} </code><code>//結點内查找失敗，但t->key[i]<k<t->key[i+1]，下一個查找的結點應為</code>
<code> </code><code>//son[i]</code>
<code> </code><code>if</code><code>(!t->son[i]) </code><code>//*t為葉子，在葉子中仍未找到k，則整個查找過程失敗</code>
<code> </code><code>return</code> <code>null；</code>
<code> </code><code>//查找插入關鍵字的位置，則應令*pos=i，并傳回t，見後面的插入操作</code>
<code> </code><code>diskread(t->son[i])； </code><code>//在磁盤上讀人下一查找的樹結點到記憶體中</code>
<code> </code><code>return</code> <code>searchbtree(t->son[i]，k，pos)； </code><code>//遞歸地繼續查找于樹t->son[i]</code>
<code> </code><code>}</code>
（2）查找操作的時間開銷
b-樹上的查找有兩個基本步驟：
1.在b-樹中查找結點，該查找涉及讀盤diskread操作，屬外查找；
2.在結點内查找，該查找屬内查找。
查找操作的時間為：
1.外查找的讀盤次數不超過樹高h，故其時間是o(h)；
2.内查找中，每個結點内的關鍵字數目keynum<m(m是b-樹的階數)，故其時間為o(nh)。
注意：
1.實際上外查找時間可能遠遠大于内查找時間。
2.b-樹作為資料庫檔案時，打開檔案之後就必須将根結點讀人記憶體，而直至檔案關閉之前，此根一直駐留在記憶體中，故查找時可以不計讀入根結點的時間。
（3）插入操作
插入一個元素時，首先在b樹中是否存在，如果不存在，即在葉子結點處結束，然後在葉子結點中插入該新的元素，注意：如果葉子結點空間足夠，這裡需要向右移動該葉子結點中大于新插入關鍵字的元素，如果空間滿了以緻沒有足夠的空間去添加新的元素，則将該結點進行“分裂”，将一半數量的關鍵字元素分裂到新的其相鄰右結點中，中間關鍵字元素上移到父結點中（當然，如果父結點空間滿了，也同樣需要“分裂”操作），而且當結點中關鍵元素向右移動了，相關的指針也需要向右移。如果在根結點插入新元素，空間滿了，則進行分裂操作，這樣原來的根結點中的中間關鍵字元素向上移動到新的根結點中，是以導緻樹的高度增加一層。
（4）删除操作
首先查找b樹中需删除的元素,如果該元素在b樹中存在，則将該元素在其結點中進行删除，如果删除該元素後，首先判斷該元素是否有左右孩子結點，如果有，則上移孩子結點中的某相近元素到父節點中，然後是移動之後的情況；如果沒有，直接删除後，移動之後的情況。
b+-tree是應檔案系統所需而産生的一種b-tree的變形樹。
（1）b樹和b+樹的對比
一棵m階的b+樹和m階的b樹的異同點在于：
1.有n棵子樹的結點中含有n-1 個關鍵字；
2.所有的葉子結點中包含了全部關鍵字的資訊，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序連結。 (而b 樹的葉子節點并沒有包括全部需要查找的資訊)
3.所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最小）關鍵字。 (而b 樹的非終節點也包含需要查找的有效資訊)
（2）為什麼說b+-tree比b 樹更适合實際應用中作業系統的檔案索引和資料庫索引？
b+-tree的磁盤讀寫代價更低
b+-tree的内部結點并沒有指向關鍵字具體資訊的指針。是以其内部結點相對b 樹更小。
如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。
一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說io讀寫次數也就降低了。
舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體資訊指針2bytes。
一棵9階b-tree(一個結點最多8個關鍵字)的内部結點需要2個盤快。而b+ 樹内部結點隻需要1個盤快。當需要把内部結點讀入記憶體中的時候，b 樹就比b+ 樹多一次盤塊查找時間(在磁盤中就是盤片旋轉的時間)。
b+-tree的查詢效率更加穩定
由于非終結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。
b*-tree是b+-tree的變體，在b+樹的基礎上(所有的葉子結點中包含了全部關鍵字的資訊，及指向含有這些關鍵字記錄的指針)，
b*樹中非根和非葉子結點再增加指向兄弟的指針；
b*樹定義了非葉子結點關鍵字個數至少為(2/3)*m，即塊的最低使用率為2/3（代替b+樹的1/2）。
下圖是一棵典型的b*樹：