图解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+树好。