B+樹
B+樹是B樹的一種變體捣域，常用語(yǔ)數(shù)據(jù)庫(kù)和操作系統(tǒng)的問(wèn)題件系統(tǒng)中
- MySQL數(shù)據(jù)庫(kù)的索引就是基于B+樹實(shí)現(xiàn)的
下圖為B+樹的大概結(jié)構(gòu)
B+樹與前面研究的B樹逾条，B+樹有以下特點(diǎn)：
-
分為內(nèi)部節(jié)點(diǎn)（非葉子）與葉子節(jié)點(diǎn)兩種節(jié)點(diǎn)
葉子節(jié)點(diǎn)為最下面一層的節(jié)點(diǎn)琢岩，除了葉子節(jié)點(diǎn)以外的節(jié)點(diǎn)，都佳作內(nèi)部節(jié)點(diǎn)师脂，葉子節(jié)點(diǎn)與內(nèi)部節(jié)點(diǎn)有以下特性- 內(nèi)部節(jié)點(diǎn)只存儲(chǔ)key担孔，不存儲(chǔ)具體數(shù)據(jù)
- 葉子節(jié)點(diǎn)存儲(chǔ)key和具體數(shù)據(jù)
所以，可以理解為吃警，B+樹是用來(lái)存儲(chǔ)key-value的糕篇，所以內(nèi)部節(jié)點(diǎn)只存儲(chǔ)key，葉子節(jié)點(diǎn)才用來(lái)存儲(chǔ)key和數(shù)據(jù)
所有葉子節(jié)點(diǎn)汤徽，會(huì)形成一條有序鏈表
從上圖可以看出，葉子節(jié)點(diǎn)之間有箭頭將節(jié)點(diǎn)串起來(lái)灸撰，并且節(jié)點(diǎn)的大小是有序的
當(dāng)了解完B+樹的特點(diǎn)以后谒府，那么B+樹到底有什么用呢？
由于B+樹的非葉子節(jié)點(diǎn)浮毯，只用來(lái)存儲(chǔ)key完疫，所以當(dāng)B+樹節(jié)點(diǎn)與B樹節(jié)點(diǎn)為同樣大小的節(jié)點(diǎn)的話，B+樹可以存儲(chǔ)更多的key债蓝，因?yàn)橐粋€(gè)key相對(duì)于一個(gè)節(jié)點(diǎn)具體數(shù)據(jù)來(lái)講壳鹤，占用的空間會(huì)更少，所以可以存儲(chǔ)更多的key饰迹，這樣芳誓，可以利用key快速找到對(duì)應(yīng)的節(jié)點(diǎn)。
B樹存儲(chǔ)Key-Value的結(jié)構(gòu)如下
所以啊鸭，對(duì)比B樹锹淌，B+樹有以下一些優(yōu)勢(shì)
- 每個(gè)節(jié)點(diǎn)存儲(chǔ)的key數(shù)量更多，樹的高度更低
- 所有的具體數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)上赠制，所以每次查詢都要查到葉子節(jié)點(diǎn)赂摆，查詢速度比較穩(wěn)定
- 所有的葉子節(jié)點(diǎn)構(gòu)成了一個(gè)鏈表，做區(qū)間查詢時(shí)更方便
