1、二叉樹(shù)：每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)

2、B樹(shù)和B+樹(shù)

2.1、區(qū)別

1）B+樹(shù)只有葉子節(jié)點(diǎn)會(huì)存儲(chǔ)指針，B樹(shù)所有節(jié)點(diǎn)都帶

2）B+樹(shù)葉子節(jié)點(diǎn)存儲(chǔ)了所有數(shù)據(jù)，B樹(shù)在內(nèi)部節(jié)點(diǎn)出現(xiàn)的數(shù)據(jù)不會(huì)出現(xiàn)在葉子節(jié)點(diǎn)

3）B+樹(shù)所有葉子節(jié)點(diǎn)都是通過(guò)指針連在一起，B樹(shù)不是

2.2、B+樹(shù)優(yōu)點(diǎn)

1）內(nèi)部節(jié)點(diǎn)不存儲(chǔ)指針，使得一個(gè)內(nèi)部節(jié)點(diǎn)中可以容納更多的數(shù)據(jù)

2）葉子節(jié)點(diǎn)通過(guò)指針連在一起范圍掃描很方便，B樹(shù)就要在葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)之間不停往返

2.3、B樹(shù)優(yōu)點(diǎn)

對(duì)于內(nèi)部節(jié)點(diǎn)，可以直接得到指針

2.4、為什么數(shù)據(jù)庫(kù)索引用B+樹(shù)

1）因?yàn)槿~子節(jié)點(diǎn)上存儲(chǔ)了所有的數(shù)據(jù)和索引而且相互之間用指針連在一起，對(duì)于范圍查找不用跨層就能把數(shù)據(jù)查出來(lái)

2）因?yàn)榉侨~子節(jié)點(diǎn)不存儲(chǔ)索引，所以每個(gè)節(jié)點(diǎn)能容納更多數(shù)據(jù)，也就是樹(shù)會(huì)更低，IO次數(shù)少