檢視 B樹的原始碼

'''B 樹'''（英語：B-tree）， 是一種佇電腦科學自平衡的樹仔，會當保持資料有序。這款的資料結構會當予走揣數據、順序的存取、插入數據佮刪除的動作，攏佇咧對數時間內完成。B 樹，概括來講是一个一般化的二箍搜尋樹仔（binary search tree）一个節點會當有兩个以上的子節點。佮自平衡二箍搜揣樹仔無仝，B 樹仔適用佇讀寫相對大的資料角的儲存系統，比如講磁仔。B 樹減少定位記錄的時陣所經過的中間過程，對加緊存取速度。B 樹仔這種資料結構會當用來描述外部儲存。這種資料結構定定予人應用佇資料庫佮檔案系統的實現上。

==概述==

佇咧 B 樹中，內部（非葉仔）節點會當有會當變數量的子節點（數量範圍預先定義好）。 做資料被插入抑是對一个節點內底共徙掉，伊的子節點數量發生變化。為著維持佇預先設定的數量範圍內底，內部節點可能會予人合併抑是分離。因為子節點數量有一定的允准的範圍，所以乎 B 樹仔毋免親像其他的平衡走揣樹仔彼款的頻繁地重新保持平衡，毋過因為節點無予人完全填充，可能浪費了一寡空間。子節點數量的頂界佮下界依照特定的實現設定。比如講，佇一个二嬸三 B 樹（通常簡稱二更三樹）， 每一个內部節點只有是三个子節點。

B 樹仔每一个內部會當點會包含一定數量的鍵，鍵共節點的子樹仔分開。比如講，若是一个內底節點有三个子節點（子樹呢）， 按呢伊著愛有兩个鍵：_ a _ 一和 _ a _ 二。倒爿樹仔的所有的值攏著愛細於 _ a _ 一，中央子樹的所有的值攏必須愛佇咧 _ a _ 一和 _ a _ 二之間，正爿樹仔的所有值著攏愛大於 _ a _ 二。

通常，鍵的數量被選定佇咧 $ d $ 和 $ 二 d $ 之間。其中 $ d $ 是鍵的上細數量，$ d + 一 $ 是樹仔上細欉的分支因為。佇實際上內底，鍵值占用節點中大部份的空間。因數二將的保證節點會用得予人拆分抑是組合。若是一个內底節點有 $ 二 d $ 個鍵，按呢愛加一个鍵值予這个此節點，只要拆分這 $ 二 d + 一 $ 個鍵為二个有 $ d $ 個鍵的節點，並共中央值節點徙振動到父節點。每一个拆分的節點需要有夠數目的鍵。相𫝛的地，若是一个內部節點佮伊的厝邊兩个攏有 $ d $ 個鍵，遐爾仔共通過伊佮厝邊頭尾的合併來刪除一个鍵。刪除這个鍵會造成這个節點擁有 $ d 影一 $ 個鍵；佮厝邊頭尾的合併是加上 $ d $ 個鍵，閣加上對厝邊隔壁節點的父節點徙來的一个鍵值。結果為完全填充的 $ 二 d $ 個鍵。

一个節點的分開（抑是子節點）的數量會比儲存佇咧節點內部閣較重的數量大一。佇咧二嬸三 B 樹中，內部節點會儲存一个鍵值（帶有兩个子節點）抑是二个鍵值（帶有三个子節點）。 一个 B 樹仔有時陣會去予人講 $ ( d + 一 )-( 二 d + 一 ) $ 抑是簡單咧使用上懸分支 $ ( 二 d + 一 ) $。

一个 Ｂ 樹通過約束所有葉仔節點佇咧相仝深度來保持平衡。深度佇元素添加到樹仔的過程當中沓沓仔增加，整體深度誠少地增長，並致使所有的葉仔節點佮根節點距離加一。

