B+樹

B+樹概況

B+樹
  • InnoDB使用了B+樹索引模型
  • 每個(gè)索引在InnoDB里面對(duì)應(yīng)一棵B+樹

B+樹特點(diǎn)

  • m階B+樹每個(gè)節(jié)點(diǎn)至多有m個(gè)子女
  • 除根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)至少有[m/2]個(gè)子女，根節(jié)點(diǎn)至少有兩個(gè)子女
  • 有k個(gè)子樹的中間節(jié)點(diǎn)包含有k個(gè)元素，每個(gè)元素不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)上
  • 所有的葉子節(jié)點(diǎn)中包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子節(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接
  • B+樹的查找，當(dāng)索引部分某個(gè)節(jié)點(diǎn)的關(guān)鍵字與所查的關(guān)鍵字相等時(shí)，并不停止查找，應(yīng)繼續(xù)沿著這個(gè)關(guān)鍵字左邊的指針向下，一直查到該關(guān)鍵字所在的葉子節(jié)點(diǎn)為止。
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容