一、引言
1970年抛寝，R.Bayer和E.mccreight提出了一種適用于外查找的樹(shù)，它是一種平衡的多叉樹(shù)曙旭，稱為B樹(shù)（或B-樹(shù)盗舰、B_樹(shù)）。我們都知道二叉查找樹(shù)的查找的時(shí)間復(fù)雜度是Ｏ(log N)夷狰，其查找效率已經(jīng)足夠高了岭皂，那為什么還有Ｂ樹(shù)和Ｂ＋樹(shù)的出現(xiàn)呢？難道它兩的時(shí)間復(fù)雜度比二叉查找樹(shù)還小嗎沼头？
答案當(dāng)然不是爷绘，Ｂ樹(shù)和Ｂ＋樹(shù)的出現(xiàn)是因?yàn)榱硗庖粋€(gè)問(wèn)題，那就是磁盤ＩＯ进倍；眾所周知土至，ＩＯ操作的效率很低，那么猾昆，當(dāng)在大量數(shù)據(jù)存儲(chǔ)中陶因，查詢時(shí)我們不能一下子將所有數(shù)據(jù)加載到內(nèi)存中，只能逐一加載磁盤頁(yè)垂蜗，每個(gè)磁盤頁(yè)對(duì)應(yīng)樹(shù)的節(jié)點(diǎn)楷扬。造成大量磁盤ＩＯ操作（最壞情況下為樹(shù)的高度）。平衡二叉樹(shù)由于樹(shù)深度過(guò)大而造成磁盤IO讀寫(xiě)過(guò)于頻繁贴见，進(jìn)而導(dǎo)致效率低下烘苹。
所以，我們?yōu)榱藴p少磁盤ＩＯ的次數(shù)片部，就你必須降低樹(shù)的深度镣衡，將“瘦高”的樹(shù)變得“矮胖”。一個(gè)基本的想法就是：
（1）廊鸥、每個(gè)節(jié)點(diǎn)存儲(chǔ)多個(gè)元素
⊥啤（2）、摒棄二叉樹(shù)結(jié)構(gòu)惰说，采用多叉樹(shù)
這樣就引出來(lái)了一個(gè)新的查找樹(shù)結(jié)構(gòu) ——多路查找樹(shù)磨德。 根據(jù)AVL給我們的啟發(fā)，一顆平衡多路查找樹(shù)(B~樹(shù))自然可以使得數(shù)據(jù)的查找效率保證在O(logN)這樣的對(duì)數(shù)級(jí)別上吆视。
【注意】：B-樹(shù)剖张，即為B樹(shù)。因?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ù)。
二郁妈、基本概念
1浑玛、B樹(shù)：B 樹(shù)是為了磁盤或其它存儲(chǔ)設(shè)備而設(shè)計(jì)的一種多叉（下面你會(huì)看到，相對(duì)于二叉噩咪，B樹(shù)每個(gè)內(nèi)結(jié)點(diǎn)有多個(gè)分支顾彰，即多叉）平衡查找樹(shù)。與本blog之前介紹的紅黑樹(shù)很相似胃碾，但在降低磁盤I/0操作方面要更好一些涨享。許多數(shù)據(jù)庫(kù)系統(tǒng)都一般使用B樹(shù)或者B樹(shù)的各種變形結(jié)構(gòu)。
2仆百、對(duì)比紅黑樹(shù)： B樹(shù)與紅黑樹(shù)最大的不同在于厕隧，B樹(shù)的結(jié)點(diǎn)可以有許多子女，從幾個(gè)到幾千個(gè)俄周。那為什么又說(shuō)B樹(shù)與紅黑樹(shù)很相似呢?因?yàn)榕c紅黑樹(shù)一樣吁讨，一棵含n個(gè)結(jié)點(diǎn)的B樹(shù)的高度也為O（lgn），但可能比一棵紅黑樹(shù)的高度小許多峦朗，應(yīng)為它的分支因子比較大建丧。所以，B樹(shù)可以在O（logn）時(shí)間內(nèi)甚垦，實(shí)現(xiàn)各種如插入（insert）茶鹃，刪除（delete）等動(dòng)態(tài)集合操作
三、性質(zhì)
1艰亮、性質(zhì)：B 樹(shù)又叫平衡多路查找樹(shù)闭翩。一棵m階的B 樹(shù) (m叉樹(shù))的特性如下：（ceil代表向上取整）
（1）根結(jié)點(diǎn)至少有2顆子樹(shù)（除非B樹(shù)只包含一個(gè)結(jié)點(diǎn)）；
（2）每個(gè)中間結(jié)點(diǎn)都包含k-1個(gè)元素（關(guān)鍵字）和k個(gè)子樹(shù)迄埃，其中 ceil(m/2) ≤ k ≤ m疗韵；
（3）每一個(gè)葉子結(jié)點(diǎn)都包含k-1個(gè)元素（關(guān)鍵字），其中 ceil（m/2）-1 ≤ k-1 ≤ m-1侄非；
（4）所有葉結(jié)點(diǎn)在同一層上蕉汪，B樹(shù)的葉結(jié)點(diǎn)可以看成一種外部結(jié)點(diǎn)，不包含任何信息逞怨；
（5）每個(gè)結(jié)點(diǎn)中的元素（關(guān)鍵字）從小到大排列者疤，結(jié)點(diǎn)當(dāng)中k-1個(gè)元素（關(guān)鍵字）正好是k個(gè)孩子包含的元素（關(guān)鍵字）的值域劃分；
（6）每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：
其中叠赦，Ki(1≤i≤n)為關(guān)鍵字驹马，且Ki<Ki+1(1≤i≤n-1)，Ai(0≤i≤n)為指向子樹(shù)根結(jié)點(diǎn)的指針除秀。且Ai所指子樹(shù)所有結(jié)點(diǎn)中的關(guān)鍵字均小于Ki+1糯累，n為結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，滿足ceil(m/2)-1≤n≤m-1册踩。
2泳姐、實(shí)例：下面我們通過(guò)一個(gè)實(shí)例進(jìn)行講解：
1）結(jié)點(diǎn)的分支數(shù)等于關(guān)鍵字?jǐn)?shù)+1，最大的分支數(shù)就是B-樹(shù)的階數(shù)暂吉，因此m階的B-樹(shù)中結(jié)點(diǎn)最多有m個(gè)分支胖秒，所以可以看到，上面的一棵樹(shù)是一個(gè)3-階B-樹(shù)慕的。??
2）因?yàn)樯厦媸且豢?階B-樹(shù)扒怖，所以非根非葉結(jié)點(diǎn)至少要有ceil(3/2)=2個(gè)分支。根結(jié)點(diǎn)可以不滿足這個(gè)條件业稼，圖中的根結(jié)點(diǎn)有兩個(gè)分支盗痒。? ? ? ? ? ??
3）如果根結(jié)點(diǎn)中沒(méi)有關(guān)鍵字就沒(méi)有分支，此時(shí)B-樹(shù)是空樹(shù)低散，如果根結(jié)點(diǎn)有關(guān)鍵字俯邓，則其分支數(shù)比大于或等于2，因?yàn)榉种?shù)等于關(guān)鍵字?jǐn)?shù)+1.? ?
4）上圖中除根結(jié)點(diǎn)外熔号，結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)至少為1稽鞭，因?yàn)榉种?shù)至少為2，分支數(shù)比關(guān)鍵字?jǐn)?shù)多1引镊，還可以看出結(jié)點(diǎn)內(nèi)關(guān)鍵字都是有序的朦蕴，并且在同一層中篮条，左邊結(jié)點(diǎn)內(nèi)所有關(guān)鍵字均小于右邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字，例如吩抓，第二層上的兩個(gè)結(jié)點(diǎn)涉茧，左邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字為12，23,30疹娶，他們均小于右邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字46伴栓。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?B-樹(shù)一個(gè)很重要的特征是，下層結(jié)點(diǎn)內(nèi)的關(guān)鍵字取值總是落在由上層結(jié)點(diǎn)關(guān)鍵字所劃分的區(qū)間內(nèi)雨饺，具體落在哪個(gè)區(qū)間內(nèi)可以由指向它的指針看出钳垮。例如，第二層左邊數(shù)第二個(gè)的結(jié)點(diǎn)內(nèi)的關(guān)鍵字劃分了三個(gè)區(qū)間额港，小于23饺窿，23到30，大于30移斩，可以看出其下層中最左邊結(jié)點(diǎn)內(nèi)的關(guān)鍵字都小于23短荐，中間結(jié)點(diǎn)的關(guān)鍵字在23和30之間，右邊結(jié)點(diǎn)的關(guān)鍵字大于30.
5）上圖中葉子結(jié)點(diǎn)都在第四層上叹哭，代表查找不成功的位置忍宋。
四、B樹(shù)的操作
B樹(shù)可視化的網(wǎng)站：[B-Trees]：(https://www.cs.usfca.edu/~galles/visualization/BTree.html)风罩，假定對(duì)高度為h的m階B樹(shù)進(jìn)行操作糠排。
1、查詢：
以上圖為例：若查詢的數(shù)值為５：
第一次磁盤ＩＯ：在內(nèi)存中定位（與17超升、35比較）入宦，比17小，左子樹(shù)室琢；
第二次磁盤ＩＯ：在內(nèi)存中定位（與８乾闰、12比較），比８小盈滴，左子樹(shù)涯肩；
第三次磁盤ＩＯ：在內(nèi)存中定位（與3、5比較）巢钓，找到5病苗，終止。
整個(gè)過(guò)程中症汹，我們可以看出：比較的次數(shù)并不比二叉查找樹(shù)少硫朦，尤其適當(dāng)某一節(jié)點(diǎn)中的數(shù)據(jù)很多時(shí)，但是磁盤IO的次數(shù)卻是大大減少背镇。比較是在內(nèi)存中進(jìn)行的咬展，相比于磁盤IO的速度泽裳，比較的耗時(shí)幾乎可以忽略。所以當(dāng)樹(shù)的高度足夠低的話破婆，就可以極大的提高效率涮总。相比之下，節(jié)點(diǎn)中的元素多點(diǎn)也沒(méi)關(guān)系荠割，僅僅是多了幾次內(nèi)存交互而已，只要不超過(guò)磁盤頁(yè)的大小即可旺矾。
2蔑鹦、插入：
對(duì)高度為ｋ的m階B樹(shù)，新結(jié)點(diǎn)一般是插在葉子層箕宙。通過(guò)檢索可以確定關(guān)鍵碼應(yīng)插入的結(jié)點(diǎn)位置嚎朽。然后分兩種情況討論：
1、 若該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)小于m-1柬帕，則直接插入即可哟忍。
2、 若該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)等于m-1陷寝，則將引起結(jié)點(diǎn)的分裂锅很。以中間關(guān)鍵碼為界將結(jié)點(diǎn)一分為二，產(chǎn)生一個(gè)新結(jié)點(diǎn)凤跑，并把中間關(guān)鍵碼插入到父結(jié)點(diǎn)(ｋ-1層)中
重復(fù)上述工作爆安，最壞情況一直分裂到根結(jié)點(diǎn)，建立一個(gè)新的根結(jié)點(diǎn)仔引，整個(gè)B樹(shù)增加一層扔仓。
例1：在下面的B樹(shù)中插入key：4
第一步：檢索key插入的節(jié)點(diǎn)位置如上圖所示，在3,5之間咖耘；
第二步：判斷節(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)：
節(jié)點(diǎn)3翘簇，5已經(jīng)是兩元素節(jié)點(diǎn)，無(wú)法再增加儿倒。父親節(jié)點(diǎn) 2版保， 6 也是兩元素節(jié)點(diǎn)，也無(wú)法再增加夫否。根節(jié)點(diǎn)9是單元素節(jié)點(diǎn)找筝，可以升級(jí)為兩元素節(jié)點(diǎn)。慷吊；
第三步：結(jié)點(diǎn)分裂：
拆分節(jié)點(diǎn)3袖裕，5與節(jié)點(diǎn)2，6溉瓶，讓根節(jié)點(diǎn)9升級(jí)為兩元素節(jié)點(diǎn)4急鳄，9谤民。節(jié)點(diǎn)6獨(dú)立為根節(jié)點(diǎn)的第二個(gè)孩子。
最終結(jié)果如下圖：雖然插入比較麻煩疾宏，但是這也能確保Ｂ樹(shù)是一個(gè)自平衡的樹(shù)张足。
例2：我們以關(guān)鍵字序列{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}創(chuàng)建一棵5階B-樹(shù)，我們將詳細(xì)體會(huì)B-樹(shù)的插入過(guò)程坎藐。
（1）確定結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)范圍
由于題目要求建立5階B-樹(shù)为牍，因此關(guān)鍵字的個(gè)數(shù)范圍為2～4
（2）根結(jié)點(diǎn)最多可以容納4個(gè)關(guān)鍵字，依次插入關(guān)鍵字1岩馍、2碉咆、6、7后的B-樹(shù)如下圖所示：
（3）當(dāng)插入關(guān)鍵字11的時(shí)候蛀恩，發(fā)現(xiàn)此時(shí)結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)變?yōu)?疫铜，超出范圍，需要拆分双谆，去關(guān)鍵字?jǐn)?shù)組中的中間位置壳咕，也就是k[3]=6，作為一個(gè)獨(dú)立的結(jié)點(diǎn)顽馋，即新的根結(jié)點(diǎn)谓厘，將關(guān)鍵字6左、右關(guān)鍵字分別做成兩個(gè)結(jié)點(diǎn)寸谜，作為新根結(jié)點(diǎn)的兩個(gè)分支庞呕，此時(shí)樹(shù)如下圖所示：
（4）新關(guān)鍵字總是插在葉子結(jié)點(diǎn)上，插入關(guān)鍵字4程帕、8住练、13之后樹(shù)為：
（5）關(guān)鍵字10需要插入在關(guān)鍵字8和11之間铃在，此時(shí)又會(huì)出現(xiàn)關(guān)鍵字個(gè)數(shù)超出范圍的情況劣挫，因此需要拆分。拆分時(shí)需要將關(guān)鍵字10納入根結(jié)點(diǎn)中店诗，并將10左右的關(guān)鍵字做成兩個(gè)新的結(jié)點(diǎn)連在根結(jié)點(diǎn)上岭埠。插入關(guān)鍵字10并經(jīng)過(guò)拆分操作后的B-樹(shù)如下圖：
（6）插入關(guān)鍵字5盏混、17、9惜论、16之后的B-樹(shù)如圖所示：
（7）關(guān)鍵字20插入在關(guān)鍵字17以后许赃，此時(shí)會(huì)造成結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)超出范圍，需要拆分馆类，方法同上混聊，樹(shù)為：
（8）按照上述步驟依次插入關(guān)鍵字3、12乾巧、14句喜、18预愤、19之后B-樹(shù)如下圖所示：
（9）插入最后一個(gè)關(guān)鍵字15，15應(yīng)該插入在14之后咳胃，此時(shí)會(huì)出現(xiàn)關(guān)鍵字個(gè)數(shù)超出范圍的情況植康，則需要進(jìn)行拆分，將13并入根結(jié)點(diǎn)展懈，13并入根結(jié)點(diǎn)之后销睁，又使得根結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)超出范圍，需要再次進(jìn)行拆分存崖，將10作為新的根結(jié)點(diǎn)冻记，并將10左、右關(guān)鍵字做成兩個(gè)新結(jié)點(diǎn)連接到新根結(jié)點(diǎn)的指針上金句，這種插入一個(gè)關(guān)鍵字之后出現(xiàn)多次拆分的情況稱為連鎖反應(yīng)檩赢，最終形成的B-樹(shù)如下圖所示：
3吕嘀、刪除：
對(duì)于B-樹(shù)關(guān)鍵字的刪除违寞，需要找到待刪除的關(guān)鍵字，在結(jié)點(diǎn)中刪除關(guān)鍵字的過(guò)程也有可能破壞B-樹(shù)的特性偶房，如舊關(guān)鍵字的刪除可能使得結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)少于規(guī)定個(gè)數(shù)趁曼，這是可能需要向其兄弟結(jié)點(diǎn)借關(guān)鍵字或者和其孩子結(jié)點(diǎn)進(jìn)行關(guān)鍵字的交換，也可能需要進(jìn)行結(jié)點(diǎn)的合并棕洋，其中挡闰，和當(dāng)前結(jié)點(diǎn)的孩子進(jìn)行關(guān)鍵字交換的操作可以保證刪除操作總是發(fā)生在終端結(jié)點(diǎn)上。
例1：下面舉一個(gè)簡(jiǎn)單的例子：刪除元素11.
第一步：判斷該元素是否在葉子結(jié)點(diǎn)上掰盘。
該元素在葉子節(jié)點(diǎn)上摄悯，可以直接刪去，但是刪除之后愧捕，中間節(jié)點(diǎn)12只有一個(gè)孩子奢驯，不符合B樹(shù)的定義：每個(gè)中間節(jié)點(diǎn)都包含k個(gè)孩子，（其中 ceil（m/2） <= k <= m）所以需要調(diào)整次绘；
第二步：判斷其左右兄弟結(jié)點(diǎn)中有“多余”的關(guān)鍵字瘪阁，即：原關(guān)鍵字個(gè)數(shù)n>=ceil(m/2) - 1；
顯然結(jié)點(diǎn)11的右兄弟節(jié)點(diǎn)中有多余的關(guān)鍵字邮偎。那么可將右兄弟結(jié)點(diǎn)中最小關(guān)鍵字上移至雙親結(jié)點(diǎn)管跺。而將雙親結(jié)點(diǎn)中小于該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點(diǎn)中即可。
例2：我們用剛剛生成的B-樹(shù)作為例子禾进，一次刪除8豁跑、16、15泻云、4這4個(gè)關(guān)鍵字贩绕。
（1）刪除關(guān)鍵字8火的、16。關(guān)鍵字8在終端結(jié)點(diǎn)上淑倾，并且刪除后其所在結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不會(huì)少于2馏鹤，因此可以直接刪除。關(guān)鍵字16不在終端結(jié)點(diǎn)上娇哆，但是可以用17來(lái)覆蓋16湃累，然后將原來(lái)的17刪除掉，這就是上面提到的和孩子結(jié)點(diǎn)進(jìn)行關(guān)鍵字交換的操作碍讨。這里不能用15和16進(jìn)行關(guān)鍵字交換治力，因?yàn)檫@樣會(huì)導(dǎo)致15所在結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)小于2。因此勃黍，刪除8和16之后B-樹(shù)如下圖所示：
（2）刪除關(guān)鍵字15宵统，15雖然也在終端結(jié)點(diǎn)上，但是不能直接刪除覆获，因?yàn)閯h除后當(dāng)前結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)小于2马澈。這是需要向其兄弟結(jié)點(diǎn)借關(guān)鍵字，顯然應(yīng)該向其右兄弟來(lái)借關(guān)鍵字弄息，因?yàn)樽笮值艿年P(guān)鍵字個(gè)數(shù)已經(jīng)是下限2.借關(guān)鍵字不能直接將18移到15所在的結(jié)點(diǎn)上痊班，因?yàn)檫@樣會(huì)使得15所在的結(jié)點(diǎn)上出現(xiàn)比17大的關(guān)鍵字，所以正確的借法應(yīng)該是先用17覆蓋15摹量，在用18覆蓋原來(lái)的17涤伐，最后刪除原來(lái)的18，刪除關(guān)鍵字15后的B-樹(shù)如下圖所示：
（3）刪除關(guān)鍵字4缨称，4在終端結(jié)點(diǎn)上凝果，但是此時(shí)4所在的結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)已經(jīng)到下限，需要借關(guān)鍵字睦尽，不過(guò)可以看到其左右兄弟結(jié)點(diǎn)已經(jīng)沒(méi)有多余的關(guān)鍵字可借器净。所以就需要進(jìn)行關(guān)鍵字的合并÷钌荆可以先將關(guān)鍵字4刪除掌动，然后將關(guān)鍵字5、6宁玫、7粗恢、9進(jìn)行合并作為一個(gè)結(jié)點(diǎn)鏈接在關(guān)鍵字3右邊的指針上，也可以將關(guān)鍵字1欧瘪、2眷射、3、5合并作為一個(gè)結(jié)點(diǎn)鏈接在關(guān)鍵字6左邊的指針上，如下圖所示：
顯然上述兩種情況下都不滿足B-樹(shù)的規(guī)定妖碉，即出現(xiàn)了非根的雙分支結(jié)點(diǎn)涌庭，需要繼續(xù)進(jìn)行合并，合并后的B-樹(shù)如下圖所示：
有時(shí)候刪除的結(jié)點(diǎn)不在終端結(jié)點(diǎn)上欧宜，我們首先需要將其轉(zhuǎn)化到終端結(jié)點(diǎn)上坐榆，然后再按上面的各種情況進(jìn)行刪除。在講述這種情況下的刪除方法之前冗茸，要引入一個(gè)相鄰關(guān)鍵字的概念席镀，對(duì)于不在終端結(jié)點(diǎn)的關(guān)鍵字a，它的相鄰關(guān)鍵字為其左子樹(shù)中值最大的關(guān)鍵字或者其右子樹(shù)中值最小的關(guān)鍵字夏漱。找a的相鄰關(guān)鍵字的方法為：沿著a的左指針來(lái)到其子樹(shù)根結(jié)點(diǎn)豪诲，然后沿著根結(jié)點(diǎn)中最右端的關(guān)鍵字的右指針往下走，用同樣的方法一直走到葉結(jié)點(diǎn)上挂绰，葉結(jié)點(diǎn)上的最右端的關(guān)鍵字即為a的相鄰關(guān)鍵字（這里找的是a左邊的相鄰關(guān)鍵字屎篱，我們可以用同樣的思路找到a右邊的相鄰關(guān)鍵字）】伲可以看到下圖中a的相鄰關(guān)鍵字是d和e交播，要?jiǎng)h除關(guān)鍵字a，可以用d來(lái)取代a刹勃，然后按照上面的情況刪除葉子結(jié)點(diǎn)上的d即可堪侯。
【注意】
『坑取①荔仁、B樹(shù)主要用于文件系統(tǒng)以及部分?jǐn)?shù)據(jù)庫(kù)索引，例如： MongoDB芽死。而大部分關(guān)系數(shù)據(jù)庫(kù)則使用B+樹(shù)做索引乏梁，例如：mysql數(shù)據(jù)庫(kù)；
」毓蟆②遇骑、從查找效率考慮一般要求B樹(shù)的階數(shù)m >= 3;
③揖曾、B-樹(shù)上算法的執(zhí)行時(shí)間主要由讀落萎、寫(xiě)磁盤的次數(shù)來(lái)決定，故一次I/O操作應(yīng)讀寫(xiě)盡可能多的信息炭剪。因此B-樹(shù)的結(jié)點(diǎn)規(guī)模一般以一個(gè)磁盤頁(yè)為單位练链。一個(gè)結(jié)點(diǎn)包含的關(guān)鍵字及其孩子個(gè)數(shù)取決于磁盤頁(yè)的大小。
五奴拦、B-樹(shù)的應(yīng)用
為了將大型數(shù)據(jù)庫(kù)文件存儲(chǔ)在硬盤上媒鼓，以減少訪問(wèn)硬盤次數(shù)為目的，在此提出了一種平衡多路查找樹(shù)——B-樹(shù)結(jié)構(gòu)。由其性能分析可知它的檢索效率是相當(dāng)高的 為了提高 B-樹(shù)性能’還有很多種B-樹(shù)的變型绿鸣，力圖對(duì)B-樹(shù)進(jìn)行改進(jìn)疚沐，比如B+樹(shù)。
