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

2、B樹和B+樹

2.1、區(qū)別

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

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

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

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

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

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

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

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

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

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

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