B-TreeB-Tree又叫做B樹，和平衡二叉樹不同的地方在于B樹是多叉樹(平衡多路查找樹)，Oracle和MongoDB的索引技術(shù)就是基于B樹的數(shù)據(jù)結(jié)構(gòu)，B樹也可以看作是對2-3查找樹的一種擴展。 一個m階的B-Tree有以下性質(zhì)
B樹查找我們以查找13為例子： 第一次磁盤IO:定位到比17小，選擇最左子樹； 第二次磁盤IO:定位到比12大，選擇最右子樹； 第三次磁盤IO:定位到13，查出對應的數(shù)據(jù)后，查找結(jié)束。 B樹插入對于一個m階B樹，新節(jié)點一般是插在葉子層，但是需要根據(jù)實際的情況考慮是否需要裂變。 1.若該節(jié)點中關鍵碼個數(shù)小于m-1,則直接插入； 2.若該節(jié)點中關鍵字個數(shù)等于m-1,則將進行分裂，以中間關鍵字為界點將節(jié)點一分為2，產(chǎn)生一個新的節(jié)點，并把中間那個關鍵字插入到父節(jié)點中，繼續(xù)判斷父節(jié)點的關鍵字個數(shù)是否等于m-1，依次判斷是否分裂，最壞情況下可一直分裂到根節(jié)點，整個樹增加一層。 B樹刪除B樹的刪除也非常復雜 如果關鍵字所在節(jié)點的原關鍵樹>=(m/2),說明刪除后仍可滿足B樹的結(jié)構(gòu)，可以直接干掉。 如果被刪除后不再滿足B樹的結(jié)構(gòu)，則需要一定的調(diào)整過程： 如果其左右兄弟節(jié)點中有多余的關鍵字，即與該節(jié)點相鄰的節(jié)點中關鍵字的數(shù)目大于（m/2）-1,就會將兄弟節(jié)點中的最大（左兄弟）或者最小（右兄弟）移到夫節(jié)點上，然后將雙親節(jié)點中小于（右兄弟的上移）或者大于（左節(jié)點上移）關鍵字的關鍵字下移到被刪關鍵字的節(jié)點中。 如果其左右兄弟都沒有多余關鍵字的時候，情況將變得非常非常復雜；需把刪除關鍵字節(jié)點與其左（或者右）兄弟節(jié)點中的關鍵字合并到（父節(jié)點指向該刪除關鍵字節(jié)點的左（右）兄弟節(jié)點的指針）所指向的兄弟節(jié)點中去，如果因此父節(jié)點中的關鍵字個數(shù)小于規(guī)定值，則需要對父節(jié)點做同樣的處理，最壞情況下會使得整個樹減少一層。 總結(jié)B樹相對于平衡二叉樹的不同是，每個節(jié)點包含的關鍵字增多了，特別是在B樹應用到數(shù)據(jù)庫的時候，數(shù)據(jù)庫充分利用了磁盤塊的原理（磁盤數(shù)據(jù)存儲是采用塊的形式存儲的，每個塊的大小為4K，每次IO進行數(shù)據(jù)讀取時，同一個磁盤塊的數(shù)據(jù)可以一次性讀取出來）把節(jié)點大小限制和充分使用在磁盤塊大小范圍；把樹的節(jié)點關鍵字增多后樹的層級比原來的二叉樹少了很多，大大減少了數(shù)據(jù)查找和比較的次數(shù)，提高了效率。 B+樹B+Tree中如果有N個關鍵字則會擁有n個分支，而B樹中n個關鍵字的節(jié)點包含n+1個分支。 B+Tree中，每個非根節(jié)點中的關鍵字個數(shù)是>=（m/2）且<=m，而B樹是>=（m/2）-1且<=(m-1)。 B+Tree中根節(jié)點的關鍵字個數(shù)是>=1且<=m,而B樹是>=1且<=(m-1)。 B+樹是B樹的一個升級版，因為B+Tree非葉子節(jié)點不存儲關鍵字記錄的指針，所以其相對于B樹來說B+樹更充分的利用了節(jié)點的空間，讓查找速度更加穩(wěn)定，其速度完全接近于二分查找。 \1. B+樹的非葉子節(jié)點不對關鍵字記錄的指針進行保存，只進行數(shù)據(jù)索引，使得B+樹非葉子節(jié)點能保存關鍵字的能力大大提升，而且樹的層級會更少； 2.B+樹葉子節(jié)點保存了其父節(jié)點的關鍵字記錄的指針，所以每次查詢必須到葉子節(jié)點才能真正獲取到相關數(shù)據(jù)，而且平很多叉樹的特點是所有子節(jié)點的層級相差不會超過一，所以查詢速度相對是非常穩(wěn)定的； 3.B+Tree樹葉子節(jié)點的關鍵字從小到大有序排列，左邊結(jié)尾數(shù)據(jù)都會保存右邊節(jié)點開始數(shù)據(jù)的指針； 4.非葉子節(jié)點的子節(jié)點樹=關鍵字數(shù)。
B+樹查找B+樹的查找規(guī)格是B樹一樣，都是按照大小一層一層往下，但是不同點在于其一定會執(zhí)行到葉子節(jié)點，因為只有葉子節(jié)點才會存儲數(shù)據(jù)的指針。 B+樹插入插入操作全部在葉子節(jié)點中進行 1.若為空樹，創(chuàng)建一個葉子節(jié)點，然后將記錄插入，同時這個葉子節(jié)點也是根節(jié)點； 2.若被插入的關鍵字所在的節(jié)點，其含有的關鍵字數(shù)目小于m，則直接插入； 3.若被插入關鍵字所在的節(jié)點的關鍵字數(shù)等于m的時候，則需要分裂為兩個節(jié)點，并將m/2的關鍵字上移到父節(jié)點中，同時判斷父節(jié)點的關鍵字個數(shù)是否大于m，如果需要分裂繼續(xù)按照上面的流程進行分裂。 B+樹刪除1.如果要刪除關鍵字所在節(jié)點的關鍵字個數(shù)，如果大于m/2，直接刪除即可； 2.當刪除關鍵字所在節(jié)點的關鍵字個數(shù)等于m/2的時候，若兄弟節(jié)點中含有多余的關鍵字，也可從兄弟節(jié)點中借用關鍵字完成刪除操作； 3.若兄弟節(jié)點沒有多余的關鍵字，則需要與其他兄弟進行合并； 4.如果合并后導致父節(jié)點不再符合B+樹的結(jié)構(gòu)，則需要按照上面的規(guī)律進行再次結(jié)構(gòu)的調(diào)整； 5.注意B+樹的結(jié)構(gòu)（非葉子節(jié)點會存儲索引信息，葉子節(jié)點才會存儲數(shù)據(jù)指針），修改完后還需修改其父節(jié)點中的索引值。 總結(jié)\1. B+樹的層級更少； \2. B+樹查詢速度更加穩(wěn)定； 3.B+樹天然具備排序功能，由于B+樹所有的葉子節(jié)點數(shù)據(jù)構(gòu)成了一個有序鏈表，在查詢范圍區(qū)間數(shù)據(jù)的時候會更加方便，數(shù)據(jù)緊密性很好高； 4.B+樹全節(jié)點遍歷更快：B+樹遍歷整棵樹只需要遍歷所有的葉子節(jié)點即可，而B樹需要對每一層進行遍歷，所以B+樹更有利于全表掃描； B*樹B*樹是B+樹的變種，不同點如下 1.關鍵字個數(shù)限制，B+樹初始化的關鍵字的個數(shù)是m/2，而B樹的初始化個數(shù)是2m/3,所以B樹的層級會更少； 2.B+樹節(jié)點滿時就會分裂，而B*樹滿時會檢查兄弟節(jié)點是否滿，如果兄弟節(jié)點沒有滿的話則會向兄弟節(jié)點轉(zhuǎn)移關鍵字，如果兄弟節(jié)點也滿了的話則從當前節(jié)點和兄弟節(jié)點各拿出1/3的數(shù)據(jù)創(chuàng)建一個新的節(jié)點出來。這個特性使得其相對B+樹分裂的次數(shù)也更少； 3.B*樹除了根節(jié)點外的非葉子節(jié)點也會存儲兄弟節(jié)點的指針； 總結(jié)B*樹對比 B+Tree其初始化的容量更大，存儲的關鍵字更多，層級更少，裂變次數(shù)也會更少。 |
|
|
