本篇文章給大家分享的是有關(guān)什么是多路搜索樹B樹和B+樹，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

10年積累的網(wǎng)站設(shè)計制作、做網(wǎng)站經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認識你，你也不認識我。但先網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有鞏留免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

多路搜索樹

1. 完全二叉樹高度：O(log2N)，其中2為對數(shù)

2. 完全M路搜索樹的高度：O(logmN)，其中M為對數(shù)，樹每層的節(jié)點數(shù)

3. M路搜索樹主要用于解決數(shù)據(jù)量大無法全部加載到內(nèi)存的數(shù)據(jù)存儲。通過增加每層節(jié)點的個數(shù)和在每個節(jié)點存放更多的數(shù)據(jù)來在一層中存放更多的數(shù)據(jù)，從而降低樹的高度，在數(shù)據(jù)查找時減少磁盤訪問次數(shù)。

4. 所以每層的節(jié)點數(shù)和每個節(jié)點包含的關(guān)鍵字越多，則樹的高度越矮。但是在每個節(jié)點確定數(shù)據(jù)就越慢，但是B樹關(guān)注的是磁盤性能瓶頸，所以在單個節(jié)點搜索數(shù)據(jù)的開銷可以忽略。

 B樹

B樹是一種M路搜索樹，B樹主要用于解決M路搜索樹的不平衡導致樹的高度變高，跟二叉樹退化為鏈表導致性能問題一樣。B樹通過對每層的節(jié)點進行控制、調(diào)整，如節(jié)點分離，節(jié)點合并，一層滿時向上分裂父節(jié)點來增加新的層等操作來來保證該M路搜索樹的平衡。具體規(guī)則如下：

1. 根節(jié)點的兒子樹個數(shù)在2到M之間，其他非葉子節(jié)點的兒子樹個數(shù)在M/2和M之間。如果兒子樹個數(shù)因為分裂超過了M則此時需要向上遞歸分裂父節(jié)點，當找到一個不需要再分裂的父節(jié)點則停止分裂。該分裂過程直到根節(jié)點，如果需要分裂根節(jié)點，則會產(chǎn)生兩個根，故需要創(chuàng)建一個新的根來將這兩個根作為兒子節(jié)點，此時樹的高度會增加1。

2. 每個非葉子節(jié)點的關(guān)鍵字的值從左到右依次變大，第i個關(guān)鍵字代表子樹i+1中的最小關(guān)鍵字；（其中對于根節(jié)點來說i在1到（2到M）之間，其他非葉子節(jié)點則是1到（M/2到M）之間）；

3. B樹的所有數(shù)據(jù)項都存放到葉子節(jié)點，非葉子節(jié)點不存放數(shù)據(jù)，非葉子節(jié)點只存放用于指示搜索方向的關(guān)鍵字，即索引。這樣有利于將更多的非葉子節(jié)點加載到內(nèi)存中，方便進行數(shù)據(jù)查找；

4. 所有葉子節(jié)點都在相同的深度并且每個葉子節(jié)點包含L/2到L項數(shù)據(jù)。

 M和L的大小選擇

1. M為B樹的階數(shù)或者說是路數(shù)

2. L為每個葉子節(jié)點最多存放的數(shù)據(jù)項個數(shù)

3. 在B樹中，每個節(jié)點都是一個磁盤區(qū)塊，所以需要根據(jù)磁盤區(qū)塊的大小來決定M和L。

 磁盤區(qū)塊大小與M的計算

1. 每個非葉子節(jié)點存放了關(guān)鍵字和指向兒子樹的指針，具體數(shù)量為：M階的B樹，每個非葉子節(jié)點存放了M-1個關(guān)鍵字和M個指向兒子樹的指針，故加入每個關(guān)鍵字的大小為8字節(jié)（如Java的long類型就是8字節(jié)），每個指針為4字節(jié)，則M階B樹的每個非一葉子節(jié)點需要：8 * (M-1) + 4 * M = 12M - 8個字節(jié)。

2. 如果規(guī)定每個非葉子節(jié)點（磁盤區(qū)塊）占用內(nèi)存不超過8K，即8192，則M大為683，即683*12-8=8192。

 葉子節(jié)點數(shù)據(jù)項個數(shù)L

1. 假如每個數(shù)據(jù)項大小也是256字節(jié)，則由于磁盤區(qū)塊大小為8K，即8192個字節(jié)，而每個葉子節(jié)點可以存放L/2到L個數(shù)據(jù)項，所以每個葉子節(jié)點最多存放：8192/256=32個數(shù)據(jù)項，即L的大小為32。

2. 一棵5階的B樹的結(jié)構(gòu)如下，即M和L等于5：其中每個非葉子節(jié)點包含最多M-1=5-1=4個關(guān)鍵字，包含M，即5個指向子樹指針。L等于5，則每個葉子節(jié)點最多存放5個數(shù)據(jù)項。

 

B+樹

B+樹結(jié)構(gòu)跟B樹基本一致，唯一的區(qū)別是B+樹的葉子節(jié)點之間通過指針相連形成一個鏈表，故便于遍歷所有的葉子節(jié)點，即獲取所有或者搜索關(guān)鍵字某一范圍的所有數(shù)據(jù)項。MySQL的InnoDB存儲引擎就是會用B+樹作為索引實現(xiàn)。

以上就是什么是多路搜索樹B樹和B+樹，小編相信有部分知識點可能是我們?nèi)粘９ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學到更多知識。更多詳情敬請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

當前文章：什么是多路搜索樹B樹和B+樹-創(chuàng)新互聯(lián)
URL分享：http://chinadenli.net/article40/eojho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計公司、做網(wǎng)站、網(wǎng)站營銷、Google、云服務(wù)器、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)