索引是資料庫常見的資料結構，每個背景開發人員都應該對索引背後的資料結構有所了解。
本文通過分析B-Tree及B-/+Tree資料結構及索引性能分析及磁盤存取原理嘗試着回答一下問題：
為什麼B-Tree适合資料庫索引及紅黑樹的二叉平衡樹不适合作為索引
B+Tree比BTree做索引的優勢
為什麼MongoDB采用B-Tree作為索引結構而MySQL采用B+Tree作為索引存儲結構
B 樹（B-Tree）是為磁盤等輔助存取裝置設計的一種平衡查找樹，它實作了以 \(O(\lg n)\) 時間複雜度執行查找、順序讀取、插入和删除操作。由于 B 樹和 B 樹的變種在降低磁盤 I/O 操作次數方面表現優異，是以經常用于設計檔案系統和資料庫。
使用階來定義 B 樹，一棵 m 階的 B 樹，需要滿足下列條件：
每個節點最多擁有m個子節點且m>=2，空樹除外
除根節點外每個節點的關鍵字數量大于等于<code>ceil(m/2)-1</code>，小于等于<code>m-1</code>，非根節點關鍵字數必須>=2
所有葉子節點均在同一層、葉子節點除了包含了關鍵字和關鍵字記錄的指針外也有指向其子節點的指針隻不過其指針位址都為null對應下圖最後一層節點的空格子
如果一個非葉節點有n個子節點，則該節點的關鍵字數等于n-1
所有節點關鍵字是按遞增次序排列，并遵循左小右大原則
注：
m階代表一個樹節點最多有多少個查找路徑，m階=m路,當m=2則是2叉樹，m=3則是3叉。
ceil()是個朝正無窮方向取整的函數，如ceil(1.1)結果為2，即向上取整。
B 樹中的節點分為内部節點（Internal Node）和葉節點（Leaf Node），内部節點也就是非葉節點（Non-Leaf Node）。
B-Tree的查找過程：根據給定值查找結點和在結點的關鍵字中進行查找交叉進行。
首先從根結點開始重複如下過程：若比結點的第一個關鍵字小，則查找在該結點第一個指針指向的結點進行；若等于結點中某個關鍵字，則查找成功；若在兩個關鍵字之間，則查找在它們之間的指針指向的結點進行；若比該結點所有關鍵字大，則查找在該結點最後一個指針指向的結點進行；若查找已經到達某個葉結點，則說明給定值對應的資料記錄不存在，查找失敗。
例如：
在一棵 5 階B-樹中查找元素 29
首先29比根節點值大，是以找根節點的右子數，然後再根據值得判斷，發現 29 介于 28 和 48 之間，然後在從中間子樹繼續查找下去。
插入的過程分兩步完成：
利用前述的B-樹的查找算法查找關鍵字的插入位置。若找到，則說明該關鍵字已經存在，直接傳回。否則查找操作必失敗于某個最低層的非終端結點上。
判斷該結點是否還有空位置。即判斷該結點的關鍵字總數是否滿足n<=m-1。若滿足，則說明該結點還有空位置，直接把關鍵字k插入到該結點的合适位置上。若不滿足，說明該結點己沒有空位置，需要把結點分裂成兩個。
分裂的方法是：
生成一新結點。把原結點上的關鍵字和k按升序排序後，從中間位置把關鍵字（不包括中間位置的關鍵字）分成兩部分。左部分所含關鍵字放在舊結點中，右部分所含關鍵字放在新結點中，中間位置的關鍵字連同新結點的存儲位置插入到父結點中。如果父結點的關鍵字個數也超過（m-1），則要再分裂，再往上插。直至這個過程傳到根結點為止。
例子：
如果該節點的元素個數還沒達到 m，則插入完後無需處理
比如：
如果該節點元素個數達到 m 時，這時候将元素插入到合适的位置，将最中間的元素取出，成為該節點的父節點元素，然後将其餘左右元素拆成兩個新節點
剛才的操作可能導緻父節點的元素個數達到 m，這時候用情況 2 疊代處理，直到如果遇到根結點元素個數達到 m，則最中間元素将成為新的根結點。
我們需要分兩種情況進行讨論：
如果該元素存在于葉子結點，直接删除它，無需進行其它處理。
如果該元素存在于非葉子節點，那麼删除它将會留下一個空位，這時候我們需要一些處理來填充該位置。
因為節點的元素個數在 [M/2, M] 的範圍内，是以比如這裡我們以 5 階B-樹為例，判斷節點元素是否充足即滿足個數則至少擁有三（2 + 1）個元素的節點才算是有充足的元素。
如果被删元素的左子樹擁有足夠的元素，這時候我們隻需拿左子節點的最大值元素上來填充即可
當左子樹不夠元素而右子樹元素充足時，這時候我們拿右子樹的最小值元素上來進行填充
當左右子樹所含元素均不足時，但左子樹的左邊兄弟節點的元素個數充足，這時我們需要拿左邊的兄弟節點來進行調整。
當左右子樹所含元素均不足時，但左子樹的左邊兄弟節點的元素個數也不足時，這時候我們還是拿左子樹的最大值元素進行填充，之後再将該節點與其他節點合并形成新的節點。
B-Tree有許多變種，其中最常見的是B+Tree，例如MySQL就普遍使用B+Tree實作其索引結構。
與B-Tree相比，B+Tree有以下不同點：
每個節點的指針上限為2d而不是2d+1。
B+Tree葉子節點儲存了父節點的所有關鍵字和關鍵字記錄的指針，每個葉子節點的關鍵字從小到大連結
内節點不存儲data，隻存儲key；葉子節點不存儲指針。是以所有資料位址必須要到葉子節點才能擷取到，是以每次資料查詢的次數都一樣。
紅黑樹等資料結構也可以用來實作索引，但是檔案系統及資料庫系統普遍采用B-/+Tree作為索引結構，這一節将結合計算機組成原理相關知識讨論B-/+Tree作為索引的理論基礎。
一般來說，索引本身也很大，不可能全部存儲在記憶體中，是以索引往往以索引檔案的形式存儲的磁盤上。這樣的話，索引查找過程中就要産生磁盤I/O消耗，相對于記憶體存取，I/O存取的消耗要高幾個數量級，是以評價一個資料結構作為索引的優劣最重要的名額就是在查找過程中磁盤I/O操作次數的漸進複雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。
下面先介紹記憶體和磁盤存取原理，然後再結合這些原理分析B-/+Tree作為索引的效率。
索引一般以檔案形式存儲在磁盤上，索引檢索需要磁盤I/O操作。與主存不同，磁盤I/O存在機械運動耗費，是以磁盤I/O的時間消耗是巨大的。
下面是磁盤的整體結構示意圖：
一個磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉動（各個磁盤必須同步轉動）。在磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的内容。磁頭不能轉動，但是可以沿磁盤半徑方向運動（實際是斜切向運動），每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的（不過目前已經有多磁頭獨立技術，可不受此限制）。
下面是磁盤結構的示意圖：
盤片被劃分成一系列同心環，圓心是盤片中心，每個同心環叫做一個磁道，所有半徑相同的磁道組成一個柱面。磁道被沿半徑線劃分成一個個小的段，每個段叫做一個扇區，每個扇區是磁盤的最小存儲單元。為了簡單起見，我們下面假設磁盤隻有一個盤片和一個磁頭。
當需要從磁盤讀取資料時，系統會将資料邏輯位址傳給磁盤，磁盤的控制電路按照尋址邏輯将邏輯位址翻譯成實體位址，即确定要讀的資料在哪個磁道，哪個扇區。為了讀取這個扇區的資料，需要将磁頭放到這個扇區上方，為了實作這一點，磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間，然後磁盤旋轉将目标扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。
由于存儲媒體的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，是以為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使隻需要一個位元組，磁盤也會從這個位置開始，順序向後讀取一定長度的資料放入記憶體。
這樣做的理論依據是計算機科學中著名的局部性原理：
當一個資料被用到時，其附近的資料也通常會馬上被使用。
程式運作期間所需要的資料通常比較集中。
由于磁盤順序讀取的效率很高（不需要尋道時間，隻需很少的旋轉時間），是以對于具有局部性的程式來說，預讀可以提高I/O效率。
預讀的長度一般為頁（page）的整倍數。頁是計算機管理存儲器的邏輯塊，硬體及作業系統往往将主存和磁盤存儲區分割為連續的大小相等的塊，每個存儲塊稱為一頁（在許多作業系統中，頁得大小通常為4k），主存和磁盤以頁為機關交換資料。當程式要讀取的資料不在主存中時，會觸發一個缺頁異常，此時系統會向磁盤發出讀盤信号，磁盤會找到資料的起始位置并向後連續讀取一頁或幾頁載入記憶體中，然後異常傳回，程式繼續運作。
一般使用磁盤I/O次數評價索引結構的優劣。先從B-Tree分析，根據B-Tree的定義，可知檢索一次最多需要通路h個節點。資料庫系統的設計者巧妙利用了磁盤預讀原理，将一個節點的大小設為等于一個頁，這樣每個節點隻需要一次I/O就可以完全載入。為了達到這個目的，在實際實作B-Tree還需要使用如下技巧：
每次建立節點時，直接申請一個頁的空間，這樣就保證一個節點實體上也存儲在一個頁裡，加之計算機存儲配置設定都是按頁對齊的，就實作了一個node隻需一次I/O。
B-Tree中一次檢索最多需要h-1次I/O（根節點常駐記憶體），漸進複雜度為\(O(h)=O(\log_d N)\)。一般實際應用中，出度d是非常大的數字，通常超過100，是以h非常小（通常不超過3）。
綜上所述，用B-Tree作為索引結構效率是非常高的。
而紅黑樹這種結構，h明顯要深的多。由于邏輯上很近的節點（父子）實體上可能很遠，無法利用局部性，是以紅黑樹的I/O漸進複雜度也為O(h)，效率明顯比B-Tree差很多。
上文還說過，B+Tree更适合外存索引，原因和内節點出度d有關。從上面分析可以看到，d越大索引的性能越好，而出度的上限取決于節點内key和data的大小：
\[d_{max}=floor({pagesize \over keysize+datasize+pointsize})
\]
floor表示向下取整。
由于B+Tree内節點去掉了data域，是以可以擁有更大的出度，容納更多的節點，能夠有效減少磁盤IO次數。
一般在資料庫系統或檔案系統中使用的B+Tree結構都在經典B+Tree的基礎上進行了優化，增加了順序通路指針。
如上圖圖所示，在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序通路指針的B+Tree。做這個優化的目的是為了提高區間通路的性能，例如圖4中如果要查詢key為從18到49的所有資料記錄，當找到18後，隻需順着節點和指針順序周遊就可以一次性通路到所有資料節點，極大提到了區間查詢效率。
綜上所述：
B+Tree做索引的優勢是：
内部節點取消data域，每一頁可以容納更多的資料，有效減少磁盤IO次數。
資料都存儲在葉子節點，是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。是以B+樹查詢時間複雜度為log n，而B樹查詢時間複雜度不固定，與所查結點在樹中的位置有關，最好為O(1)。
通過增加順序通路指針提高區間查詢效率。
而MongoDB索引選擇B樹可能是因為：
MongoDB 是文檔型的資料庫，是一種nosql，它使用BSON格式儲存資料，歸屬于聚合型資料庫。被設計用在資料模型簡單，性能要求高的場合。之是以采用B樹，是因為B樹key和data域聚合在一起。
參考文檔：
MySQL索引背後的資料結構及算法原理
人人都是 DBA（VII）B 樹和 B+ 樹
平衡二叉樹、B-Tree、B+Tree、B*樹 了解其中一種你就都明白了
https://zh.wikipedia.org/wiki/B樹
B-Tree gif：https://www.cs.usfca.edu/~galles/visualization/BTree.html
6. 資料結構 - B 樹