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