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

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

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

延伸閱讀：

二、使用B+樹的好處

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

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