1 概述

前一講提到了二叉搜索樹做鹰，從直覺的角度看击纬，貌似較好地解決了快速搜索的問題，其實不然钾麸。如果給定一個關(guān)鍵字序列<1, 2, 3, 4, 5, 6>更振，要求按照這個順序構(gòu)建一個搜索二叉樹，則這個二叉樹的高度為5饭尝，從而退化為一個鏈表肯腕，并且浪費大量的空間。因此钥平，二叉樹在具體的實踐中幾乎沒有應(yīng)用实撒。

針對二叉搜索樹的問題，本文主要講解B樹涉瘾，也會簡單提到B+樹（有些數(shù)據(jù)庫索引使用B+樹）知态。下面的內(nèi)容首先介紹B樹的背景，然后重點講解B樹上的相關(guān)操作（本文大部分內(nèi)容參考算法導(dǎo)論和維基百科）睡汹。

2 背景

B樹系列主要用在哪里肴甸？答：主要用在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)。大家知道囚巴，文件和數(shù)據(jù)庫主要存儲在磁盤（外存）上原在，特別是大數(shù)據(jù)時代友扰，大規(guī)模的數(shù)據(jù)很難一次性導(dǎo)入到硬盤，即使可以導(dǎo)入庶柿，其耗費的時間是也無法容忍的（筆者2012年的時候曾經(jīng)幫一個公司優(yōu)化過MySQL數(shù)據(jù)庫村怪，在未經(jīng)優(yōu)化的前提下，從100萬條數(shù)據(jù)中查詢數(shù)據(jù)都非常耗時）浮庐。下面對磁盤上數(shù)據(jù)的操作基本原理進(jìn)行解釋甚负。

圖1:機(jī)械磁盤

當(dāng)前應(yīng)用廣泛的機(jī)械磁盤如圖1所示。數(shù)據(jù)存儲在磁盤盤片上的磁道中审残，機(jī)械磁盤中的盤片圍繞機(jī)械軸運(yùn)行梭域，讀寫磁頭定位到需要讀寫的磁道（機(jī)械操作），然后再進(jìn)行讀寫操作（電子操作）搅轿。機(jī)械操作的時間比電子操作的時間要高出5個數(shù)量級病涨，因此，讀寫操作的效率取決于定位磁道（機(jī)械操作）的次數(shù)璧坟，即讀寫磁盤的次數(shù)既穆。因此，降低磁盤讀寫操作次數(shù)是提高讀寫效率的關(guān)鍵雀鹃。這時幻工，就需要某種合理的數(shù)據(jù)組織形式來降低磁盤讀寫的次數(shù)。B樹即是解決此類問題的基本數(shù)據(jù)結(jié)構(gòu)黎茎，B樹大致的樣子如圖2所示：

圖2: B樹的長相

與二叉搜索樹不同囊颅，B樹是一顆平衡樹，即各子樹的高度是一致的工三，且每個節(jié)點中存放的關(guān)鍵字?jǐn)?shù)量t通常遠(yuǎn)大于2（通常是1000左右）迁酸。假設(shè)除根節(jié)點外的所有節(jié)點都存儲在磁盤上先鱼，一次讀寫操作訪問一個B樹節(jié)點俭正，對于查找操作，定位到任何一個節(jié)點需要訪問磁盤的次數(shù)不超過樹的高度h焙畔，如果每個節(jié)點中存放的關(guān)鍵字越多掸读，則其高度h越小，即訪問磁盤的次數(shù)越少宏多，這樣就可有效降低讀寫磁盤的次數(shù)儿惫。

如果t=1000，則高h(yuǎn)為2的B樹伸但，其存儲的關(guān)鍵字個數(shù)達(dá)10億個肾请，定位任何一個關(guān)鍵字需要的磁盤操作樹不超過2。

3 B樹的結(jié)構(gòu)

B樹是一顆有根樹（設(shè)為T.root)更胖，所有節(jié)點具有如下性質(zhì)（有點多铛铁，從背景的角度容易理解）：

• 每個節(jié)點node具有如下屬性：

  • node.n隔显，存儲node中的關(guān)鍵字?jǐn)?shù)量；
  • node.n個關(guān)鍵字本身node.key₁,node.key₂, ..., node.key_n以非降序的方式存放饵逐；
  • node.leaf是一個布爾值括眠，標(biāo)示當(dāng)前節(jié)點是否是葉子節(jié)點；

