什么是多路搜索樹(shù)B樹(shù)和B+樹(shù)

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

創(chuàng)新互聯(lián)專(zhuān)注于企業(yè)成都全網(wǎng)營(yíng)銷(xiāo)、網(wǎng)站重做改版、福鼎網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5場(chǎng)景定制、商城網(wǎng)站建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為福鼎等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。

多路搜索樹(shù)

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

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

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

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

 B樹(shù)

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

  1. 根節(jié)點(diǎn)的兒子樹(shù)個(gè)數(shù)在2到M之間，其他非葉子節(jié)點(diǎn)的兒子樹(shù)個(gè)數(shù)在M/2和M之間。如果兒子樹(shù)個(gè)數(shù)因?yàn)榉至殉^(guò)了M則此時(shí)需要向上遞歸分裂父節(jié)點(diǎn)，當(dāng)找到一個(gè)不需要再分裂的父節(jié)點(diǎn)則停止分裂。該分裂過(guò)程直到根節(jié)點(diǎn)，如果需要分裂根節(jié)點(diǎn)，則會(huì)產(chǎn)生兩個(gè)根，故需要?jiǎng)?chuàng)建一個(gè)新的根來(lái)將這兩個(gè)根作為兒子節(jié)點(diǎn)，此時(shí)樹(shù)的高度會(huì)增加1。

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

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

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

 M和L的大小選擇

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

  2. L為每個(gè)葉子節(jié)點(diǎn)最多存放的數(shù)據(jù)項(xiàng)個(gè)數(shù)

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

 磁盤(pán)區(qū)塊大小與M的計(jì)算

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

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

 葉子節(jié)點(diǎn)數(shù)據(jù)項(xiàng)個(gè)數(shù)L

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

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

 什么是多路搜索樹(shù)B樹(shù)和B+樹(shù)

B+樹(shù)

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

以上就是什么是多路搜索樹(shù)B樹(shù)和B+樹(shù)，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見(jiàn)到或用到的。希望你能通過(guò)這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

網(wǎng)頁(yè)題目：什么是多路搜索樹(shù)B樹(shù)和B+樹(shù)
URL網(wǎng)址：http://bm7419.com/article42/gejpec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、微信公眾號(hào)、網(wǎng)頁(yè)設(shè)計(jì)公司、網(wǎng)站導(dǎo)航、品牌網(wǎng)站建設(shè)、手機(jī)網(wǎng)站建設(shè)

廣告

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

成都seo排名網(wǎng)站優(yōu)化