佇存取節點資料所費時間遠超過處理節點資料所費時間的狀況下，Ｂ 樹仔佇可選的實現中有足濟優勢，因為存取節點的開銷予人分擔到內底層節點的濟擺操作上。這通常出現佇咧做節點儲存佇咧二級的記憶體如硬碟記憶體頂懸。通過上大化內部內層節點的子節點的數量，樹仔的懸度減細，儉取節點的開銷予人縮減。另外咧，重新平衡樹的動作嘛加足少出現。子節點的上大數量攏著愛看，逐个子節點必須儲存的資訊量，佮完整磁仔角的大細抑是二次記持體中類似的容量。雖然二嬸三樹閣較會當解說，實際運用中，Ｂ 樹仔使用二級記持體，需要大量數目的子節點來提升效率。

===變體===

術語 B 樹仔會當指一个特定的方案，嘛會當指大體頂一類的方案。狹義上，一个 Ｂ 樹仔佇伊內部節點中儲存鍵值，毋過無需要佇葉仔節點頂懸儲存遮的鍵值的記錄。大體上的一類包含一寡變體，如 B + 樹佮 B \ * 樹。

佇咧 B + 樹，遮的鍵值的複製品予人儉佇咧內部節點；鍵值佮記錄儲存佇葉仔節點；另外咧，一个葉仔節點會當包含一个指標，指向另外一个葉仔節點以加速順序存取。

B \ * 樹分支出閣較濟的內部厝邊節點以保持內部節點閣較密集地填充。此變體要求非根節點至少三分之二填充，毋是二分之一。為著維持按呢的結構，做一个節點填滿了後將袂閣隨分開割節點，是共伊的鍵值佮後一个節點共享。做兩个節點攏坉滇了後，分割做三个節點。

計數 B 樹儲存，每一樹攏帶有一个指標佮指向子樹的節點數目。這就允准以鍵值為序快速走揣第 N 筆記錄，抑是統計二筆記錄之間的記錄數目，猶閣有其他足濟相關的操作。

===名號義===

魯道夫 ・ 拜而已（Rudolf Bayer）佮艾華 ・ M ・ 麥克雷（Ed M . McCreight）佇一九七二年佇波音研究實驗室（Boeing Research Labs）做工課的時陣發明矣 B 樹，但是𪜶無解說 B 就是代表啥物意義（如果若有）。 道格拉斯 ・ 科默爾（Douglas Comer）解說講 :
兩位作者從來攏毋捌解說過 B 樹仔的原始意義。正如咱所見，「 balanced」，「 broad」抑是「bushy」可能適合。其他人建議字母「B」代表 Boeing。𪜶自於伊的贊助嘛，猶毋過，看起來共 B 樹仔當做「Bayer」樹閣較適合高德納（Donald Knuth）佇伊一九八Ｏ年五月發表的題為「CS 一百四十四 C classroom lecture about disk storage and B-trees」的論文中推測了 B 樹仔的名號義，提出「B」可能意味 Boeing 抑是講 Bayer 的名。

==資料庫的問題==

===已經排序檔案的走揣時間===

通常，排序佮走揣演算法會予人通過 O 符號，刻畫為較級別的數值。嘿一个有 N 筆記錄的已經排序表進行二箍搜揣，拍一个比如講，會當佇 O（log 二 N）較有級完成。若表有一 , 零 , 空筆記錄，彼種的定位其中一筆記錄，欲佇咧二十个較級內完成。
log 二 ( 一 , 零 , 零 )=十九九三一 . . .

大數據庫一直以來被儲存佇磁碟。對磁仔頂頭讀一筆記錄，佮後壁的比較鍵值操作相比，佇開的執行時間進前者支配地位。對磁碟讀記錄的時間牽涉著一个尋道時間佮轉踅延延。尋道的時間可能是對無到二十抑是閣較濟理秒，轉踅予平均落來約是轉踅拜拜的一半。對一个七 , 兩百轉每分鐘的磁碟，旋轉周期大約是八堵三毫秒。像希捷 ST 三百五十五空三百二十 NS 按呢的彼个磁碟，磁鐵至磁鐵的尋道時間為零馮八毫秒，平均讀的時間為八堵五毫秒。為著簡單，假使對吸碟讀取開用十毫秒。

