一、文件系統和數據庫是由于什么原因才選擇B樹或B+樹建立索引的
索引的目標是要找到數據所在的物理位置，因此用樹去實現搜索數據所在物理位置，每個節點對應一次IO，因此結合知識點1為了減少搜索時間，就需要控制樹的高度，那這樣的話二叉樹明顯不行，因為二叉樹插入的話樹的高度是沒辦法控制的，因此采用B+樹的形式，每個節點對應很多子節點，插入節點時增加子節點而不是增加樹高度。更進一步，采用B+樹時在相同數據量的情況下如何降低樹的高度？當然是增加每一層的數據量，而考慮到知識點2，一個節點對應一個扇區大小存儲多個數據項，既可以降低索引文件大小，又可以在相同數據量的情況下減少每層節點數，提高性能。
這是配合磁盤特性的，本來查詢樹使用多分支在內存里是沒有意義的，只會導致讀取了更多數據，但磁盤（或者說機械硬盤）的特性在于，多次隨機讀取效率遠低于連續讀取一大段數據，因為每一次都需要經過尋道。這樣B樹就被設計為用較少的次數讀取磁盤，每次讀取較大的塊，從而優化整體查詢。
延伸閱讀：
二、使用B+樹的好處
由于B+樹的內部節點只存放鍵，不存放值，因此，一次讀取，可以在內存頁中獲取更多的鍵，有利于更快地縮小查找范圍。
B+樹的葉節點由一條鏈相連，因此，當需要進行一次全數據遍歷的時候，B+樹只需要使用O(logN)時間找到最小的一個節點，然后通過鏈進行O(N)的順序遍歷即可。而B樹則需要對樹的每一層進行遍歷，這會需要更多的內存置換次數，因此也就需要花費更多的時間。
京公網安備 11010802030320號