部分内容轉載自網際網路
<a href="https://en.wikipedia.org/wiki/b-tree">https://en.wikipedia.org/wiki/b-tree</a>
<a href="https://en.wikipedia.org/wiki/b%2b_tree">https://en.wikipedia.org/wiki/b%2b_tree</a>
為了描述b-tree，首先定義一條資料記錄為一個二進制組[key, data]，key為記錄的鍵值，對于不同資料記錄，key是互不相同的；data為資料記錄除key外的資料。那麼b-tree是滿足下列條件的資料結構：
.1. d為大于1的一個正整數，稱為b-tree的度。
.2. h為一個正整數，稱為b-tree的高度或深度。
.3. 每個非葉子節點由n-1個key和n個指針組成，其中d<=n<=2d。
.4. 每個葉子節點最少包含一個key和兩個指針，最多包含2d-1個key和2d個指針，葉節點的指針均為null(因葉子節點是最底層的節點，不需要再指向其他節點) 。
.5. 所有葉節點具有相同的深度，等于樹高h。
.6. key和指針互相間隔，節點兩端是指針，是以節點中指針比key多一個。
.7. 一個節點中的key從左到右非遞減(即升序)排列。
.8. 所有節點組成樹結構。
.9. 每個指針要麼為null，要麼指向另外一個節點。
.10. 如果某個指針在節點node最左邊且不為null，則其指向節點的所有key小于v(key1)，其中v(key1)為node的第一個key的值。
.11. 如果某個指針在節點node最右邊且不為null，則其指向節點的所有key大于v(keym)，其中v(keym)為node的最後一個key的值。
.12. 如果某個指針在節點node的左右相鄰key分别是keyi和keyi+1且不為null，則其指向節點的所有key小于v(keyi+1)且大于v(keyi)。
圖2 是一個d=2的b-tree示意圖。
圖2
由于b-tree的特性，在b-tree中按key檢索資料的算法非常直覺：
首先從根節點進行二分查找，如果找到則傳回對應節點的data，否則對相應區間的指針指向的節點遞歸進行查找，直到找到節點或找到null指針，前者查找成功，後者查找失敗。
b-tree上查找算法的僞代碼如下：
關于b-tree有一系列有趣的性質，例如一個度為d的b-tree，設其索引n個key，則其樹高h的上限為logd((n+1)/2)，檢索一個key，其查找節點個數的漸進複雜度為o(logdn)。
從這點可以看出，b-tree是一個非常有效率的索引資料結構。
另外，由于插入删除新的資料記錄會破壞b-tree的性質，是以在插入删除時，需要對樹進行一個分裂、合并、轉移等操作以保持b-tree性質。
b-tree有許多變種，其中最常見的是b+tree，例如mysql就普遍使用b+tree實作其索引結構。
與b-tree相比，b+tree有以下不同點：
.1. 每個節點的指針上限為2d而不是2d+1。(上下沖突?)
.2. 内節點不存儲data，隻存儲key；葉子節點不存儲指針。
圖3 是一個簡單的b+tree示意。
圖3
由于并不是所有節點都具有相同的域，是以b+tree中葉節點和内節點一般大小不同。
這點與b-tree不同，雖然b-tree中不同節點存放的key和指針可能數量不一緻，但是每個節點的域和上限是一緻的，是以在實作中b-tree往往對每個節點申請同等大小的空間。
本質差别是b-tree的每個node都記錄了data，是以不是每次都要搜葉子節點才能拿到data。
b+tree，隻有葉子節點有data，是以，每次都要搜到葉子節點取data。
但是b+tree在葉子節點上可以加指向下一個葉子節點的指針，是以範圍掃描，b+tree占優，比如排序。
一般在資料庫系統或檔案系統中使用的b+tree結構都在經典b+tree的基礎上進行了優化，增加了順序通路指針(稱為b* tree)。
圖4
如圖4 所示，在b+tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序通路指針的b+tree。做這個優化的目的是為了提高區間通路的性能，例如圖4中如果要查詢key為從18到49的所有資料記錄，當找到18後，隻需順着節點和指針順序周遊就可以一次性通路到所有資料節點，極大提到了區間查詢效率。
b+樹的分裂：當一個結點滿時，配置設定一個新的結點，并将原結點中1/2的資料複制到新結點，最後在父結點中增加新結點的指針；
b+樹的分裂隻影響原結點和父結點，而不會影響兄弟結點，是以它不需要指向兄弟的指針。
b*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那麼将一部分資料移到兄弟結點中，再在原結點插入關鍵字，最後修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字範圍改變了）；
如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各複制1/3的資料到新結點，最後在父結點增加新結點的指針。
是以，b*樹配置設定新結點的機率比b+樹要低，空間使用率更高；
也是一種增強版本，具體算法見
src/backend/access/nbtree/readme
主要用了兩篇論文中的算法，postgresql的插入性能是非常有保障的.
lehman & yao algorithm算法優化
添加了一個右指針(like b+tree)，以及一個upper bound value（解決了分裂的并發問題）。
mysql的請參考
<a href="http://tech.it168.com/a2011/0711/1216/000001216087_all.shtml">http://tech.it168.com/a2011/0711/1216/000001216087_all.shtml</a>