B 樹(shù)的結(jié)構(gòu)如下圖所示：
B 樹(shù)作為平衡的多路搜索樹(shù)，它的每一個(gè)節(jié)點(diǎn)最多可以包括 M 個(gè)子節(jié)點(diǎn)窝稿，M 稱為 B 樹(shù)的階凿掂。同時(shí)你能看到，每個(gè)磁盤(pán)塊中包括了關(guān)鍵字和子節(jié)點(diǎn)的指針踪少。如果一個(gè)磁盤(pán)塊中包括了 x 個(gè)關(guān)鍵字糠涛，那么指針數(shù)就是 x+1。對(duì)于一個(gè) 100 階的 B 樹(shù)來(lái)說(shuō)萝究，如果有 3 層的話最多可以存儲(chǔ)約 100 萬(wàn)的索引數(shù)據(jù)锉罐。對(duì)于大量的索引數(shù)據(jù)來(lái)說(shuō)，采用 B 樹(shù)的結(jié)構(gòu)是非常適合的栽连，因?yàn)闃?shù)的高度要遠(yuǎn)小于二叉樹(shù)的高度侨舆。
一個(gè) M 階的 B 樹(shù)（M>2）有以下的特性：
1.根節(jié)點(diǎn)的兒子數(shù)的范圍是[2,M]挨下。
2.每個(gè)中間節(jié)點(diǎn)包含 k-1 個(gè)關(guān)鍵字和 k 個(gè)孩子，孩子的數(shù)量 = 關(guān)鍵字的數(shù)量 +1臭笆，k 的取值范圍為[ceil(M/2), M]愁铺。
3.葉子節(jié)點(diǎn)包括 k-1 個(gè)關(guān)鍵字（葉子節(jié)點(diǎn)沒(méi)有孩子），k 的取值范圍為[ceil(M/2), M]茵乱。
4.假設(shè)中間節(jié)點(diǎn)節(jié)點(diǎn)的關(guān)鍵字為：Key[1], Key[2], …, Key[k-1]瓶竭，且關(guān)鍵字按照升序排序渠羞，即 Key[i]<Key[i+1]智哀。此時(shí) k-1 個(gè)關(guān)鍵字相當(dāng)于劃分了 k 個(gè)范圍，也就是對(duì)應(yīng)著 k 個(gè)指針渗蟹，即為：P[1], P[2], …, P[k]赞辩，其中 P[1]指向關(guān)鍵字小于 Key[1]的子樹(shù)，P[i]指向關(guān)鍵字屬于 (Key[i-1], Key[i]) 的子樹(shù)世落，P[k]指向關(guān)鍵字大于 Key[k-1]的子樹(shù)糟需。
5.所有葉子節(jié)點(diǎn)位于同一層。
什么是 B+ 樹(shù)
B+ 樹(shù)基于 B 樹(shù)做出了改進(jìn)武花，主流的 DBMS 都支持 B+ 樹(shù)的索引方式杈帐，比如 MySQL挑童。B+ 樹(shù)和 B 樹(shù)的差異在于以下幾點(diǎn)：
1.有 k 個(gè)孩子的節(jié)點(diǎn)就有 k 個(gè)關(guān)鍵字。也就是孩子數(shù)量 = 關(guān)鍵字?jǐn)?shù)娃兽，而 B 樹(shù)中尽楔，孩子數(shù)量 = 關(guān)鍵字?jǐn)?shù) +1。
2.非葉子節(jié)點(diǎn)的關(guān)鍵字也會(huì)同時(shí)存在在子節(jié)點(diǎn)中轻要，并且是在子節(jié)點(diǎn)中所有關(guān)鍵字的最大（或最锌衙濉）驹碍。
3.非葉子節(jié)點(diǎn)僅用于索引凡恍，不保存數(shù)據(jù)記錄嚼酝，跟記錄有關(guān)的信息都放在葉子節(jié)點(diǎn)中竟坛。而 B 樹(shù)中，非葉子節(jié)點(diǎn)既保存索引涎跨，也保存數(shù)據(jù)記錄崭歧。
4.所有關(guān)鍵字都在葉子節(jié)點(diǎn)出現(xiàn)，葉子節(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表叔营，而且葉子節(jié)點(diǎn)本身按照關(guān)鍵字的大小從小到大順序鏈接所宰。
B+ 樹(shù)和 B 樹(shù)有個(gè)根本的差異在于仔粥，B+ 樹(shù)的中間節(jié)點(diǎn)并不直接存儲(chǔ)數(shù)據(jù)。這樣的好處都有什么呢勘究？
首先斟冕，B+ 樹(shù)查詢效率更穩(wěn)定。因?yàn)?B+ 樹(shù)每次只有訪問(wèn)到葉子節(jié)點(diǎn)才能找到對(duì)應(yīng)的數(shù)據(jù)景描，而在 B 樹(shù)中秀撇，非葉子節(jié)點(diǎn)也會(huì)存儲(chǔ)數(shù)據(jù)，這樣就會(huì)造成查詢效率不穩(wěn)定的情況棠绘，有時(shí)候訪問(wèn)到了非葉子節(jié)點(diǎn)就可以找到關(guān)鍵字，而有時(shí)需要訪問(wèn)到葉子節(jié)點(diǎn)才能找到關(guān)鍵字夜矗。
其次让虐，B+ 樹(shù)的查詢效率更高，這是因?yàn)橥ǔ?B+ 樹(shù)比 B 樹(shù)更矮胖（階數(shù)更大对扶，深度更低）惭缰，查詢所需要的磁盤(pán) I/O 也會(huì)更少从媚。同樣的磁盤(pán)頁(yè)大小，B+ 樹(shù)可以存儲(chǔ)更多的節(jié)點(diǎn)關(guān)鍵字喷众。
不僅是對(duì)單個(gè)關(guān)鍵字的查詢上紧憾，在查詢范圍上，B+ 樹(shù)的效率也比 B 樹(shù)高憔四。這是因?yàn)樗嘘P(guān)鍵字都出現(xiàn)在 B+ 樹(shù)的葉子節(jié)點(diǎn)中般眉，并通過(guò)有序鏈表進(jìn)行了鏈接。而在 B 樹(shù)中則需要通過(guò)中序遍歷才能完成查詢范圍的查找柿汛，效率要低很多埠对。
