二叉搜索樹不適合應用到磁盤上，因為它的扇出數較低並且平衡時需要大量的節點重定位和指針更新。B樹通過增加每個節點存儲項的數量(高扇出)和減少頻繁的平衡操作來解決這些問題。下面我們將討論了B樹的內部結構，B樹的查找、插入和刪除操作算法概要，以及用於保持B樹平衡的拆分和合並操作。
B樹實際上是平衡二叉樹的擴展，不同之處在於B樹具有更大的扇出數（即更多的子節點）和更低的樹高。前文討論二叉樹時節點以圓形表示，而B樹節點通常以矩形表示，當然二叉樹也可以使用矩形來表示。圖2-7使用矩形的方式表示二叉樹，2-3樹和B樹，從中我們可以看出它們之間的相似性和差異性。
圖2-7
B樹的節點也是有序排列的，因此B樹可以像二叉搜索樹一樣進行節點查找。這也就是說B樹查找節點的時間複雜度是對數的，通過32次比較就能從包含40億個節點的B樹中找到某個鍵。
對於磁盤數據結構，如果每次比較都要經過磁盤扇區定位，這樣的性能顯然是不能接受的。但是每個B樹節點存儲幾十甚至上百個條目，這就避免了每次比較都需要定位新的磁盤扇區，僅僅在進入B樹下一層的時候才需要重定位加載新扇區。後面我們會更加詳細的討論查詢算法的細節。
B樹上可以非常高效的查詢單個數據或者是查詢某個範圍內的數據。在查詢語言裡（如SQL），查詢某個數據通常表示為等於（=），而查詢某個範圍數據通常表示為比較（, ≤和≥）。
B樹的層次結構
B樹由多個節點構成，每個節點又包含N個鍵和N+1個指向子節點的指針。從邏輯上節點可以分成3類：
根節點(Root Node)： 根節點沒有父節點，位於樹的最頂部；
葉子節點(Leaf Nodes)： 樹的最底層節點，而且沒有任何子節點。
內部節點(Internal Nodes): 所有連接根節點和葉子節點的節點，通常樹包含多層內部節點。
圖2-9
由於B樹是一種磁盤頁面組織技術(即用於組織固定大小的頁面)，通常一個節點即是一個磁盤頁面，術語節點和頁面通常是同一概念。節點容量與它實際持有的鍵數之間的關係稱為佔用率。
B樹的顯著特徵是高扇出數(每個節點有較多的子節點)。高扇出數減少了為維持樹平衡而需要做的結構改動，也可以減少查詢時磁盤扇區定位的時間。B樹只有在節點空或滿的情況下才觸發平衡操作（即分裂和合並）。
分隔鍵（Separator Keys）
B樹節點上半部分存儲的鍵稱為分隔鍵。它們把樹劃分成子樹，每個子樹包含相應範圍內鍵的節點。分隔鍵以有序的方式保存在節點內，因此節點內能通過二分法進行鍵查找；找到鍵對應區間後，沿著對應的指針指向的子樹進入B樹的下一層。
B樹節點的下半部分保存了指向子樹的指針，第一個指針指向保存了所有小於第一個分隔鍵的子樹，最後一個指針指向了保存所有大於或等於最後一個分隔鍵的子樹，其它中間指針指向包含了所有大於等於其左側分隔鍵同時小於右側分隔鍵節點的子樹。 如圖2-10。
圖2-10
B樹的查複雜度
B樹查詢的複雜性需要從兩個方面考慮：磁盤頁傳輸的數量和查找時進行鍵比較的數量。
在磁盤頁傳輸數量方面，每個節點的分隔鍵劃分當前搜索空間為原來的1/N。因此在從根節點到葉子節點的遍歷過程中，需要讀取磁盤頁的數量為B樹的層數，即B樹的高度。
在鍵比較次數方面，每個節點中以二分法進行搜索，每一次比較都將當前搜索空間減半，因此複雜度為log₂M (M為節點的數目)。
B樹的查詢
為了從B樹上查詢某個鍵，我們需要從根節點到葉子節點遍歷B樹。首先在根節點保存的分隔鍵上執行二分查找，找到第一個大於查詢鍵的分隔鍵，找到該分隔鍵對應的子樹；在子樹上重複二分查詢操作，直到到達目標葉子節點。這時我們要麼找到了需要查詢的鍵，或者查詢的鍵不存在。
查詢時我們從最粗粒度的層次(樹根)開始查找，然後進入到粒度更細的下一層，其中每層分隔鍵表示更精確、更詳細的範圍。重複這個過程，直到最後到達葉節點，即數據記錄所在的位置。
單鍵查詢時，在找到查詢鍵時或確定沒有查詢鍵後搜索即告結束；而在範圍查詢時，在找到最接近範圍開始的鍵值對後繼續沿著它的兄弟節點查詢，直到到達查詢範圍的末尾。
B樹節點的拆分
當插入記錄到B樹時，首先需要找到插入目標位置，使用前一節中描述的查找算法即可找到目標位置；鍵值被附加到找到的葉子節點後面，鍵被添加到對應節點分隔鍵列表的適當位置。如果是B樹鍵值的更新，使用查找算法找到目標葉節點，並將新值與現有鍵關聯即可。
如果目標位置沒有足夠的空間存儲新鍵值，為了存儲更多鍵值我們必須要拆分該節點成兩個節點。拆分節點可能有下面兩種情況：
- 分隔葉子節點：如果葉子節點最多能夠保存N個鍵值對，新插入鍵值對前該葉子節點就已經保存有N個鍵值對；
- 分隔非葉子節點：如果節點可以保存N+1個指向子樹的指針，新插入一個子樹指針前該節點就已經保存了N+1個指針；
拆分節點時，通常我們需要創建一個新的節點，然後從被拆分節點上轉移一半的元素到新創建的節點上；添加新創建節點的第一個分隔鍵和指針都其父節點對應的位置上（通常稱這個鍵被晉級）。新創建的節點和原來的節點稱為兄弟節點。
拆分節點的父節點也有可能沒有更多的空間保存被晉級的鍵和新建節點的指針，這時其父節點也需要拆分。這樣的拆分操作有可能需要一直傳遞到根節點。當根節點也達到它的容量上限時，根節點也必須進行拆分。
這種情況下，首先會新創建一個新的根節點，其中保存了用於拆分舊根節點的鍵；其次為舊的根節點創建一個兄弟節點，以拆分鍵平分舊根節點的元素，並轉移到新創建的兄弟節點上；最後，添加舊根節點和其兄弟節點的指針到新根節點的子樹指針列表中。這個過程中，舊的根節點和新為其創建的兄弟節點一起被降級到第二層，樹的高度也增加了1。當根節點被拆分或兩個節點合併為新的根節點時，樹的高度會發生變，而在葉子和內部節點層，B樹只會水平擴展。
圖2-11展示了將一個新元素11加入到一個已經完全佔用的葉節點的過程。其中一半的元素留在老的節點，另一半元素被轉移到新創建的節點上。而拆分點的鍵（13）被作為分隔鍵保存到父節點對應的位置。
圖2-11
圖2-12展示了插入元素11前非葉子節點被完全佔用的情況。首先一個新的節點被創建, 待分割節點中從N/2+1開始的元素被移入新創建的節點；其次拆分鍵被晉級到其父節點；最後新建的節點的指針被加入到其父節點的適當位置。
圖2-12
因為非葉節點拆分總是從下往上的，所以父節點需要一個額外的指針位置(指向下一層新創建的節點)。如果父節點沒有足夠的空間，那麼它也必須被拆分。
拆分完成後，原來的一個節點變成兩個節點，我們必須選擇正確的節點來完成插入操作。如果插入的鍵小於新晉升的分隔鍵，則插入新元素到被拆分節點；否則，插入新元素到新創建的節點。
總而言之，節點拆分大致分為四步:
- 創建一個新的節點；
- 從待分割節點上轉移一半元素到新創建的節點上；
- 把新元素插入到相應的節點上；
- 把新分隔鍵和新建節點的指針加入到被拆分節點的父節點中；
B樹節點的合併
在進行刪除操作時，首先找到目標葉子節點，然後刪除鍵和與之關聯的值。刪除後，如果該葉子節點和它相鄰兄弟節點保存的鍵值對過少（低於某個閥值），這時候就需要合併節點。
準確的說，如果以下條件成立，則需要合併兩個節點:
- 合併葉子節點：如果節點能夠保存N個鍵值對，相鄰兩個兄弟節點保存的鍵值對數量之和少於或等於N。
- 合併非葉子節點： 如果節點能夠保存N+1個子樹指針，相鄰兩個兄弟節點保存的指針數量之和少於或等於N+1。
圖2-13展示了刪除元素16後，B樹合併兩個葉子節點後結構的變化。通常，我們把右邊兄弟節點的元素移入左邊節點。但是也可以把左邊的元素移入右邊節點，只要保證鍵是有序的即可。
圖2-13
圖2-14展示了刪除元素10後，B樹合併兩個相鄰非葉子節點後結構的變化。我們合併兩個節點包含的元素到一個節點中，刪除另一個多餘的節點。在合併非葉節點的過程中，我們還必須從父節點中轉移相應的分隔鍵到合併後子節點的適當位置(即分隔鍵的降級)。由於合併導致父節點的指針也減少了一個，由此有可能觸發父節點的合併操作。和節點拆分一樣，節點的合併也可能需要一直傳遞到根節點。
圖2-14
總而言之，節點合併大概也分為三步:
- 轉移所有右節點的元素到左邊節點；
- 從父節點中移除右節點的指針（如果是非葉節點則降級分隔符）；
- 移除右節點；
在B樹中，為了減少節點拆分和合並操作的數量，經常會使用一種稱為重新平衡的技術（Rebalancing），我們會在後面的文章中再具體討論這個問題。