樂觀來講，如此，佇一百萬中定位一筆記錄將對談開二十擺磁碟讀取乘十毫秒每擺讀取時間，總共是零仙二秒。

時間開無遐爾害的原因是，獨立的記錄被成組地記錄佇磁碟塊頂懸。一个磁碟箍可能為十六千位元組。若逐筆記錄大細為一百六十位元組，遐爾仔一塊會當儉一百筆的記錄。頂頭假使的磁仔讀取時間確切地講是讀一个完規塊的時間。一旦磁頭到位，一个抑是閣較濟的彼个磁仔角會當較細的延遲來完成讀取。對一百筆記錄逐塊，落尾差不多六个較級是無需要任何磁碟讀取的—— 攏佇頂遍讀操作中完成矣。

為進一步來加速走揣，開始的十三抑是十四个較級（每一个需要一擺磁碟存取）著愛提速。

===提升走揣的索引===

比較大程度上的提升是通過索引來做到的。佇頂懸的彼个例中，初初磁碟讀對二的因素限制矣走揣範圍。這基本上會當通過建立一个輔助索引來改善，這索引包含講逐塊磁仔角頂懸的首筆記錄（有時叫做疏失引）。 這个輔助索引可能只有原始的資料庫百分之一大細，但是伊會當更加緊速地予人檢索。佇輔助索引起揣入口會當共咱講的主資料庫內底欲讀佗一塊；走揣輔助索引了後，咱只要讀主資料庫內底的特定的某一个磁碟分塊—— 通過一擺磁碟讀開銷。索引會使提供十 , 零入口，所以乎，按呢上濟需要十四个較級。就像主資料庫，輔助索引起最後六个左右的比較級可能佇相仝的磁碟分塊頂懸。索引會當佇大約八擺磁碟讀取中完成走揣，目標記錄會佇九擺磁碟讀了後獲得。

建立輔助索引的撇步是會當重複地予輔助索引建立輔助索引。彼會當實現一个干焦有一百入口，會當添甲滿整個磁碟塊的輔助-輔助索引。

愛揣著想欲的記錄，咱只要讀著三擺磁碟分塊，毋是十四改。讀佮走揣輔助-輔助索引中第一个（而且是唯一的）塊，標記者綜合報導。讀佮走揣輔助索引起的分塊，標記主資料庫當中相應的分箍。阮干焦需要三十毫秒，毋是一百五十毫秒就會當提著記錄。

輔助的索引，予遮的問題對約是 log 二 N 磁碟讀開銷的二分走揣，變做是 logbN 磁碟讀開銷的走揣，其中 b 為分塊因素（逐分箍的入口數目：b=一百入喙逐分箍；logb 一 , 零 , 零=三改讀）。

佇實際上內底，若是主資料庫閣被頻繁走揣，輔助-輔助索引起大部份的輔助索引可能會儲存佇磁碟緊取中，所以𪜶袂產生磁碟讀取。

===插入去攏共刣掉去的麻煩===

若是資料庫袂改變，遐爾編制索引就真簡單，而且索引永遠無需要改變。𪜶若會改變，遐爾管理資料庫佮其實連結就變甲足麻煩的。

對資料庫中刪除記錄袂引起傷大問題。索引會當保持無變，記錄只需要標記為已經刪除。資料庫猶原保持順序的狀態。若會有足濟刪除，了後走揣佮儲存就無閣遐懸效矣。

佇一个順序檔案當中進行插入將是一个災難，因為需要予人插入的記錄製造空間。佇檔案當中頭一筆記錄後插入記錄需要共所有記錄向後偏徙一个位置。按呢操作佇實際中實在傷過貴。

一種做法是預留一寡空間予插入去操作。磁碟箍有一寡空縫允准後來的插入，毋是高密度的填充。遮的記錄會當予人標記做親像刪除的記錄。