• 每個內(nèi)部節(jié)點（非葉子節(jié)點）node包含指向node.n+1個孩子節(jié)點的指針node.c₁,node.c₂,...,node.c_n+1倍权；

• 關(guān)鍵字node.key_i對各子樹中的關(guān)鍵字加以分割掷豺，假設(shè)其左右孩子分別為node.c_i、node.c_i+1薄声，則node.c_i中的所有關(guān)鍵字不大于node.key_i当船，node.c_i+1的所有關(guān)鍵字不小于node.key_i；

• 每個葉子節(jié)點具有相同的深度默辨；

• 每個節(jié)點包含的關(guān)鍵字個數(shù)有規(guī)定的取值范圍生年，由B樹的度d（>= 2）決定:

  • 除根節(jié)點外，其它節(jié)點至少有d-1個關(guān)鍵字廓奕，即除根節(jié)點外抱婉，所有節(jié)點至少包含d個孩子節(jié)點。如果樹非空桌粉，根節(jié)點至少又個關(guān)鍵字蒸绩。（注：這里沒有說根節(jié)點只有一個關(guān)鍵字）
  • 每個節(jié)點至多包含2d-1個關(guān)鍵字。因此铃肯，一個內(nèi)部節(jié)點患亿，至多有2d個節(jié)點，當(dāng)一個節(jié)點恰好有2d-1個節(jié)點時押逼，則稱此節(jié)點時滿的（非常重要步藕，插入刪除操作需要關(guān)注的重點）

B樹的高度h滿足： h <= log_d((n+1)/2)，其證明分析如下圖3所示：

圖3: B樹的高度分析過程

4 B樹的操作

在B樹定義的基礎(chǔ)上挑格，如何查詢咙冗、增加、刪除是關(guān)鍵漂彤。在后面的算法描述中雾消，引入磁盤讀寫操作，分別記作diskRead(t,x), diskWrite(t, x)挫望，表示從子樹t中讀寫x立润。

4.1 查詢操作：BTreeSearch

查詢操作的思路很容易理解：對于子樹t，要搜尋關(guān)鍵字key媳板，首先在子樹t中尋找桑腮，若存在關(guān)鍵字，則返回蛉幸，若不存在破讨，則定位到對應(yīng)的子樹（假設(shè)一次讀取一個節(jié)點旨巷，這一過程要繼續(xù)讀磁盤），遞歸搜索添忘。其算法描述如下：
BTreeSearch(t, k){ i =1; while i <= t.n and k > t.key[i]{ i++; } if i <= t.n and k == t.key[i] return (t, i); // t表示子樹根采呐，i表示這個根節(jié)點中的index elif t.leaf return nil; else diskRead(t, c[i]) return BTreeSearch(t.c[i], k); }
顯然，BTreeSearch算法的執(zhí)行時間分為兩部分：1）內(nèi)存類遍歷時間O(t)搁骑；2）讀寫磁盤次數(shù)為O(h)斧吐，設(shè)讀取一次磁盤的時間為T，則總的時間為： O(ht) + TO(h).

4.2 插入操作BTreeInsert(t, k)

B樹中的插入操作比較麻煩仲器，因為要保持B樹的特征不變煤率。其關(guān)鍵在于要保持除根節(jié)點外的所有節(jié)點的關(guān)鍵字?jǐn)?shù)目滿足：d -1 <= n <= 2d，根據(jù)這一規(guī)則乏冀，分情況討論如下：

