多路搜索樹
- 完全二叉樹高度:O(log2N),其中2為對數(shù)
- 完全M路搜索樹的高度:O(logmN),其中M為對數(shù),樹每層的節(jié)點(diǎn)數(shù)
- M路搜索樹主要用于解決數(shù)據(jù)量大無法全部加載到內(nèi)存的數(shù)據(jù)存儲。通過增加每層節(jié)點(diǎn)的個數(shù)和在每個節(jié)點(diǎn)存放更多的數(shù)據(jù)來在一層中存放更多的數(shù)據(jù),從而降低樹的高度,在數(shù)據(jù)查找時減少磁盤訪問次數(shù)。
- 所以每層的節(jié)點(diǎn)數(shù)和每個節(jié)點(diǎn)包含的關(guān)鍵字越多,則樹的高度越矮。但是在每個節(jié)點(diǎn)確定數(shù)據(jù)就越慢,但是B樹關(guān)注的是磁盤性能瓶頸,所以在單個節(jié)點(diǎn)搜索數(shù)據(jù)的開銷可以忽略。
B樹
B樹是一種M路搜索樹,B樹主要用于解決M路搜索樹的不平衡導(dǎo)致樹的高度變高,跟二叉樹退化為鏈表導(dǎo)致性能問題一樣。B樹通過對每層的節(jié)點(diǎn)進(jìn)行控制、調(diào)整,如節(jié)點(diǎn)分離,節(jié)點(diǎn)合并,一層滿時向上分裂父節(jié)點(diǎn)來增加新的層等操作來來保證該M路搜索樹的平衡。具體規(guī)則如下:
- 根節(jié)點(diǎn)的兒子樹個數(shù)在2到M之間,其他非葉子節(jié)點(diǎn)的兒子樹個數(shù)在M/2和M之間。如果兒子樹個數(shù)因?yàn)榉至殉^了M則此時需要向上遞歸分裂父節(jié)點(diǎn),當(dāng)找到一個不需要再分裂的父節(jié)點(diǎn)則停止分裂。該分裂過程直到根節(jié)點(diǎn),如果需要分裂根節(jié)點(diǎn),則會產(chǎn)生兩個根,故需要創(chuàng)建一個新的根來將這兩個根作為兒子節(jié)點(diǎn),此時樹的高度會增加1。
- 每個非葉子節(jié)點(diǎn)的關(guān)鍵字的值從左到右依次變大,第i個關(guān)鍵字代表子樹i+1中的最小關(guān)鍵字;(其中對于根節(jié)點(diǎn)來說i在1到(2到M)之間,其他非葉子節(jié)點(diǎn)則是1到(M/2到M)之間);
- B樹的所有數(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ù)查找;
- 所有葉子節(jié)點(diǎn)都在相同的深度并且每個葉子節(jié)點(diǎn)包含L/2到L項(xiàng)數(shù)據(jù)。
M和L的大小選擇
- M為B樹的階數(shù)或者說是路數(shù)
- L為每個葉子節(jié)點(diǎn)最多存放的數(shù)據(jù)項(xiàng)個數(shù)
- 在B樹中,每個節(jié)點(diǎn)都是一個磁盤區(qū)塊,所以需要根據(jù)磁盤區(qū)塊的大小來決定M和L。
磁盤區(qū)塊大小與M的計算
- 每個非葉子節(jié)點(diǎn)存放了關(guān)鍵字和指向兒子樹的指針,具體數(shù)量為:M階的B樹,每個非葉子節(jié)點(diǎn)存放了M-1個關(guān)鍵字和M個指向兒子樹的指針,故加入每個關(guān)鍵字的大小為8字節(jié)(如Java的long類型就是8字節(jié)),每個指針為4字節(jié),則M階B樹的每個非一葉子節(jié)點(diǎn)需要:8 * (M-1) + 4 * M = 12M - 8個字節(jié)。
- 如果規(guī)定每個非葉子節(jié)點(diǎn)(磁盤區(qū)塊)占用內(nèi)存不超過8K,即8192,則M最大為683,即683*12-8=8192。
葉子節(jié)點(diǎn)數(shù)據(jù)項(xiàng)個數(shù)L
- 假如每個數(shù)據(jù)項(xiàng)大小也是256字節(jié),則由于磁盤區(qū)塊大小為8K,即8192個字節(jié),而每個葉子節(jié)點(diǎn)可以存放L/2到L個數(shù)據(jù)項(xiàng),所以每個葉子節(jié)點(diǎn)最多存放:8192/256=32個數(shù)據(jù)項(xiàng),即L的大小為32。
- 一棵5階的B樹的結(jié)構(gòu)如下,即M和L等于5:其中每個非葉子節(jié)點(diǎn)包含最多M-1=5-1=4個關(guān)鍵字,包含M,即5個指向子樹指針。L等于5,則每個葉子節(jié)點(diǎn)最多存放5個數(shù)據(jù)項(xiàng)。
B+樹
B+樹結(jié)構(gòu)跟B樹基本一致,唯一的區(qū)別是B+樹的葉子節(jié)點(diǎn)之間通過指針相連形成一個鏈表,故便于遍歷所有的葉子節(jié)點(diǎn),即獲取所有或者搜索關(guān)鍵字某一范圍的所有數(shù)據(jù)項(xiàng)。MySQL的InnoDB存儲引擎就是會用B+樹作為索引實(shí)現(xiàn)。
以上所述是小編給大家介紹的多路搜索樹B樹、B+樹詳解整合,希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持!
您可能感興趣的文章:- MySQL優(yōu)化中B樹索引知識點(diǎn)總結(jié)
- 淺談MySQL的B樹索引與索引優(yōu)化小結(jié)
- 完整B樹算法Java實(shí)現(xiàn)代碼
- c語言B樹深入理解