這馬乎，只要塊中存在空間，插入去攏共刣掉攏會使誠緊。若是一个插入去操作佇一塊塊頂懸揣無合的空間，就佇咧臨近的塊中走揣，而且愛調整輔助索引。向望是臨近存在有夠的空間，避免重新調整大量的角。成做是可選方案，會當使用一寡非排序的塊。

===B 樹仔運用的理念===

B 樹仔使用矣以上所有的想法。特別是：

* 保持鍵值有序，以順序遍歷
* 使用層次化的索引來小化磁碟讀取
* 使用無完全填充的塊來加速插入去佮刪除
* 通過優雅的遍歷演算法來保持索引平衡另外，B 樹通過保證內部節點至少半滿來上細化空間浪費。一欉 B 樹仔會當處理任意數目的插入佮刪除。

===B 樹的弊端===

* 除非完全重建資料庫，若無法度改變鍵值的上大長度。這予真濟資料庫系統共人名截斷到七十字元之內。

（ 其他的關聯陣列的實現，譬如講三箍撨樹仔抑是開雜鬥雜鬥表，會使動態適應任意長度的鍵值）。

==術語佮定義==

===術語===

文獻內底 B 樹仔的術語並無統一（Folk & Zoellick 一千九百九十二，p . 三百六十二）。

Bayer & McCreight ( 一千九百七十二 )，Comer ( 一千九百七十九 ) 等人將 B 樹仔的 _ 階 _ 定義為非根節點擁有鍵的上小數量。Folk & Zoellick ( 一千九百九十二 ) 指出這術語是霧嗄嗄。一个三階 B 樹鍵的上大數量可能為六抑是七。Knuth ( 一千九百九十八 , p .   四仔八十三 ) 通過將 _ 階 _ 定義為上大數量的子節點（比上大數量的鍵大一）來避免這个問題。

術語 _ 葉仔 _ 的定義嘛無一致。Bayer & McCreight ( 一千九百七十二 ) 認為葉仔層是上下跤一層的鍵，猶毋過 Knuth 認為葉仔層是上下跤一層鍵之下的一層（Folk & Zoellick 一千九百九十二，p . 三百六十三）。 可能的實現有真濟。佇一寡設計中，葉仔可能儉甲完整的資料記錄；佇咧另外一寡設計中，葉仔可能干焦儲存指向資料記錄的指標。

為著簡單，真濟作者假定一个節點會使容納固定數量的鍵。基礎的假設是鍵佮節點的大細攏是固定的。事實上，可能會去予人使用（Folk & Zoellick 一千九百九十二，p . 三百七十九）。

===定義===

根據 Knuth 的定義，一个 _ m _ 階的 B 樹仔是一个有以下屬性的樹仔：

一 . 每一个節點上濟有 _ m _ 個子節點二 . 每一个非葉仔節點（除了節點）上無嘛有⌈ _ m _ / 二 ⌉ 個子節點三 . 若根節點毋是葉仔節點，上無伊至少有兩个子節點四 . 有 _ k _ 個子節點的非葉仔節點擁有 _ k _ − 一个鍵五 . 所有的葉仔節點攏佇仝一層每一个內部節點的鍵共節點的子樹仔分開。比如講，若是一个內底節點有三个子節點（子樹呢）， 按呢伊著愛有兩个鍵：_ a _ 一和 _ a _ 二。倒爿樹仔的所有的值攏著愛細於 _ a _ 一，中央子樹的所有的值攏必須愛佇咧 _ a _ 一和 _ a _ 二之間，正爿樹仔的所有值著攏愛大於 _ a _ 二。