• 如果t為空樹蝶糯，則直接構(gòu)造一個節(jié)點t，并將此節(jié)點作為根辆沦；
• 如果t非空昼捍，則遍歷t中的關(guān)鍵字，尋找插入點肢扯，此時情況又分幾種情況：
  1. 如果t.leaf = true(為葉子節(jié)點)妒茬，且t.n < 2d，則按照非降序原則插入關(guān)鍵字k蔚晨；
  2. 如果t.leaf = true乍钻，且t.n = 2d - 1，即此節(jié)點是滿的铭腕，則此節(jié)點t需要分裂以保持特性银择，分裂規(guī)則為：將關(guān)鍵字為[t.key₁,t.key₂,...,t.key_2d-1]分裂為t_left=[t.key₁,t.key₂,...,t.key_d-1]、t_right=[t.key_d+1,t.key₂,...,t.key_2d-1]兩棵子樹累舷，然后將t.key_d插入到其父節(jié)點t.p的合適位置location, 并將t_left和t_right分別作為t.p.key[location]的左右子樹浩考；如果在向父節(jié)點t.p插入t.key_d前，父節(jié)點已滿笋粟，則按照此情況繼續(xù)分裂父節(jié)點t.p;
  3. 如果t.leaf = false(為內(nèi)部節(jié)點怀挠，非葉子節(jié)點)析蝴，可以有兩種思路害捕，一種思路是先檢查當(dāng)前節(jié)點是否已滿，如果已滿闷畸，則分裂尝盼，然后再插入節(jié)點；另一種則是佑菩，先定位到需要插入的葉子節(jié)點位置盾沫，如果葉子節(jié)點已滿裁赠，則分裂，分裂完成之后赴精，再插入節(jié)點佩捞，分別介紹如下：
  • 如果t中的節(jié)點已滿，則按照2）中的方法分裂蕾哟，分裂后t.key[d]移到父節(jié)點t'.key[m]一忱，t.key[1]...t.key[d-1]作為t'.key[m]的左孩子left，t.key[d+1]...t.key[2d-1]作為t'.key[m]的右孩子right谭确；然后根據(jù)k與t'.key[m]的大小決定插入到哪個子樹帘营，若k < t'.key[m]，執(zhí)行BTreeInsert(left, k)逐哈，反之芬迄，則執(zhí)行BTreeInsert(right, k);
  • 在t中尋找合適的位置m，使其滿足: t.key[m] < k < t.key[m+1]或k < t.key[0];當(dāng)t.key[m] < k < t.key[m+1]滿足時昂秃，進(jìn)入t.key[m]的右子樹t.child[m]禀梳，繼續(xù)執(zhí)行BTreeInsert(t.child[m], k)；當(dāng)k < t.key[0]時肠骆，進(jìn)入 t.key[0]的左子樹t.child[0]出皇，執(zhí)行BTreeInsert(t.child[0], k)；直到葉子節(jié)點哗戈，然后再從葉子節(jié)點逐層向上回溯郊艘，判斷是否需要逐層向上分裂。（顯然唯咬，這種方法比前一種方法多了一個回溯判斷非葉子節(jié)點的情況纱注，但是從總體執(zhí)行效率上講，兩者是一致的胆胰，兩種方法分裂的次數(shù)是一致的狞贱，前一種方法將分裂的情況分?jǐn)傇诿恳淮蔚牟迦氩僮髦辛耍笳邉t有可能在某次操作中執(zhí)行更多的分裂蜀涨，總體上而言瞎嬉，前者的均衡效果更好，現(xiàn)實中基本上都采用前者）

為了不讓大家搞暈厚柳，請查閱圖4所示直觀理解氧枣。

圖4:B樹中插入節(jié)點的過程(d=3)

其算法為：
BTreeInsert(t, k){ r = t.root; if r.n = 2d - 1{ s = allocateNode(); // 構(gòu)造一個B樹節(jié)點 t.root = s; s.leaf = false; s.n = 0; s.child[1] = r; BTreeSplitChild(s, 1); // 將t分裂 BTreeInsertNotFull(s, k); // 向非空B樹中插入節(jié)點 } else BTreeInsertNotFull(r, k); }
分析BTreeInsert，讀取磁盤的次數(shù)為O(h)别垮，分裂B樹的次數(shù)也為O(h)便监，即寫磁盤的次數(shù)也為O(h)，因此，讀寫總次數(shù)為O(h)

4.3 B樹刪除

在B樹中刪除節(jié)點時烧董，同樣要保持B樹的特征毁靶，此時，關(guān)注的重點是：待刪除的節(jié)點中逊移，刪除節(jié)點后预吆，其節(jié)點個數(shù)是否會小于d-1.如果只滿足這個要求，是否會出現(xiàn)問題胳泉，下面看一個具體的例子：

圖5: d=3的B樹

若刪除關(guān)鍵字為1的元素啡浊，則變?yōu)椋?/p>

圖6: 刪除1后的樹的情況

非常幸運(yùn)的是，在這個例子中貌似沒有問題胶背，因為根節(jié)點的關(guān)鍵字個數(shù)可以保持一個巷嚣，如果圖5中的（50， 100）不是根節(jié)點钳吟，而是內(nèi)部節(jié)點廷粒，則刪除關(guān)鍵字為1的元素后，圖6就違反了B樹的特征红且。

從上面分析可以看出坝茎，如果只要求刪除節(jié)點過程中，僅僅滿足節(jié)點數(shù)不小于d-1暇番，會造成圖5->圖6變化的問題嗤放。

如果在B樹T刪除k的過程中，始終能夠保持當(dāng)前節(jié)點node中數(shù)量至少為d壁酬，則可以保證不會出現(xiàn)圖5圖6中那樣的問題次酌。在當(dāng)前節(jié)點node中刪除k的方法BTreeDelete(node, x)可分為如下幾種情況（始終注意當(dāng)前節(jié)點的意義，如下的幾種情況明確說明了k是否在當(dāng)前節(jié)點中的情況）：

• 如果node為葉子節(jié)點（意味著node.n >=d）且k在node中舆乔，則直接刪除k;
• 如果node為內(nèi)部節(jié)點岳服，且k在node中，則分為如下幾種情況：
  a. 如果node中希俩，k的左孩子left至少包含d個關(guān)鍵字吊宋，則以左孩子left為當(dāng)前節(jié)點，尋找left中的最大關(guān)鍵字k', 執(zhí)行BTreeDelete(left, k')颜武，并返回k',以k'代替node節(jié)點中的k璃搜；
  b. 如果node中，k的右孩子right至少包含d個關(guān)鍵字鳞上，則以右孩子right為當(dāng)前節(jié)點这吻，尋找right中的最小關(guān)鍵字k', 執(zhí)行BTreeDelete(right, k')，并返回k',以k'代替node節(jié)點中的k因块；
  c. 如果node中k的左右孩子關(guān)鍵字均只包含d-1個關(guān)鍵字橘原，則將左右孩子合并即可；
