一、文件系統(tǒng)和數(shù)據(jù)庫(kù)是由于什么原因才選擇B樹或B+樹建立索引的

索引的目標(biāo)是要找到數(shù)據(jù)所在的物理位置，因此用樹去實(shí)現(xiàn)搜索數(shù)據(jù)所在物理位置，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一次IO，因此結(jié)合知識(shí)點(diǎn)1為了減少搜索時(shí)間，就需要控制樹的高度，那這樣的話二叉樹明顯不行，因?yàn)槎鏄洳迦氲脑挊涞母叨仁菦](méi)辦法控制的，因此采用B+樹的形式，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)很多子節(jié)點(diǎn)，插入節(jié)點(diǎn)時(shí)增加子節(jié)點(diǎn)而不是增加樹高度。更進(jìn)一步，采用B+樹時(shí)在相同數(shù)據(jù)量的情況下如何降低樹的高度？當(dāng)然是增加每一層的數(shù)據(jù)量，而考慮到知識(shí)點(diǎn)2，一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)扇區(qū)大小存儲(chǔ)多個(gè)數(shù)據(jù)項(xiàng)，既可以降低索引文件大小，又可以在相同數(shù)據(jù)量的情況下減少每層節(jié)點(diǎn)數(shù)，提高性能。

這是配合磁盤特性的，本來(lái)查詢樹使用多分支在內(nèi)存里是沒(méi)有意義的，只會(huì)導(dǎo)致讀取了更多數(shù)據(jù)，但磁盤（或者說(shuō)機(jī)械硬盤）的特性在于，多次隨機(jī)讀取效率遠(yuǎn)低于連續(xù)讀取一大段數(shù)據(jù)，因?yàn)槊恳淮味夹枰?jīng)過(guò)尋道。這樣B樹就被設(shè)計(jì)為用較少的次數(shù)讀取磁盤，每次讀取較大的塊，從而優(yōu)化整體查詢。

延伸閱讀：

二、使用B+樹的好處

由于B+樹的內(nèi)部節(jié)點(diǎn)只存放鍵，不存放值，因此，一次讀取，可以在內(nèi)存頁(yè)中獲取更多的鍵，有利于更快地縮小查找范圍。

B+樹的葉節(jié)點(diǎn)由一條鏈相連，因此，當(dāng)需要進(jìn)行一次全數(shù)據(jù)遍歷的時(shí)候，B+樹只需要使用O(logN)時(shí)間找到最小的一個(gè)節(jié)點(diǎn)，然后通過(guò)鏈進(jìn)行O(N)的順序遍歷即可。而B樹則需要對(duì)樹的每一層進(jìn)行遍歷，這會(huì)需要更多的內(nèi)存置換次數(shù)，因此也就需要花費(fèi)更多的時(shí)間。