''''''內部節點''''''
: 內部節點是除葉仔節點佮根節點以外的所有節點。𪜶通常予人表示為一組有序的元素佮指向子節點的指標。每一个內部節點擁上濟 _ U _ 個，上少 _ L _ 個子節點。元素的數量總是比子節點指標的數量減一（元素的數量佇咧 _ L _ 板一和 _ U _ 鋪一之間）。 _ U _ 著愛等於二 _ L _ 抑是二 _ L _ 影一 ; 所以，每一个內部節點攏至少是半滿的。_ U _ 和 _ L _ 之間的關係意味對兩个半滿的節點會當合做一个合法的節點，全滿的節點會當予分裂做兩个合法的節點（若是父節點有空間容納移來的一个元素）。 遮的特性會當予佇咧 B 樹仔刪除抑是插入新的值的時陣會當調整樹仔來保持 B 樹仔的性質。

''''''根節點''''''
: 根節點擁有的子節點數量的上限佮內部節點仝款，但是無下限。比如講，做規个樹仔內底的元素數量細於 _ L _ 學一時仔，根節點是唯一的節點並且無任何子節點。

''''''葉仔節點''''''
: 葉仔節點對元素的數量有仝款的限制，但是無子節點，也無指向子節點的指標。

一个深度為 _ n _ + 一的 B 樹仔會當容納的元素數量大約是深度為 _ n _ 的 B 樹仔的 _ U _ 倍，猶毋過搜揣、插入去刪除操作的開銷嘛會增加。佮其他的平衡樹仝款，這一開銷增加的速度遠遠慢於元素數量的增加。

一寡平衡樹只佇葉仔節點中儲存值，而且葉仔節點佮內部節點使用無仝的結構。B 樹仔佇每一个節點中攏儲存值，所有的儉點有仝款的結構。毋過，因為葉仔節點無子節點，所以會當通過用專門的結構來提懸 B 樹仔的效能。

==演算法==

===搜揣===

B 樹仔的搜揣佮兩箍搜揣的樹仔類似。對根節點開始，對頂到下迴的遍歷樹。佇每一層上，搜揣的範圍予人減細到包含了撨揣值的子樹內底。子樹值的範圍予伊的父節點的鍵確定。

===插入去===

所有的插入攏對根節點開始。愛插一个新的元素，首先搜揣這欉樹仔揣著新的元素應該予人添加著的對應節點。共新元素插入到這節點內底的工課親像下：

一 . 若節點誠有的元素數量傷過上大值，遐爾仔有空間容納新的元素。共新元素插入來到這節點，而且保持節點中元素有序。
二 . 若無這節點已經滿矣，共平均分裂做兩个節點：
一 . 對該節點的原有元素佮新的元素內底選擇出中位數二 . 小於這中位數的元素共囥入倒爿節點，較大於這中位數的元素共正爿囥入來，中位數作為分隔值。
三 . 分隔值予人插入去父節點內底，這可能會造成父節點分裂，分裂父節點的時可能會閣予伊的父節點分裂，以此類推。若無父節點（這節點是根節點）， 就建立一个新的根節點（增加樹仔的懸）。

若有分裂一直升到根節點，遐爾一个新的根節點會去予建立，伊有一个分隔值佮兩个子節點。這就是根節點並無親像內部節點仝款有上少囝節點數量限制的原因。每一个節點中元素的上大數量是 _ U _ 影一。做一个節點分裂的時陣，一个元素予振動著伊的父節點，但是一个新的元素增加入來。所以上大的元素數量 _ U _ 糊著愛會當予人分做兩个合法的節點。若是 _ U _ 鋪一是奇數，遐爾 _ U _=二 _ L _，攏總有二 _ L _ 建一个元素，一个新的節點有 _ L _ 建一个元素，另外一个有 _ L _ 個元素，攏是合法的節點。若是 _ U _ 挨一个是尪仔數，遐爾 _ U _=二 _ L _ 影一 , 攏總有二 _ L _ 鋪二个元素。一半是 _ L _ 影一，拄好是節點允准的上小元素數量。

===刪除===

