B樹(shù)
動(dòng)態(tài)查找樹(shù)主要有：二叉查找樹(shù)（Binary Search Tree）顶霞，平衡二叉查找樹(shù)（Balanced Binary Search Tree），紅黑樹(shù)(Red-Black Tree )锣吼，B-tree/B+-tree/ B*-tree (B~Tree)选浑。前三者是典型的二叉查找樹(shù)結(jié)構(gòu)，其查找的時(shí)間復(fù)雜度O(log2N)與樹(shù)的深度相關(guān)玄叠，那么降低樹(shù)的深度自然會(huì)提高查找效率古徒。
但是咱們有面對(duì)這樣一個(gè)實(shí)際問(wèn)題：就是大規(guī)模數(shù)據(jù)存儲(chǔ)中，實(shí)現(xiàn)索引查詢這樣一個(gè)實(shí)際背景下读恃，樹(shù)節(jié)點(diǎn)存儲(chǔ)的元素?cái)?shù)量是有限的（如果元素?cái)?shù)量非常多的話隧膘，查找就退化成節(jié)點(diǎn)內(nèi)部的線性查找了）代态，這樣導(dǎo)致二叉查找樹(shù)結(jié)構(gòu)由于樹(shù)的深度過(guò)大而造成磁盤I/O讀寫(xiě)過(guò)于頻繁，進(jìn)而導(dǎo)致查詢效率低下疹吃，因此我們?cè)撓朕k法降低樹(shù)的深度蹦疑，從而減少磁盤查找存取的次數(shù)。一個(gè)基本的想法就是：采用多叉樹(shù)結(jié)構(gòu)（由于樹(shù)節(jié)點(diǎn)元素?cái)?shù)量是有限的萨驶，自然該節(jié)點(diǎn)的子樹(shù)數(shù)量也就是有限的）歉摧。
這樣我們就提出了一個(gè)新的查找樹(shù)結(jié)構(gòu)——平衡多路查找樹(shù)，即B-tree（B-tree樹(shù)即B樹(shù)*腔呜，B即Balanced叁温，平衡的意思**）**，這棵神奇的樹(shù)是在Rudolf Bayer, Edward M. McCreight(1970)寫(xiě)的一篇論文《Organization and Maintenance of Large Ordered Indices》中首次提出的核畴。
后面我們會(huì)看到膝但，B樹(shù)的各種操作能使B樹(shù)保持較低的高度，從而有效避免磁盤過(guò)于頻繁的查找存取操作谤草，達(dá)到有效提高查找效率的目的锰镀。然在開(kāi)始介紹Btree之前，先了解下相關(guān)的硬件知識(shí)咖刃，才能很好的了解為什么需要Btree這種外存數(shù)據(jù)結(jié)構(gòu)泳炉。
計(jì)算機(jī)存儲(chǔ)設(shè)備一般分為兩種：內(nèi)存儲(chǔ)器(main memory)和外存儲(chǔ)器(external memory)。 內(nèi)存存取速度快嚎杨，但容量小花鹅，價(jià)格昂貴，而且不能長(zhǎng)期保存數(shù)據(jù)(在不通電情況下數(shù)據(jù)會(huì)消失)枫浙。
外存儲(chǔ)器—磁盤是一種直接存取的存儲(chǔ)設(shè)備(DASD)刨肃。它是以存取時(shí)間變化不大為特征的÷嶂悖可以直接存取任何字符組真友，且容量大、速度較其它外存設(shè)備更快紧帕。
磁盤是一個(gè)扁平的圓盤(與電唱機(jī)的唱片類似)盔然。盤面上有許多稱為磁道的圓圈，數(shù)據(jù)就記錄在這些磁道上是嗜。磁盤可以是單片的愈案，也可以是由若干盤片組成的盤組，每一盤片上有兩個(gè)面鹅搪。如下圖11.3中所示的6片盤組為例站绪，除去最頂端和最底端的外側(cè)面不存儲(chǔ)數(shù)據(jù)之外，一共有10個(gè)面可以用來(lái)保存信息丽柿。
當(dāng)磁盤驅(qū)動(dòng)器執(zhí)行讀/寫(xiě)功能時(shí)恢准。盤片裝在一個(gè)主軸上魂挂，并繞主軸高速旋轉(zhuǎn)，當(dāng)磁道在讀/寫(xiě)頭(又叫磁頭) 下通過(guò)時(shí)馁筐，就可以進(jìn)行數(shù)據(jù)的讀 / 寫(xiě)了涂召。
一般磁盤分為固定頭盤(磁頭固定)和活動(dòng)頭盤。固定頭盤的每一個(gè)磁道上都有獨(dú)立的磁頭眯漩，它是固定不動(dòng)的芹扭，專門負(fù)責(zé)這一磁道上數(shù)據(jù)的讀/寫(xiě)。
活動(dòng)頭盤 (如上圖)的磁頭是可移動(dòng)的赦抖。每一個(gè)盤面上只有一個(gè)磁頭(磁頭是雙向的舱卡，因此正反盤面都能讀寫(xiě))。它可以從該面的一個(gè)磁道移動(dòng)到另一個(gè)磁道队萤。所有磁頭都裝在同一個(gè)動(dòng)臂上轮锥，因此不同盤面上的所有磁頭都是同時(shí)移動(dòng)的(行動(dòng)整齊劃一)。當(dāng)盤片繞主軸旋轉(zhuǎn)的時(shí)候要尔，磁頭與旋轉(zhuǎn)的盤片形成一個(gè)圓柱體舍杜。各個(gè)盤面上半徑相同的磁道組成了一個(gè)圓柱面，我們稱為柱面 赵辕。因此既绩，柱面的個(gè)數(shù)也就是盤面上的磁道數(shù)。
磁盤上數(shù)據(jù)必須用一個(gè)三維地址唯一標(biāo)示：柱面號(hào)还惠、盤面號(hào)饲握、塊號(hào)(磁道上的盤塊)。
讀/寫(xiě)磁盤上某一指定數(shù)據(jù)需要下面3個(gè)步驟：
首先移動(dòng)臂根據(jù)柱面號(hào)使磁頭移動(dòng)到所需要的柱面上蚕键，這一過(guò)程被稱為定位或查找 救欧。
如上圖11.3中所示的6盤組示意圖中，所有磁頭都定位到了10個(gè)盤面的10條磁道上(磁頭都是雙向的)锣光。這時(shí)根據(jù)盤面號(hào)來(lái)確定指定盤面上的磁道笆怠。
盤面確定以后，盤片開(kāi)始旋轉(zhuǎn)誊爹，將指定塊號(hào)的磁道段移動(dòng)至磁頭下蹬刷。
經(jīng)過(guò)上面三個(gè)步驟，指定數(shù)據(jù)的存儲(chǔ)位置就被找到替废。這時(shí)就可以開(kāi)始讀/寫(xiě)操作了箍铭。
訪問(wèn)某一具體信息，由3部分時(shí)間組成：
查找時(shí)間(seek time) Ts: 完成上述步驟(1)所需要的時(shí)間椎镣。這部分時(shí)間代價(jià)最高，最大可達(dá)到0.1s左右兽赁。
等待時(shí)間(latency time) Tl: 完成上述步驟(3)所需要的時(shí)間状答。由于盤片繞主軸旋轉(zhuǎn)速度很快冷守，一般為7200轉(zhuǎn)/分(電腦硬盤的性能指標(biāo)之一, 家用的普通硬盤的轉(zhuǎn)速一般有5400rpm(筆記本)、7200rpm幾種)惊科。因此一般旋轉(zhuǎn)一圈大約0.0083s拍摇。
傳輸時(shí)間(transmission time) Tt: 數(shù)據(jù)通過(guò)系統(tǒng)總線傳送到內(nèi)存的時(shí)間，一般傳輸一個(gè)字節(jié)(byte)大概0.02us=2*10^(-8)s
磁盤讀取數(shù)據(jù)是以盤塊(block)為基本單位的馆截。位于同一盤塊中的所有數(shù)據(jù)都能被一次性全部讀取出來(lái)充活。而磁盤IO代價(jià)主要花費(fèi)在查找時(shí)間Ts上。因此我們應(yīng)該盡量將相關(guān)信息存放在同一盤塊蜡娶，同一磁道中混卵。或者至少放在同一柱面或相鄰柱面上窖张，以求在讀/寫(xiě)信息時(shí)盡量減少磁頭來(lái)回移動(dòng)的次數(shù)幕随，避免過(guò)多的查找時(shí)間Ts。
所以宿接，在大規(guī)模數(shù)據(jù)存儲(chǔ)方面赘淮，大量數(shù)據(jù)存儲(chǔ)在外存磁盤中，而在外存磁盤中讀取/寫(xiě)入塊(block)中某數(shù)據(jù)時(shí)睦霎，首先需要定位到磁盤中的某塊梢卸，如何有效地查找磁盤中的數(shù)據(jù)，需要一種合理高效的外存數(shù)據(jù)結(jié)構(gòu)副女，就是下面所要重點(diǎn)闡述的B-tree結(jié)構(gòu)蛤高，以及相關(guān)的變種結(jié)構(gòu)：B+-tree結(jié)構(gòu)和B*-tree結(jié)構(gòu)。
B-樹(shù)肮塞，即為B樹(shù)襟齿。順便說(shuō)句，因?yàn)锽樹(shù)的原英文名稱為B-tree枕赵，而國(guó)內(nèi)很多人喜歡把B-tree譯作B-樹(shù)猜欺，其實(shí)，這是個(gè)非常不好的直譯拷窜，很容易讓人產(chǎn)生誤解开皿。如人們可能會(huì)以為B-樹(shù)是一種樹(shù)，而B(niǎo)樹(shù)又是另外一種樹(shù)篮昧。而事實(shí)上是赋荆，B-tree就是指的B樹(shù)。
我們知道懊昨，B 樹(shù)是為了磁盤或其它存儲(chǔ)設(shè)備而設(shè)計(jì)的一種多叉（下面你會(huì)看到窄潭，相對(duì)于二叉，B樹(shù)每個(gè)內(nèi)結(jié)點(diǎn)有多個(gè)分支酵颁，即多叉）平衡查找樹(shù)嫉你。與之前介紹的紅黑樹(shù)很相似月帝，但在降低磁盤I/0操作方面要更好一些。許多數(shù)據(jù)庫(kù)系統(tǒng)都一般使用B樹(shù)或者B樹(shù)的各種變形結(jié)構(gòu)幽污，如下文即將要介紹的B+樹(shù)嚷辅，B*樹(shù)來(lái)存儲(chǔ)信息。
B樹(shù)與紅黑樹(shù)最大的不同在于距误，B樹(shù)的結(jié)點(diǎn)可以有許多子女簸搞，從幾個(gè)到幾千個(gè)。不過(guò)B樹(shù)與紅黑樹(shù)一樣准潭，一棵含n個(gè)結(jié)點(diǎn)的B樹(shù)的高度也為O(lgn)趁俊，但可能比一棵紅黑樹(shù)的高度小許多，因?yàn)樗姆种б蜃颖容^大惋鹅。所以则酝，B樹(shù)可以在O（logn）時(shí)間內(nèi)，實(shí)現(xiàn)各種如插入（insert）闰集，刪除（delete）等動(dòng)態(tài)集合操作沽讹。
如下圖所示，即是一棵B樹(shù)武鲁，一棵關(guān)鍵字為英語(yǔ)中輔音字母的B樹(shù)爽雄，現(xiàn)在要從樹(shù)中查找字母R（包含n[x]個(gè)關(guān)鍵字的內(nèi)結(jié)點(diǎn)x，x有n[x]+1個(gè)子女（也就是說(shuō)沐鼠，一個(gè)內(nèi)結(jié)點(diǎn)x若含有n[x]個(gè)關(guān)鍵字挚瘟，那么x將含有n[x]+1個(gè)子女）。所有的葉結(jié)點(diǎn)都處于相同的深度饲梭，帶陰影的結(jié)點(diǎn)為查找字母R時(shí)要檢查的結(jié)點(diǎn)）：
相信乘盖，從上圖你能輕易的看到，一個(gè)內(nèi)結(jié)點(diǎn)x若含有n[x]個(gè)關(guān)鍵字憔涉，那么x將含有n[x]+1個(gè)子女订框。如含有2個(gè)關(guān)鍵字D H的內(nèi)結(jié)點(diǎn)有3個(gè)子女，而含有3個(gè)關(guān)鍵字Q T X的內(nèi)結(jié)點(diǎn)有4個(gè)子女兜叨。
B樹(shù)的定義
B 樹(shù)又叫平衡多路查找樹(shù)穿扳。一棵m階的B 樹(shù)(注：切勿簡(jiǎn)單的認(rèn)為一棵m階的B樹(shù)是m叉樹(shù)，雖然存在四叉樹(shù)国旷，八叉樹(shù)矛物，KD樹(shù)，及vp/R樹(shù)/R*樹(shù)/R+樹(shù)/X樹(shù)/M樹(shù)/線段樹(shù)/希爾伯特R樹(shù)/優(yōu)先R樹(shù)等空間劃分樹(shù)跪但，但與B樹(shù)完全不等同)的特性如下：
樹(shù)中每個(gè)結(jié)點(diǎn)最多含有m個(gè)孩子（m>=2）履羞；
除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有[ceil(m / 2)]個(gè)孩子（其中ceil(x)是一個(gè)取上限的函數(shù)）；
根結(jié)點(diǎn)至少有2個(gè)孩子（除非B樹(shù)只包含一個(gè)結(jié)點(diǎn)：根結(jié)點(diǎn)）吧雹；
所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層骨杂，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部結(jié)點(diǎn)或查詢失敗的結(jié)點(diǎn)涂身，指向這些結(jié)點(diǎn)的指針都為null)雄卷；（注：葉子節(jié)點(diǎn)只是沒(méi)有孩子和指向孩子的指針，這些節(jié)點(diǎn)也存在蛤售，也有元素丁鹉。類似紅黑樹(shù)中，每一個(gè)NULL指針即當(dāng)做葉子結(jié)點(diǎn)悴能，只是沒(méi)畫(huà)出來(lái)而已）揣钦。
每個(gè)非終端結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (n，P0漠酿，K1冯凹，P1，K2炒嘲，P2宇姚，......，Kn夫凸，Pn)浑劳。其中：
a) Ki (i=1...n)為關(guān)鍵字，且關(guān)鍵字按順序升序排序K(i-1)< Ki夭拌。
b) Pi為指向子樹(shù)根的結(jié)點(diǎn)魔熏，且指針P(i-1)指向子樹(shù)種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki，但都大于K(i-1)鸽扁。
c) 關(guān)鍵字的個(gè)數(shù)n必須滿足： [ceil(m / 2)-1]<= n <= m-1蒜绽。比如有j個(gè)孩子的非葉結(jié)點(diǎn)恰好有j-1個(gè)關(guān)鍵碼。
B樹(shù)中的每個(gè)結(jié)點(diǎn)根據(jù)實(shí)際情況可以包含大量的關(guān)鍵字信息和分支(當(dāng)然是不能超過(guò)磁盤塊的大小桶现，根據(jù)磁盤驅(qū)動(dòng)(disk drives)的不同躲雅，一般塊的大小在1k~4k左右)；這樣樹(shù)的深度降低了巩那，這就意味著查找一個(gè)元素只要很少結(jié)點(diǎn)從外存磁盤中讀入內(nèi)存吏夯，很快訪問(wèn)到要查找的數(shù)據(jù)。
3.2 B樹(shù)的類型和節(jié)點(diǎn)定義
B樹(shù)的類型和節(jié)點(diǎn)定義如下圖所示：
為了簡(jiǎn)單即横，這里用少量數(shù)據(jù)構(gòu)造一棵3叉樹(shù)的形式噪生，實(shí)際應(yīng)用中的B樹(shù)結(jié)點(diǎn)中關(guān)鍵字很多的。上面的圖中比如根結(jié)點(diǎn)东囚，其中17表示一個(gè)磁盤文件的文件名跺嗽；小紅方塊表示這個(gè)17文件內(nèi)容在硬盤中的存儲(chǔ)位置；p1表示指向17左子樹(shù)的指針。
其結(jié)構(gòu)可以簡(jiǎn)單定義為：
typedefstruct{/*文件數(shù)*/intfile_num;/*文件名(key)*/char* file_name[max_file_num];/*指向子節(jié)點(diǎn)的指針*/BTNode * BTptr[max_file_num+1];/*文件在硬盤中的存儲(chǔ)位置*/FILE_HARD_ADDR offset[max_file_num];}BTNode;
假如每個(gè)盤塊可以正好存放一個(gè)B樹(shù)的結(jié)點(diǎn)（正好存放2個(gè)文件名）桨嫁。那么一個(gè)BTNODE結(jié)點(diǎn)就代表一個(gè)盤塊植兰，而子樹(shù)指針就是存放另外一個(gè)盤塊的地址。
下面璃吧，咱們來(lái)模擬下查找文件29的過(guò)程：
根據(jù)根結(jié)點(diǎn)指針找到文件目錄的根磁盤塊1楣导，將其中的信息導(dǎo)入內(nèi)存⌒蟀ぃ【磁盤IO操作 1次】
此時(shí)內(nèi)存中有兩個(gè)文件名17筒繁、35和三個(gè)存儲(chǔ)其他磁盤頁(yè)面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)：17<29<35巴元，因此我們找到指針p2毡咏。
根據(jù)p2指針，我們定位到磁盤塊3逮刨，并將其中的信息導(dǎo)入內(nèi)存呕缭。【磁盤IO操作 2次】
此時(shí)內(nèi)存中有兩個(gè)文件名26修己，30和三個(gè)存儲(chǔ)其他磁盤頁(yè)面地址的數(shù)據(jù)恢总。根據(jù)算法我們發(fā)現(xiàn)：26<29<30，因此我們找到指針p2箩退。
根據(jù)p2指針离熏，我們定位到磁盤塊8，并將其中的信息導(dǎo)入內(nèi)存戴涝∽檀粒【磁盤IO操作 3次】
此時(shí)內(nèi)存中有兩個(gè)文件名28，29啥刻。根據(jù)算法我們查找到文件名29奸鸯，并定位了該文件內(nèi)存的磁盤地址。
分析上面的過(guò)程可帽，發(fā)現(xiàn)需要3次磁盤IO操作和3次內(nèi)存查找操作娄涩。關(guān)于內(nèi)存中的文件名查找，由于是一個(gè)有序表結(jié)構(gòu)映跟，可以利用折半查找提高效率蓄拣。至于IO操作是影響整個(gè)B樹(shù)查找效率的決定因素。
當(dāng)然努隙，如果我們使用平衡二叉樹(shù)的磁盤存儲(chǔ)結(jié)構(gòu)來(lái)進(jìn)行查找球恤，磁盤4次，最多5次荸镊，而且文件越多咽斧，B樹(shù)比平衡二叉樹(shù)所用的磁盤IO操作次數(shù)將越少堪置，效率也越高。
根據(jù)上面的例子我們可以看出张惹，對(duì)于輔存做IO讀的次數(shù)取決于B樹(shù)的高度舀锨。而B(niǎo)樹(shù)的高度又怎么求呢？
對(duì)于一棵含有N個(gè)關(guān)鍵字宛逗，m階的B樹(shù)來(lái)說(shuō)（據(jù)B樹(shù)的定義可知：m滿足：ceil(m/2)<=m<=m坎匿，m階即代表樹(shù)中任一結(jié)點(diǎn)最多含有m個(gè)孩子，如5階代表每個(gè)結(jié)點(diǎn)最多5個(gè)孩子拧额，或俗稱5叉樹(shù)）碑诉，且從1開(kāi)始計(jì)數(shù)的話，其高度h為：
這個(gè)B樹(shù)的高度公式從側(cè)面顯示了B樹(shù)的查找效率是相當(dāng)高的侥锦。為什么呢？因?yàn)榈讛?shù)m/2可以取很大德挣，如m可以達(dá)到幾千恭垦，從而在關(guān)鍵字?jǐn)?shù)一定的情況下，使得最終的h值盡量比較小格嗅，樹(shù)的高度比較低番挺。
樹(shù)的高度降低了，磁盤存取的次數(shù)也隨著樹(shù)高度的降低而減少，從而使得存取性能也相應(yīng)提升。
根據(jù)B樹(shù)的性質(zhì)可知，如果是一棵m階的B 樹(shù)肌稻，那么有：
樹(shù)中每個(gè)結(jié)點(diǎn)含有最多含有m個(gè)孩子，即m滿足：ceil(m/2)<=m<=m。
除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外徘意，其它每個(gè)結(jié)點(diǎn)至少有[ceil(m / 2)]個(gè)孩子（其中ceil(x)是一個(gè)取上限的函數(shù)）；
除根結(jié)點(diǎn)之外的結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)n必須滿足： [ceil(m / 2)-1]<= n <= m-1（葉子結(jié)點(diǎn)也必須滿足此條關(guān)于關(guān)鍵字?jǐn)?shù)的性質(zhì)）轩褐。
下面咱們通過(guò)另外一個(gè)實(shí)例來(lái)對(duì)這棵B樹(shù)的插入（insert）,刪除（delete）基本操作進(jìn)行詳細(xì)的介紹椎咧。以一棵5階（即樹(shù)中任一結(jié)點(diǎn)至多含有4個(gè)關(guān)鍵字，5棵子樹(shù)）B樹(shù)實(shí)例進(jìn)行講解(如下圖所示)：
在上圖所示的一棵5階B樹(shù)中把介，讀者可以看到關(guān)鍵字?jǐn)?shù)2-4個(gè)勤讽，內(nèi)結(jié)點(diǎn)孩子數(shù)3-5個(gè)。**關(guān)鍵字?jǐn)?shù)（2-4個(gè)）針對(duì)包括葉子結(jié)點(diǎn)在內(nèi)的非根結(jié)點(diǎn)拗踢，孩子數(shù)（3-5個(gè)）則針對(duì)根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外的內(nèi)結(jié)點(diǎn)脚牍。同時(shí)，根結(jié)點(diǎn)是必須至少有2個(gè)孩子的秒拔，不然就成直線型搜索樹(shù)了莫矗。**且關(guān)鍵字為大寫(xiě)字母飒硅，順序?yàn)樽帜干颉?/p>
結(jié)點(diǎn)定義如下：
typedefstruct{intCount;//當(dāng)前節(jié)點(diǎn)中關(guān)鍵元素?cái)?shù)目ItemType Key[4];//存儲(chǔ)關(guān)鍵字元素的數(shù)組longBranch[5];//偽指針數(shù)組，(記錄數(shù)目)方便判斷合并和分裂的情況} NodeType;
針對(duì)一棵高度為h的m階B樹(shù)作谚，插入一個(gè)元素時(shí)三娩，首先在B樹(shù)中是否存在，如果不存在妹懒，一般在葉子結(jié)點(diǎn)中插入該新的元素雀监，此時(shí)分3種情況：
如果葉子結(jié)點(diǎn)空間足夠，即該結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)小于m-1眨唬，則直接插入在葉子結(jié)點(diǎn)的左邊或右邊会前；
如果空間滿了以致沒(méi)有足夠的空間去添加新的元素，即該結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)已經(jīng)有了m個(gè)匾竿，則需要將該結(jié)點(diǎn)進(jìn)行“分裂”瓦宜，將一半數(shù)量的關(guān)鍵字元素分裂到新的其相鄰右結(jié)點(diǎn)中，中間關(guān)鍵字元素上移到父結(jié)點(diǎn)中岭妖，而且當(dāng)結(jié)點(diǎn)中關(guān)鍵元素向右移動(dòng)了临庇，相關(guān)的指針也需要向右移。
此外昵慌，如果在上述中間關(guān)鍵字上移到父結(jié)點(diǎn)的過(guò)程中假夺，導(dǎo)致根結(jié)點(diǎn)空間滿了，那么根結(jié)點(diǎn)也要進(jìn)行分裂操作斋攀，這樣原來(lái)的根結(jié)點(diǎn)中的中間關(guān)鍵字元素向上移動(dòng)到新的根結(jié)點(diǎn)中已卷，因此導(dǎo)致樹(shù)的高度增加一層。
下面咱們通過(guò)一個(gè)實(shí)例來(lái)逐步講解下淳蔼。插入以下字符字母到一棵空的5階B 樹(shù)中：C N G A H E K Q M F W L T Z D P R X Y S侧蘸，而且，因?yàn)槭?階B樹(shù)肖方，所以必有非根結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)小了（小于2個(gè)）就合并闺魏，大了（超過(guò)4個(gè)）就分裂。
首先俯画，結(jié)點(diǎn)空間足夠析桥，剛開(kāi)始的4個(gè)字母可以直接到插入相同的結(jié)點(diǎn)中，如下圖：
插入H結(jié)點(diǎn)時(shí)艰垂，發(fā)現(xiàn)結(jié)點(diǎn)空間不夠泡仗，所以將其分裂成2個(gè)結(jié)點(diǎn)，移動(dòng)中間元素G上移到新的根結(jié)點(diǎn)中猜憎，且把A和C留在當(dāng)前結(jié)點(diǎn)中娩怎，而H和N放置在新的右鄰居結(jié)點(diǎn)中。如下圖：
當(dāng)插入E,K,Q時(shí)胰柑，不需要任何分裂操作
插入M需要一次分裂截亦，注意到M恰好是中間關(guān)鍵字元素爬泥，所以M向上移到父節(jié)點(diǎn)中
插入F,W,L,T不需要任何分裂操作
插入Z時(shí)，最右的葉子結(jié)點(diǎn)空間滿了崩瓤，需要進(jìn)行分裂操作袍啡，中間元素T上移到父節(jié)點(diǎn)中
插入D時(shí)，導(dǎo)致最左邊的葉子結(jié)點(diǎn)被分裂却桶，D恰好也是中間元素境输，上移到父節(jié)點(diǎn)中，然后字母P,R,X,Y直接陸續(xù)插入颖系，不需要任何分裂操作
最后嗅剖，當(dāng)插入S時(shí)，含有N,P,Q,R的結(jié)點(diǎn)需要分裂嘁扼，把中間元素Q上移到父節(jié)點(diǎn)中信粮，但是問(wèn)題來(lái)了，因?yàn)镼上移導(dǎo)致父結(jié)點(diǎn) “D G M T” 也滿了偷拔，所以也要進(jìn)行分裂蒋院，將父結(jié)點(diǎn)中的中間元素M上移到新形成的根結(jié)點(diǎn)中，從而致使樹(shù)的高度增加一層莲绰。
下面介紹刪除操作姑丑，刪除操作相對(duì)于插入操作要考慮的情況多點(diǎn)蛤签。
首先查找B樹(shù)中需刪除的元素,如果該元素在B樹(shù)中存在，則將該元素在其結(jié)點(diǎn)中進(jìn)行刪除栅哀，如果刪除該元素后震肮，首先判斷該元素是否有左右孩子結(jié)點(diǎn)
如果有，則上移孩子結(jié)點(diǎn)中的某相近元素(“左孩子最右邊的節(jié)點(diǎn)”或“右孩子最左邊的節(jié)點(diǎn)”)到父節(jié)點(diǎn)中留拾，然后是移動(dòng)之后的情況戳晌；
如果沒(méi)有，直接刪除后痴柔，移動(dòng)之后的情況沦偎。
刪除元素，移動(dòng)相應(yīng)元素之后咳蔚，如果某結(jié)點(diǎn)中元素?cái)?shù)目（即關(guān)鍵字?jǐn)?shù)）小于ceil(m/2)-1豪嚎，則需要看其某相鄰兄弟結(jié)點(diǎn)是否豐滿（結(jié)點(diǎn)中元素個(gè)數(shù)大于ceil(m/2)-1）
如果豐滿，則向父節(jié)點(diǎn)借一個(gè)元素來(lái)滿足條件谈火；
如果其相鄰兄弟都剛脫貧侈询，即借了之后其結(jié)點(diǎn)數(shù)目小于ceil(m/2)-1，則該結(jié)點(diǎn)與其相鄰的某一兄弟結(jié)點(diǎn)進(jìn)行“合并”成一個(gè)結(jié)點(diǎn)糯耍，以此來(lái)滿足條件扔字。
下面咱們還是以上述插入操作構(gòu)造的一棵5階B樹(shù)（樹(shù)中除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外的任意結(jié)點(diǎn)的孩子數(shù)m滿足3<=m<=5囊嘉，除根結(jié)點(diǎn)外的任意結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)n滿足：2<=n<=4，所以關(guān)鍵字?jǐn)?shù)小于2個(gè)就合并革为，超過(guò)4個(gè)就分裂）為例扭粱，依次刪除H,T,R,E。
首先刪除元素H篷角，當(dāng)然首先查找H焊刹，H在一個(gè)葉子結(jié)點(diǎn)中，且該葉子結(jié)點(diǎn)元素?cái)?shù)目3大于最小元素?cái)?shù)目ceil(m/2)-1=2恳蹲，則操作很簡(jiǎn)單虐块，咱們只需要移動(dòng)K至原來(lái)H的位置，移動(dòng)L至K的位置（也就是結(jié)點(diǎn)中刪除元素后面的元素向前移動(dòng)）
下一步嘉蕾，刪除T,因?yàn)門沒(méi)有在葉子結(jié)點(diǎn)中贺奠，而是在中間結(jié)點(diǎn)中找到，咱們發(fā)現(xiàn)他的繼承者W(字母升序的下個(gè)元素)错忱，將W上移到T的位置儡率，然后將原包含W的孩子結(jié)點(diǎn)中的W進(jìn)行刪除，這里恰好刪除W后以清，該孩子結(jié)點(diǎn)中元素個(gè)數(shù)大于2儿普，無(wú)需進(jìn)行合并操作。
下一步刪除R掷倔，R在葉子結(jié)點(diǎn)中,但是該結(jié)點(diǎn)中元素?cái)?shù)目為2眉孩，刪除導(dǎo)致只有1個(gè)元素，已經(jīng)小于最小元素?cái)?shù)目ceil(5/2)-1=2,而由前面我們已經(jīng)知道：如果其某個(gè)相鄰兄弟結(jié)點(diǎn)中比較豐滿（元素個(gè)數(shù)大于ceil(5/2)-1=2）勒葱，則可以向父結(jié)點(diǎn)借一個(gè)元素浪汪，然后將最豐滿的相鄰兄弟結(jié)點(diǎn)中上移最后或最前一個(gè)元素到父節(jié)點(diǎn)中（有沒(méi)有看到紅黑樹(shù)中左旋操作的影子?）。 故在這個(gè)實(shí)例中凛虽，由于右相鄰兄弟結(jié)點(diǎn)“X Y Z”比較豐滿死遭，而刪除元素R后，導(dǎo)致“S”結(jié)點(diǎn)稀缺
所以原來(lái)的的“R S”結(jié)點(diǎn)先向父節(jié)點(diǎn)借一個(gè)元素W下移到該葉子結(jié)點(diǎn)中凯旋，代替原來(lái)S的位置呀潭，S前移；
然后相鄰右兄弟結(jié)點(diǎn)中的X上移到父結(jié)點(diǎn)中瓦阐；
最后相鄰右兄弟結(jié)點(diǎn)中元素Y和Z前移蜗侈。
最后一步刪除E， 刪除后會(huì)導(dǎo)致很多問(wèn)題睡蟋，因?yàn)镋所在的結(jié)點(diǎn)數(shù)目剛好達(dá)標(biāo)踏幻，剛好滿足最小元素個(gè)數(shù)（ceil(5/2)-1=2）,而相鄰的兄弟結(jié)點(diǎn)也是同樣的情況，刪除一個(gè)元素都不能滿足條件戳杀，所以需要該節(jié)點(diǎn)與某相鄰兄弟結(jié)點(diǎn)進(jìn)行合并操作该面；
首先移動(dòng)父結(jié)點(diǎn)中的元素（該元素在兩個(gè)需要合并的兩個(gè)結(jié)點(diǎn)元素之間）下移到其子結(jié)點(diǎn)中夭苗，
然后將這兩個(gè)結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)。所以在該實(shí)例中隔缀，咱們首先將父節(jié)點(diǎn)中的元素D下移到已經(jīng)刪除E而只有F的結(jié)點(diǎn)中题造，然后將含有D和F的結(jié)點(diǎn)和含有A,C的相鄰兄弟結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)。
也許你認(rèn)為這樣刪除操作已經(jīng)結(jié)束了猾瘸，其實(shí)不然界赔，在看看上圖，對(duì)于這種特殊情況牵触，你立即會(huì)發(fā)現(xiàn)父節(jié)點(diǎn)只包含一個(gè)元素G淮悼，沒(méi)達(dá)標(biāo)（因?yàn)榉歉?jié)點(diǎn)包括葉子結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)n必須滿足于2=
所以在這個(gè)實(shí)例中，咱們沒(méi)有辦法去借一個(gè)元素揽思，只能與兄弟結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)袜腥，而根結(jié)點(diǎn)中的唯一元素M下移到子結(jié)點(diǎn)，這樣钉汗，樹(shù)的高度減少一層羹令。
為了進(jìn)一步詳細(xì)討論刪除的情況，再舉另外一個(gè)實(shí)例：
這里是一棵不同的5序B樹(shù)损痰，那咱們?cè)囍鴦h除C
于是將刪除元素C的右子結(jié)點(diǎn)中的D元素上移到C的位置福侈，但是出現(xiàn)上移元素后，只有一個(gè)元素的結(jié)點(diǎn)的情況卢未。
又因?yàn)楹蠩的結(jié)點(diǎn)癌刽，其相鄰兄弟結(jié)點(diǎn)才剛脫貧（最少元素個(gè)數(shù)為2），不可能向父節(jié)點(diǎn)借元素尝丐，所以只能進(jìn)行合并操作，于是這里將含有A,B的左兄弟結(jié)點(diǎn)和含有E的結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)衡奥。
這樣又出現(xiàn)只含有一個(gè)元素F結(jié)點(diǎn)的情況爹袁，這時(shí)，其相鄰的兄弟結(jié)點(diǎn)是豐滿的（元素個(gè)數(shù)為3>最小元素個(gè)數(shù)2）矮固，這樣就可以想父結(jié)點(diǎn)借元素了失息，把父結(jié)點(diǎn)中的J下移到該結(jié)點(diǎn)中，相應(yīng)的如果結(jié)點(diǎn)中J后有元素則前移档址，然后相鄰兄弟結(jié)點(diǎn)中的第一個(gè)元素（或者最后一個(gè)元素）上移到父節(jié)點(diǎn)中盹兢，后面的元素（或者前面的元素）前移（或者后移）；注意含有K守伸，L的結(jié)點(diǎn)以前依附在M的左邊绎秒，現(xiàn)在變?yōu)橐栏皆贘的右邊。這樣每個(gè)結(jié)點(diǎn)都滿足B樹(shù)結(jié)構(gòu)性質(zhì)尼摹。
從以上操作可看出：除根結(jié)點(diǎn)之外的結(jié)點(diǎn)（包括葉子結(jié)點(diǎn)）的關(guān)鍵字的個(gè)數(shù)n滿足：（ceil(m / 2)-1）<= n <= m-1见芹，即2<=n<=4剂娄。這也佐證了咱們之前的觀點(diǎn)。刪除操作完玄呛。
B+-tree：是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B-tree的變形樹(shù)阅懦。
一棵m階的B+樹(shù)和m階的B樹(shù)的異同點(diǎn)在于：
有n棵子樹(shù)的結(jié)點(diǎn)中含有n-1 個(gè)關(guān)鍵字； (與B 樹(shù)n棵子樹(shù)有n-1個(gè)關(guān)鍵字 保持一致徘铝，參照：http://en.wikipedia.org/wiki/B%2B_tree#Overview耳胎，而下面B+樹(shù)的圖可能有問(wèn)題，請(qǐng)讀者注意)
所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息惕它，及指向含有這些關(guān)鍵字記錄的指針怕午，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。 (而B(niǎo) 樹(shù)的葉子節(jié)點(diǎn)并沒(méi)有包括全部需要查找的信息)
所有的非終端結(jié)點(diǎn)可以看成是索引部分怠缸，結(jié)點(diǎn)中僅含有其子樹(shù)根結(jié)點(diǎn)中最大（或最惺帷）關(guān)鍵字。 (而B(niǎo) 樹(shù)的非終節(jié)點(diǎn)也包含需要查找的有效信息)
a) 為什么說(shuō)B+-tree比B 樹(shù)更適合實(shí)際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫(kù)索引揭北？
B+-tree的磁盤讀寫(xiě)代價(jià)更低 B+-tree的內(nèi)部結(jié)點(diǎn)并沒(méi)有指向關(guān)鍵字具體信息的指針扳炬。因此其內(nèi)部結(jié)點(diǎn)相對(duì)B 樹(shù)更小。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中搔体，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多恨樟。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對(duì)來(lái)說(shuō)IO讀寫(xiě)次數(shù)也就降低了疚俱。
舉個(gè)例子劝术，假設(shè)磁盤中的一個(gè)盤塊容納16bytes，而一個(gè)關(guān)鍵字2bytes呆奕，一個(gè)關(guān)鍵字具體信息指針2bytes养晋。一棵9階B-tree(一個(gè)結(jié)點(diǎn)最多8個(gè)關(guān)鍵字)的內(nèi)部結(jié)點(diǎn)需要2個(gè)盤塊。而B(niǎo)+ 樹(shù)內(nèi)部結(jié)點(diǎn)只需要1個(gè)盤快梁钾。當(dāng)需要把內(nèi)部結(jié)點(diǎn)讀入內(nèi)存中的時(shí)候绳泉，B 樹(shù)就比B+ 樹(shù)多一次盤塊查找時(shí)間(在磁盤中就是盤片旋轉(zhuǎn)的時(shí)間)。
B+-tree的查詢效率更加穩(wěn)定
由于非終結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)姆泻，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引零酪。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路。所有關(guān)鍵字查詢的路徑長(zhǎng)度相同拇勃，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)四苇。
總而言之，B樹(shù)在提高了磁盤IO性能的同時(shí)并沒(méi)有解決元素遍歷的效率低下的問(wèn)題方咆。正是為了解決這個(gè)問(wèn)題月腋，B+樹(shù)應(yīng)運(yùn)而生。B+樹(shù)只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹(shù)的遍歷，支持基于范圍的查詢罗售，而B(niǎo)樹(shù)不支持range-query這樣的操作（或者說(shuō)效率太低）辜窑。
b) B+-tree的應(yīng)用: VSAM(虛擬存儲(chǔ)存取法)文件(來(lái)源論文the ubiquitous Btree作者：D COMER - 1979 )
B*-tree是B+-tree的變體，在B+樹(shù)的基礎(chǔ)上(所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息寨躁，及指向含有這些關(guān)鍵字記錄的指針)穆碎，B*樹(shù)中非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針；B*樹(shù)定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M职恳，即塊的最低使用率為2/3（代替B+樹(shù)的1/2）所禀。給出了一個(gè)簡(jiǎn)單實(shí)例，如下圖所示：
B+樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)放钦，分配一個(gè)新的結(jié)點(diǎn)色徘，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針操禀；B+樹(shù)的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)褂策，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針颓屑。
B*樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)斤寂，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中揪惦，再在原結(jié)點(diǎn)插入關(guān)鍵字遍搞，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）；如果兄弟也滿了器腋，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)溪猿，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針纫塌。
所以诊县，B*樹(shù)分配新結(jié)點(diǎn)的概率比B+樹(shù)要低，空間使用率更高措左；
通過(guò)以上介紹翎冲，大致將B樹(shù)，B+樹(shù)媳荒，B*樹(shù)總結(jié)如下：
B樹(shù)：有序數(shù)組+平衡多叉樹(shù)；
B+樹(shù)：有序數(shù)組鏈表+平衡多叉樹(shù)驹饺；
B*樹(shù)：一棵豐滿的B+樹(shù)钳枕。
順便說(shuō)一句，無(wú)論是B樹(shù)赏壹，還是B+樹(shù)鱼炒、b樹(shù)，由于根或者樹(shù)的上面幾層被反復(fù)查詢蝌借，所以這幾塊可以存在內(nèi)存中昔瞧，換言之指蚁，B樹(shù)、B+樹(shù)自晰、B樹(shù)的根結(jié)點(diǎn)和部分頂層數(shù)據(jù)在內(nèi)存中凝化，大部分下層數(shù)據(jù)在磁盤上。
