歡迎探讨，如有錯誤敬請指正
如需轉載，請注明出處 http://www.cnblogs.com/nullzx/
大多數人可能認為肯定還是B+樹快，畢竟存儲同樣多的資料，100階的B+樹肯定比平衡二叉樹的高度要低的多。但是别忘了B樹在一個結點可能需要比較很多次才能找到下一層的結點，但是平衡二叉樹隻要比較一次就可以向下走一層。是以綜合起來，其實兩者索引的速度幾乎（甚至說就是）是一樣的。最簡單的道理，一顆4階B樹就是一顆紅黑樹，比較的次數完全一樣（如果不明白這個道理，請參考我關于紅黑樹的三篇技術部落格）。那麼我們為什麼還要使用B+樹呢？這是因為上面說索引速度相當的前提是兩者的資料結構都位于記憶體中，當我們要在磁盤上索引一個記錄時，将磁盤中的資料傳輸到記憶體中才是花費時間的大頭，而在記憶體中的索引過程所花的時間基本是可以忽略不計的。在磁盤中以B+樹的形式組織資料就有着天然的優勢。要解釋這個道理，我們必須先強調一個概念，主存和磁盤之間的資料交換不是以位元組為機關的，而是以n個扇區為機關的（一個扇區有512位元組），通常是4KB（8個扇區），8KB（16個扇區），16KB，……64KB為機關的。假設，我們現在選擇4KB作為記憶體和磁盤之間的傳輸機關，那麼我們在設計B+樹的時候，不論是索引結點還是葉子結點都使用4KB作為結點的大小。我們這時不妨再假設一個記錄的大小是1KB，那麼一個葉子結點可以存4個記錄。而對于索引結點（大小也是4KB），由于隻需要存key值和相應的指針，是以一個索引結點可能可以存儲100~150個分支，我們不妨就取100吧。當然這和B樹和B+樹的插入、删除圖文詳解第2節和第3節中的情況不太一樣，因為現在索引結點的階數是100，而葉子結點的階數是4，兩者并不一緻，但這并沒有什麼問題。
我們考慮如上圖所示的B+樹，下面的B+樹有三層，兩層是索引結點，最後一層是葉子結點。那麼這個三層的B+樹最多可以存400萬個記錄。如果這個B+樹存儲到硬碟中，我們怎麼根據記錄的key找到對應的記錄呢？首先我們要讀取這個B+樹的根結點到記憶體（花費一個IO的時間）然後在記憶體中進行索引，根據key找到對應的分支，再将這個分支所指向的第二層索引結點讀取到記憶體中（花費第二個IO時間）然後在記憶體中進行索引，同樣根據key找到對應的分支，而這個分支指向的就是葉子結點，我們最後将這個葉子結點讀取到記憶體中（花費的第三個IO時間）判斷是否存在這個記錄。這樣我們隻需要通過三次IO時間就從400萬個記錄中找到了對應的key記錄，可以說是非常快了。快速的原因是，索引結點中不存資料，隻存鍵和指針，是以一個索引結點就可以存儲大量的分支，而一個索引結點隻需要一次IO即可讀取到記憶體中。
我們現在再考慮一個問題，當記錄的大小可變時，葉子結點中記錄該如何存儲？
這個時候有兩種極限情況。
1）假設葉子結點的階數仍然為4，但每個記錄僅僅有100個位元組，顯然當葉子結點中存滿4個記錄後，葉子結點中仍然有大量的剩餘空間。這個時候我們能不能直接向該葉子結點中插入資料，而不必分裂這個葉子結點（分裂指在磁盤中的分裂）？答案是可以，有人一定會說，這不就違反B+樹的定義了麼？的确違反了，但是B+樹之是以定義階數的目的是為了平衡（或者說增強）每一個分支的索引效率，不過這個優點僅當整個B+樹都位于記憶體時才能展現出來。當B+樹存儲在磁盤中的情況時，IO效率才是第一要考慮的因素。CPU在某個結點内部多比較幾次或少比較幾次和IO花費的時間相比就不值得一提了。而不分裂反而能提升B+樹的IO效率，因為分裂需要更多的IO次數。綜合起來了說就是，檔案系統及資料庫中的B+樹是不考慮階數這一個概念的，結點（即包括葉子結點，也包括索引結點）中僅遵行一個規則，如果剩餘空間夠大那麼就存入資料，如果剩餘空間不夠，隻能分裂後再存入。
2）如果某條記錄太大，即使葉子結點中還剩餘一多半的空間但仍然存不下怎麼辦？這個時候MySql稱之為行溢出，簡單的解決方式就是把記錄存儲在溢出頁（磁盤的其它空閑地方）中，然後葉子結點中存儲的是這個記錄的指針。
補充：如果按照key值的大小順序插入，按照B+樹定義的方式進行分裂時，每個葉子結點的存儲效率隻有50%，為了解決這個問題，我們可以采取這樣的分裂方式：原葉子結點中的資料不動，建立一個新的空葉子結點，記錄插入到新葉子節點中。這樣磁盤的插入效率就很高，而且每個葉子結點的使用率也很高。但這種分裂方式僅僅對按key的大小将記錄順序插入才有效，随機插入條件反而不如50%分裂的方式。
[1] B+樹介紹
[2] 從MySQL Bug#67718淺談B+樹索引的分裂優化
[3] B+樹的幾點總結