有兩種常用的共你斂掉策略一 . 定位並刪除元素，然後調整樹仔予伊滿足約束條件；'''抑是講'''
二 . 對頂懸到下跤處理這欉樹仔，佇進入一个節點進前，調整樹仔予伊了後一旦拄著愛刣除的鍵，伊會當共你直接刣掉啊若無需要閣進行調整以下的演算法使用矣前一種策略。

刪除一个元素的時有以下兩種特殊情況一 . 這个元素因為分隔一个內部節點的子節點二 . 刪除元素會致使伊所在的節點的元素抑是子節點數量傷過低值下跤分別是遮的狀況的處理過程

====刪除葉仔節點中的元素====

一 . 搜揣愛刣除的元素二 . 若是伊佇咧葉仔節點，共刪除對中共刣掉 . 若發生落來加溢个，照後壁「刪除了後重新平衡」部份的描述重新調整樹仔

====刪除內部節點中的元素====

內部節點內底的每一个元素攏做分隔兩粒子樹的分隔值，所以咱需要重新來劃分。值得注意的是倒子樹中上大的元素猶原較細佇分隔值。按呢仝款，正子樹中上細的元素猶原大於分隔值。這兩个元素攏佇咧葉仔節點內底，並且任何一个攏會當做兩欉樹仔的新分隔值。這个算法是來講親像下底：

一 . 選擇一个新的分隔符（倒子樹中上大的元素抑是正子樹中上細的元素）， 共伊對葉仔節點內底共徙掉，替換掉去予人刣掉的元素作為新的分隔值。
二 . 刪除了一个葉仔節點中的元素。若是這葉仔節點擁有的元素數量傷過上低要求，按呢對這葉仔節點開始重新進行平衡。

====刪除了後的重新平衡====

重新平衡對葉仔節點開始向根節點進行，到樹仔重新平衡。若準共刪除節點中的一个元素使該節點的元素數量傷低上細值，遐爾一寡元素著愛予人重新分配。通常，徙動一个元素數量大於上小值的兄弟節點中的元素。若兄弟節點攏無加的元素，遐爾仔欠元素的節點就必須愛佮伊的兄弟節點'''合併'''。敆可能致使父節點失去矣分隔值，所以父節點可能欠缺元素並且需要重新平衡。合併佮重新平衡可能一直進行到根節點，根節點變成惟一欠缺元素的節點。重新平衡樹的演算法如下：

* 若欠缺元素節的正兄弟存在閣有加的元素，遐倒爿踅一下 . 共父節點的分隔值複製到欠缺元素節點的最後（分隔值予徙落來；欠缺元素的節點這馬有上細數量的元素）
二 . 將父節點的分隔值替換做正兄弟的頭一个元素（正兄弟失去一个節點但是猶原閣有上細數量的元素）
三 . 樹閣重新平衡
* 抑無，若是欠缺元素節點的左兄弟存在閣有加的元素，遐爾仔正斡斡咧 . 共父節點的分隔值複製到欠缺元素節點的第一个節點（分隔值予徙落來；欠缺元素的節點這馬有上細數量的元素）
二 . 共父節點的分隔值替換做左兄弟的最後一个元素（左兄弟失去一个節點但是猶原閣有上細數量的元素）
三 . 樹閣重新平衡
* 抑無，若準伊的兩个直接兄弟節點攏干焦上細數量的元素，按呢共佮一个直接兄弟節點以及父節點中𪜶的分隔值合併一 . 將分隔值複製到倒爿的節點（倒爿的節點會當是欠缺元素的節點抑是擁有上小數量元素的兄弟節點）
二 . 共正爿節點中所有的元素徙振動到倒爿節點（倒爿節點這陣有上大的數量的元素，正爿節點為空）
三 . 共父節點中的分隔值佮空的正子樹徙掉（父節點失去一个元素）
* 若是父節點是根節點並且無元素矣，欲按怎釋放伊並且合併了後的節點成做新的根節點（樹仔的深度減細）
* 抑無，若是父節點的元素數量細於上細值，重新平衡父節點

==相關條目==

B + 樹

[[分類: 待校正]]