B-樹
B-樹概述
B-樹,這里的 B 表示 balance( 平衡的意思),B-樹是一種多路自平衡的搜索樹（B樹是一顆多路平衡查找樹）
它類似普通的平衡二叉樹，不同的一點是B-樹允許每個節(jié)點有更多的子節(jié)點。下圖是 B-樹的簡化圖.
B-樹有如下特點:
- 所有鍵值分布在整顆樹中（索引值和具體data都在每個節(jié)點里）氛改；
- 任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個結(jié)點中；
- 搜索有可能在非葉子結(jié)點結(jié)束（最好情況O(1)就能找到數(shù)據(jù)）诡渴；
- 在關(guān)鍵字全集內(nèi)做一次查找,性能逼近二分查找彰檬；
B樹深入
B樹由來
定義：B-樹是一類樹镰烧，包括B-樹瓷叫、B+樹屯吊、B*樹等，是一棵自平衡的搜索樹摹菠，它類似普通的平衡二叉樹盒卸，不同的一點是B-樹允許每個節(jié)點有更多的子節(jié)點。
B-樹是專門為外部存儲器設(shè)計的次氨，如磁盤蔽介，它對于讀取和寫入大塊數(shù)據(jù)有良好的性能，所以一般被用在文件系統(tǒng)及數(shù)據(jù)庫中煮寡。
定義只需要知道B-樹允許每個節(jié)點有更多的子節(jié)點即可（多叉樹）虹蓄。子節(jié)點數(shù)量一般在上千，具體數(shù)量依賴外部存儲器的特性幸撕。
先來看看為什么會出現(xiàn)B-樹這類數(shù)據(jù)結(jié)構(gòu)薇组。
傳統(tǒng)用來搜索的平衡二叉樹有很多，如 AVL 樹杈帐，紅黑樹等。這些樹在一般情況下查詢性能非常好专钉，但當(dāng)數(shù)據(jù)非常大的時候它們就無能為力了挑童。原因當(dāng)數(shù)據(jù)量非常大時，內(nèi)存不夠用跃须，大部分?jǐn)?shù)據(jù)只能存放在磁盤上站叼，只有需要的數(shù)據(jù)才加載到內(nèi)存中。一般而言內(nèi)存訪問的時間約為 50 ns菇民，而磁盤在 10 ms 左右尽楔。速度相差了近 5 個數(shù)量級投储，磁盤讀取時間遠遠超過了數(shù)據(jù)在內(nèi)存中比較的時間。這說明程序大部分時間會阻塞在磁盤 IO 上阔馋。那么我們?nèi)绾翁岣叱绦蛐阅苈贶瘢繙p少磁盤 IO 次數(shù)，像 AVL 樹呕寝，紅黑樹這類平衡二叉樹從設(shè)計上無法“迎合”磁盤勋眯。
上圖是一顆簡單的平衡二叉樹，平衡二叉樹是通過旋轉(zhuǎn)來保持平衡的下梢，而旋轉(zhuǎn)是對整棵樹的操作客蹋，若部分加載到內(nèi)存中則無法完成旋轉(zhuǎn)操作。其次平衡二叉樹的高度相對較大為 log n（底數(shù)為2）孽江，這樣邏輯上很近的節(jié)點實際可能非常遠讶坯，無法很好的利用磁盤預(yù)讀（局部性原理），所以這類平衡二叉樹在數(shù)據(jù)庫和文件系統(tǒng)上的選擇就被 pass 了岗屏。
空間局部性原理：如果一個存儲器的某個位置被訪問辆琅，那么將它附近的位置也會被訪問。
我們從“迎合”磁盤的角度來看看B-樹的設(shè)計担汤。
索引的效率依賴與磁盤 IO 的次數(shù)涎跨，快速索引需要有效的減少磁盤 IO 次數(shù)，如何快速索引呢崭歧？索引的原理其實是不斷的縮小查找范圍隅很，就如我們平時用字典查單詞一樣，先找首字母縮小范圍率碾，再第二個字母等等叔营。平衡二叉樹是每次將范圍分割為兩個區(qū)間。為了更快所宰，B-樹每次將范圍分割為多個區(qū)間绒尊，區(qū)間越多，定位數(shù)據(jù)越快越精確仔粥。那么如果節(jié)點為區(qū)間范圍婴谱，每個節(jié)點就較大了。所以新建節(jié)點時躯泰，直接申請頁大小的空間（磁盤存儲單位是按 block 分的谭羔，一般為 512 Byte。磁盤 IO 一次讀取若干個 block麦向，我們稱為一頁瘟裸，具體大小和操作系統(tǒng)有關(guān)，一般為 4 k诵竭，8 k或 16 k）话告，計算機內(nèi)存分配是按頁對齊的兼搏，這樣就實現(xiàn)了一個節(jié)點只需要一次 IO。
上圖是一棵簡化的B-樹沙郭，多叉的好處非常明顯佛呻，有效的降低了B-樹的高度，為底數(shù)很大的 log n棠绘，底數(shù)大小與節(jié)點的子節(jié)點數(shù)目有關(guān)件相，一般一棵B-樹的高度在 3 層左右。層數(shù)低氧苍，每個節(jié)點區(qū)確定的范圍更精確夜矗，范圍縮小的速度越快（比二叉樹深層次的搜索肯定快很多）。上面說了一個節(jié)點需要進行一次 IO让虐，那么總 IO 的次數(shù)就縮減為了 log n 次紊撕。B-樹的每個節(jié)點是 n 個有序的序列(a1,a2,a3…an)，并將該節(jié)點的子節(jié)點分割成 n+1 個區(qū)間來進行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)赡突。
點評：B樹的每個節(jié)點对扶，都是存多個值的，不像二叉樹那樣惭缰，一個節(jié)點就一個值浪南，B樹把每個節(jié)點都給了一點的范圍區(qū)間，區(qū)間更多的情況下漱受，搜索也就更快了络凿，比如：有1-100個數(shù)，二叉樹一次只能分兩個范圍昂羡，0-50和51-100絮记，而B樹，分成4個范圍 1-25虐先， 25-50怨愤，51-75，76-100一次就能篩選走四分之三的數(shù)據(jù)蛹批。所以作為多叉樹的B樹是更快的
B-樹的查找
我們來看看B-樹的查找撰洗，假設(shè)每個節(jié)點有 n 個 key值，被分割為 n+1 個區(qū)間腐芍，注意差导，每個 key 值緊跟著 data 域，這說明B-樹的 key 和 data 是聚合在一起的甸赃。一般而言柿汛，根節(jié)點都在內(nèi)存中冗酿，B-樹以每個節(jié)點為一次磁盤 IO埠对，比如上圖中络断，若搜索 key 為 25 節(jié)點的 data，首先在根節(jié)點進行二分查找（因為 keys 有序项玛，二分最快）貌笨，判斷 key 25 小于 key 50，所以定位到最左側(cè)的節(jié)點襟沮，此時進行一次磁盤 IO锥惋，將該節(jié)點從磁盤讀入內(nèi)存，接著繼續(xù)進行上述過程开伏，直到找到該 key 為止膀跌。
查找偽代碼：
Data* BTreeSearch(Root *node, Key key)
{
Data* data;
if(root == NULL)
return NULL;
data = BinarySearch(node);
if(data->key == key)
{
return data;
}else{
node = ReadDisk(data->next);
BTreeSearch(node, key);
}
}
B+ 樹
B+樹概述
B+樹是B-樹的變體，也是一種多路搜索樹, 它與 B- 樹的不同之處在于:
- 所有關(guān)鍵字存儲在葉子節(jié)點出現(xiàn),內(nèi)部節(jié)點(非葉子節(jié)點并不存儲真正的 data)
- 為所有葉子結(jié)點增加了一個鏈指針
簡化 B+樹 如下圖
因為內(nèi)節(jié)點并不存儲 data固灵，所以一般B+樹的葉節(jié)點和內(nèi)節(jié)點大小不同捅伤，而B-樹的每個節(jié)點大小一般是相同的，為一頁巫玻。
為了增加 區(qū)間訪問性丛忆，一般會對B+樹做一些優(yōu)化。
如下圖帶順序訪問的B+樹仍秤。
B-樹和B+樹的區(qū)別
1.B+樹內(nèi)節(jié)點不存儲數(shù)據(jù)熄诡，所有 data 存儲在葉節(jié)點導(dǎo)致查詢時間復(fù)雜度固定為 log n。而B-樹查詢時間復(fù)雜度不固定诗力，與 key 在樹中的位置有關(guān)凰浮，最好為O(1)励烦。
如下所示B-樹/B+樹查詢節(jié)點 key 為 50 的 data艺晴。
B-樹：
從上圖可以看出，key 為 50 的節(jié)點就在第一層悠栓，B-樹只需要一次磁盤 IO 即可完成查找圈澈。所以說B-樹的查詢最好時間復(fù)雜度是 O(1)惫周。
B+樹：
由于B+樹所有的 data 域都在根節(jié)點，所以查詢 key 為 50的節(jié)點必須從根節(jié)點索引到葉節(jié)點康栈，時間復(fù)雜度固定為 O(log n)递递。
點評：B樹的由于每個節(jié)點都有key和data，所以查詢的時候可能不需要O(logn)的復(fù)雜度啥么，甚至最好的情況是O(1)就可以找到數(shù)據(jù)登舞，而B+樹由于只有葉子節(jié)點保存了data，所以必須經(jīng)歷O(logn)復(fù)雜度才能找到數(shù)據(jù)
2. B+樹葉節(jié)點兩兩相連可大大增加區(qū)間訪問性悬荣，可使用在范圍查詢等菠秒，而B-樹每個節(jié)點 key 和 data 在一起，則無法區(qū)間查找。
根據(jù)空間局部性原理：如果一個存儲器的某個位置被訪問践叠，那么將它附近的位置也會被訪問言缤。
B+樹可以很好的利用局部性原理，若我們訪問節(jié)點 key為 50禁灼，則 key 為 55管挟、60、62 的節(jié)點將來也可能被訪問弄捕，我們可以利用磁盤預(yù)讀原理提前將這些數(shù)據(jù)讀入內(nèi)存僻孝，減少了磁盤 IO 的次數(shù)。
當(dāng)然B+樹也能夠很好的完成范圍查詢守谓。比如查詢 key 值在 50-70 之間的節(jié)點穿铆。
點評：由于B+樹的葉子節(jié)點的數(shù)據(jù)都是使用鏈表連接起來的，而且他們在磁盤里是順序存儲的斋荞，所以當(dāng)讀到某個值的時候悴务，磁盤預(yù)讀原理就會提前把這些數(shù)據(jù)都讀進內(nèi)存，使得范圍查詢和排序都很快
3.B+樹更適合外部存儲譬猫。由于內(nèi)節(jié)點無 data 域讯檐，每個節(jié)點能索引的范圍更大更精確
這個很好理解，由于B-樹節(jié)點內(nèi)部每個 key 都帶著 data 域染服，而B+樹節(jié)點只存儲 key 的副本别洪，真實的 key 和 data 域都在葉子節(jié)點存儲。前面說過磁盤是分 block 的柳刮，一次磁盤 IO 會讀取若干個 block挖垛，具體和操作系統(tǒng)有關(guān)，那么由于磁盤 IO 數(shù)據(jù)大小是固定的秉颗，在一次 IO 中痢毒，單個元素越小，量就越大蚕甥。這就意味著B+樹單次磁盤 IO 的信息量大于B-樹哪替，從這點來看B+樹相對B-樹磁盤 IO 次數(shù)少。
點評：由于B樹的節(jié)點都存了key和data菇怀，而B+樹只有葉子節(jié)點存data凭舶，非葉子節(jié)點都只是索引值，沒有實際的數(shù)據(jù)爱沟，這就時B+樹在一次IO里面帅霜，能讀出的索引值更多。從而減少查詢時候需要的IO次數(shù)呼伸！
從上圖可以看出相同大小的區(qū)域身冀，B-樹僅有 2 個 key，而B+樹有 3 個 key。
拓展：MySQL為什么使用B-Tree（B+Tree）&& 存儲知識
上文說過搂根，紅黑樹等數(shù)據(jù)結(jié)構(gòu)也可以用來實現(xiàn)索引蝶怔，但是文件系統(tǒng)及數(shù)據(jù)庫系統(tǒng)普遍采用B-/+Tree作為索引結(jié)構(gòu)，這一節(jié)將結(jié)合計算機組成原理相關(guān)知識討論B-/+Tree作為索引的理論基礎(chǔ)兄墅。
一般來說，索引本身也很大澳叉，不可能全部存儲在內(nèi)存中隙咸，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話成洗，索引查找過程中就要產(chǎn)生磁盤I/O消耗五督，相對于內(nèi)存存取，I/O存取的消耗要高幾個數(shù)量級瓶殃，所以評價一個數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過程中磁盤I/O操作次數(shù)的漸進復(fù)雜度充包。換句話說，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)遥椿。下面先介紹內(nèi)存和磁盤存取原理基矮，然后再結(jié)合這些原理分析B-/+Tree作為索引的效率。
存儲數(shù)據(jù)最小單元
我們都知道計算機在存儲數(shù)據(jù)的時候冠场，有最小存儲單元家浇，這就好比我們今天進行現(xiàn)金的流通最小單位是一毛。
在計算機中磁盤存儲數(shù)據(jù)最小單元是扇區(qū)碴裙，一個扇區(qū)的大小是512字節(jié)钢悲，而文件系統(tǒng)（例如XFS/EXT4）他的最小單元是塊，一個塊的大小是4k
而對于我們的InnoDB存儲引擎也有自己的最小儲存單元——頁（Page）舔株，一個頁的大小是16K莺琳。
下面幾張圖可以幫你理解最小存儲單元：
文件系統(tǒng)中一個文件大小只有1個字節(jié)，但不得不占磁盤上4KB的空間载慈。
磁盤扇區(qū)惭等、文件系統(tǒng)、InnoDB存儲引擎都有各自的最小存儲單元办铡。
在MySQL中我們的InnoDB頁的大小默認(rèn)是16k咕缎，當(dāng)然也可以通過參數(shù)設(shè)置：
數(shù)據(jù)表中的數(shù)據(jù)都是存儲在頁中的，所以一個頁中能存儲多少行數(shù)據(jù)呢料扰？假設(shè)一行數(shù)據(jù)的大小是1k凭豪，那么一個頁可以存放16行這樣的數(shù)據(jù)。
主存存取原理
目前計算機使用的主存基本都是隨機讀寫存儲器（RAM）晒杈，現(xiàn)代RAM的結(jié)構(gòu)和存取原理比較復(fù)雜嫂伞，這里本文拋卻具體差別，抽象出一個十分簡單的存取模型來說明RAM的工作原理。
從抽象角度看帖努，主存是一系列的存儲單元組成的矩陣撰豺，每個存儲單元存儲固定大小的數(shù)據(jù)。每個存儲單元有唯一的地址拼余，現(xiàn)代主存的編址規(guī)則比較復(fù)雜污桦，這里將其簡化成一個二維地址：通過一個行地址和一個列地址可以唯一定位到一個存儲單元。圖5展示了一個4 x 4的主存模型匙监。
主存的存取過程如下：
當(dāng)系統(tǒng)需要讀取主存時凡橱，則將地址信號放到地址總線上傳給主存，主存讀到地址信號后亭姥，解析信號并定位到指定存儲單元稼钩，然后將此存儲單元數(shù)據(jù)放到數(shù)據(jù)總線上，供其它部件讀取达罗。
寫主存的過程類似坝撑，系統(tǒng)將要寫入單元地址和數(shù)據(jù)分別放在地址總線和數(shù)據(jù)總線上，主存讀取兩個總線的內(nèi)容粮揉，做相應(yīng)的寫操作巡李。
這里可以看出，主存存取的時間僅與存取次數(shù)呈線性關(guān)系扶认，因為不存在機械操作击儡，兩次存取的數(shù)據(jù)的“距離”不會對時間有任何影響，例如蝠引，先取A0再取A1和先取A0再取D3的時間消耗是一樣的阳谍。
磁盤存取原理
上文說過，索引一般以文件形式存儲在磁盤上螃概，索引檢索需要磁盤I/O操作矫夯。與主存不同，磁盤I/O存在機械運動耗費吊洼，因此磁盤I/O的時間消耗是巨大的训貌。
圖6是磁盤的整體結(jié)構(gòu)示意圖。
一個磁盤由大小相同且同軸的圓形盤片組成冒窍，磁盤可以轉(zhuǎn)動（各個磁盤必須同步轉(zhuǎn)動）递沪。在磁盤的一側(cè)有磁頭支架，磁頭支架固定了一組磁頭综液，每個磁頭負責(zé)存取一個磁盤的內(nèi)容款慨。磁頭不能轉(zhuǎn)動，但是可以沿磁盤半徑方向運動（實際是斜切向運動）谬莹，每個磁頭同一時刻也必須是同軸的檩奠，即從正上方向下看桩了，所有磁頭任何時候都是重疊的（不過目前已經(jīng)有多磁頭獨立技術(shù)，可不受此限制）埠戳。
圖7是磁盤結(jié)構(gòu)的示意圖井誉。
盤片被劃分成一系列同心環(huán)，圓心是盤片中心整胃，每個同心環(huán)叫做一個磁道颗圣，所有半徑相同的磁道組成一個柱面。磁道被沿半徑線劃分成一個個小的段屁使，每個段叫做一個扇區(qū)在岂，每個扇區(qū)是磁盤的最小存儲單元。為了簡單起見屋灌，我們下面假設(shè)磁盤只有一個盤片和一個磁頭。
當(dāng)需要從磁盤讀取數(shù)據(jù)時应狱，系統(tǒng)會將數(shù)據(jù)邏輯地址傳給磁盤共郭，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數(shù)據(jù)在哪個磁道疾呻，哪個扇區(qū)除嘹。為了讀取這個扇區(qū)的數(shù)據(jù)，需要將磁頭放到這個扇區(qū)上方岸蜗，為了實現(xiàn)這一點尉咕，磁頭需要移動對準(zhǔn)相應(yīng)磁道，這個過程叫做尋道璃岳，所耗費時間叫做尋道時間年缎，然后磁盤旋轉(zhuǎn)將目標(biāo)扇區(qū)旋轉(zhuǎn)到磁頭下，這個過程耗費的時間叫做旋轉(zhuǎn)時間铃慷。
局部性原理與磁盤預(yù)讀
由于存儲介質(zhì)的特性单芜，磁盤本身存取就比主存慢很多，再加上機械運動耗費犁柜，磁盤的存取速度往往是主存的幾百分分之一洲鸠，因此為了提高效率，要盡量減少磁盤I/O馋缅。為了達到這個目的，磁盤往往不是嚴(yán)格按需讀取萤悴，而是每次都會預(yù)讀，即使只需要一個字節(jié)覆履，磁盤也會從這個位置開始祭务，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計算機科學(xué)中著名的局部性原理：
當(dāng)一個數(shù)據(jù)被用到時义锥，其附近的數(shù)據(jù)也通常會馬上被使用。
程序運行期間所需要的數(shù)據(jù)通常比較集中拌倍。
由于磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉(zhuǎn)時間）噪径，因此對于具有局部性的程序來說柱恤，預(yù)讀可以提高I/O效率。
預(yù)讀的長度一般為頁（page）的整倍數(shù)找爱。頁是計算機管理存儲器的邏輯塊梗顺，硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊，每個存儲塊稱為一頁（在許多操作系統(tǒng)中车摄，頁得大小通常為4k）寺谤，主存和磁盤以頁為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時吮播，會觸發(fā)一個缺頁異常变屁，此時系統(tǒng)會向磁盤發(fā)出讀盤信號，磁盤會找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁或幾頁載入內(nèi)存中意狠，然后異常返回粟关，程序繼續(xù)運行。
所以IO一次就是讀一頁的大小
參考
從 MongoDB 及 Mysql 談B/B+樹
MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理
面試官問你B樹和B+樹环戈，就把這篇文章丟給他
面試官：為什么 MySQL 索引要使用 B+樹而不是其它樹形結(jié)構(gòu)闷板？比如 B 樹？
由 B-/B+樹看 MySQL索引結(jié)構(gòu)