• 如果關(guān)鍵字k不在當(dāng)前內(nèi)部節(jié)點node中涡上，若k在樹中趾断，則必然在node的某棵子樹node.c[i]中。如果node.c[i].n >= d吩愧，已滿足前面討論的要求芋酌，遞歸刪除即可；若node.c[i].n = d - 1雁佳，則要求通過某種操作滿足node.c[i].n = d,以規(guī)避圖5圖6中出現(xiàn)的狀況脐帝，然后繼續(xù)執(zhí)行BTreeDelete(node.c[i], k)，具體可分為如下兩種情況：
  a. 若node.c[i].n = d - 1糖权，但它的相鄰左兄弟或有兄弟的關(guān)鍵字?jǐn)?shù)量不少于d堵腹，則通過node，將左兄弟或右兄弟的某個關(guān)鍵字移至node中（具體移動哪個關(guān)鍵字其實很容易獲取）星澳，將node中的對應(yīng)的關(guān)鍵字移至node.c[i]中疚顷；
  b. 若a不成立，則必然是左右兄弟關(guān)鍵字?jǐn)?shù)量都是d-1禁偎，將兩者合并即可.

分析這一刪除過程腿堤，由于在當(dāng)前子樹中刪除k時，始終保持了當(dāng)前子樹根節(jié)點的個數(shù)始終不小于d（整棵樹的根節(jié)點除外）如暖，因此笆檀，不會出現(xiàn)在刪除過程中向上回溯的過程，即節(jié)點中關(guān)鍵字移動控制在當(dāng)前子樹中盒至。同樣酗洒，在分析的過程中，始終是單向由樹根向葉子前進(jìn)枷遂，其訪問磁盤的次數(shù)為O(h)次（h為樹高）寝蹈。

具體的例子如圖7所示：

圖7:刪除節(jié)點圖示

關(guān)于B樹中刪除元素的方法其實不止這一種，筆者本人最近也在嘗試結(jié)合概率算法對B樹中的操作進(jìn)行優(yōu)化登淘，感興趣的童鞋也可以進(jìn)一步思考箫老。

5 總結(jié)

B樹在算法中的地位至關(guān)重要，它對高效訪問外存提供了堅實的算法基礎(chǔ)黔州。在很多場合耍鬓，童鞋們可能也聽說過B+樹，B+樹其實就是B樹的一個變體流妻，其最大的不同之處在于B+樹中的所有節(jié)點可以看成是索引牲蜀，最終的數(shù)據(jù)內(nèi)容在葉子節(jié)點上，且所有葉子節(jié)點組成鏈表的方式绅这，因此涣达，在B+樹中尋找節(jié)點，可以同時使用B樹搜索和鏈表搜索，結(jié)合具體場景度苔，選擇一個更加高效的搜索方法匆篓。