圖解B Tree和B+ Tree

1 B Tree起源

一篇國外的論文：https://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf

論文名稱為大型有序索引的組織和維護，其中就指出了B Tree這個資料結構

其中，B Tree的定義：

• 從根到葉結點的每條路徑長度都是h，也稱為Tree的高度，即h = 路徑中的節點數。
• 除根節點和葉節點外，每個節點至少有k -1個兒子。 根至少有兩個兒子。
• 每個節點最多有2k-1個兒子。

2 B Tree 資料結構

/**
 * B樹資料結構
 */
private static class BTreeNode<K, V> {
    /**
     * 節點的項，按鍵非降序存放
     */
    private List<Entry<K, V>> entries;
    /**
     * 内節點的子節點
     */
    private List<BTreeNode<K, V>> children;
    /**
     * 是否為葉子節點
     */
    private boolean isLeaf;
    /**
     * 排序對象
     */
    private Comparator<K> kComparator;

    private BTreeNode() {
        entries = new ArrayList<>();
        children = new ArrayList<>();
        leaf = false;
    }
    
    /**
     * Entry類
     */
    static class Entry<K, V> {
        private K key;
        private V value;

        public Entry(K k, V v) {
            this.key = k;
            this.value = v;
        }
    }
}      

3 圖解B Tree

4 B+ Tree資料結構

• 有k個子結點的結點必然有k個關鍵碼；
• 非葉結點僅具有索引作用，跟記錄有關的資訊均存放在葉結點中。
• 樹的所有葉結點構成一個有序連結清單，可以按照關鍵碼排序的次序周遊全部記錄。

5 B Tree和B+ Tree對比

B和B+樹的差別在于，B+樹的非葉子結點隻包含導航資訊，不包含實際的值，所有的葉子結點和相連的節點使用連結清單相連，便于區間查找和周遊。

B+ 樹的優點在于：

• 由于B+樹在内部節點上不包含資料資訊，是以在記憶體頁中能夠存放更多的key。 資料存放的更加緊密，具有更好的空間局部性。是以通路葉子節點上關聯的資料也具有更好的緩存命中率。
• B+樹的葉子結點都是相鍊的，是以對整棵樹的便利隻需要一次線性周遊葉子結點即可。而且由于資料順序排列并且相連，是以便于區間查找和搜尋。而B樹則需要進行每一層的遞歸周遊。相鄰的元素可能在記憶體中不相鄰，是以緩存命中性沒有B+樹好。

子結點即可。而且由于資料順序排列并且相連，是以便于區間查找和搜尋。而B樹則需要進行每一層的遞歸周遊。相鄰的元素可能在記憶體中不相鄰，是以緩存命中性沒有B+樹好。