2019-11-15

数据结构 B+树

words: 1.4k views: time: 6min

B+树又在B树基础上做了一些改进，主要是在树叶节点上添加了一个链表结构，这样可以很好的解决范围查询问题。具体做法是将所有数据节点放在最下一层树叶节点上，所有的树叶自左向右为一个链表，而对于任意非树叶节点，不保存数据，只充当索引，这样节点可以保存更多的关键字，从而使树的高度更低，其实如果去掉最下一层树叶节点的话，它就是一颗B树。

1. 定义

参考B树，不再赘述：数据结构. B树

2. 分析实现

还是以5阶树为例，讨论下插入和删除

2.1. 插入

与B树一样，区别只在于最下一层进行拆分时，只将树叶拆为两部分，中间元素划分给右边，然后在父节点中创建一个与中间元素等值的元素（只包含索引数据），并将拆的两个树叶链接为它的左右子节点。

示例

依次插入3、8、11、31、23

接着依次插入29、50

接着再依次插入32、33、34、35、36、37

2.2. 删除

根据B+树的特点，要删除的关键字肯定都在树叶节点中，并且内部节点的关键字全部来自于树叶节点的第0位。因此，在删除树叶关键字时，如果位于第0位，不管是否富余，都要记得修改父节点。

1.树叶节点富余，那么直接删除。

示例

依次插入3,8,11,23,31,32，删除32,11

2.树叶节点不富余，但兄弟节点富余，那么可以向兄弟节点借。

示例

依次插入3,8,11,23,31，然后删除3

3.树叶节点不富余，且兄弟节点也不富余，那么可以与兄弟节点合并。

示例

依次插入3,8,11,23,29,31,32,33,34,35,36,37,50，删除23

3. java实现

继承前面B树的实现做一些修改，这里没有实现remove，也是考虑到本身没有太大实现意义，有时间了可以再试一试

https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/BTreeExtended.java

public class ExtendBTree<E extends Comparable<? super E>> extends BTree<E> {

    private ENode<E> root;

    public ExtendBTree(int m) {
        super(m);
        this.root = new ENode<>(m, null, null);
    }

    private static class ENode<E> extends BTree.Node<E> {

        ENode<E> next;

        ENode(int m, Entry<E> leftEntry, Entry<E> rightEntry) {
            super(m, leftEntry, rightEntry);
        }
    }

    @Override
    protected Node<E> getRoot() {
        return root;
    }

    @Override
    public void clear() {
        root = new ENode<>(m, null, null);
        size = 0;
    }

    @Override
    public void add(E e){
        add(e, root, height);
    }

    @Override
    protected void fixAdd(Node<E> node, int ht) {
        if(ht == 0){
            fixLeafAdd((ENode<E>)node, ht);
        }else{
            super.fixAdd(node, ht);
        }
    }

    private void fixLeafAdd(ENode<E> leaf, int ht){
        if(leaf.entrys[m - 1] == null){
            return;
        }

        Entry<E>[] entrys = leaf.entrys;
        Entry<E> middle = entrys[middleIndex + 1];  
        //实际中这里新建的关键字不需要包含卫星数据data，只要索引数据
        Entry<E> created = new Entry<>(middle.element, 0, null, null, null); 

        ENode<E> right = new ENode<>(m, created, null); 
        leaf.next = right;
        created.leftNode = leaf;
        created.rightNode = right;

        initEntrys(leaf, m);
        System.arraycopy(entrys, 0, leaf.entrys, 0, middleIndex + 1);
        System.arraycopy(entrys, middleIndex + 1, right.entrys, 0, middleIndex + 2);
        fixEntryNode(right.entrys, right);
        fixIndex(0, right);

        //created插入到上层Node, 并确定它的前后Entry, 修正相互关联
        if(leaf.leftEntry != null){
            Entry<E> preEntry = leaf.leftEntry; 
            Node<E> parent = preEntry.node;

            int index = preEntry.index;
            Entry<E> afterEntry = parent.entrys[index + 1]; 
            if(afterEntry != null){
                afterEntry.leftNode = right;
            }
            right.rightEntry = afterEntry;
            leaf.rightEntry = created;

            System.arraycopy(parent.entrys, index + 1, parent.entrys, index + 2, m - index - 2);
            parent.entrys[index + 1] = created;
            created.node = parent;
            fixIndex(index, parent);
            fixAdd(parent, ht + 1);
        }else if(leaf.rightEntry != null){ 
            Entry<E> afterEntry = leaf.rightEntry; 
            Node<E> parent = afterEntry.node;

            afterEntry.leftNode = right;
            right.rightEntry = afterEntry;
            leaf.rightEntry = created;

            int index = afterEntry.index;
            System.arraycopy(parent.entrys, index, parent.entrys, index + 1, m - index - 1);
            parent.entrys[index] = created;
            created.node = parent;
            fixIndex(index, parent);
            fixAdd(parent, ht + 1);
        }else{
            height++;
            root = new ENode<>(m, null, null);
            root.entrys[0] = created;
            created.node = root; 
        }
    }

    @Override
    public void remove(E e) { 
        //TODO 
    }

    @Override
    public String toString() {
        Entry<E> entry = findMin(root, height);
        ENode<E> node = (ENode<E>)entry.node;

        List<E> list = new LinkedList<>();
        build(list, node);
        while((node = node.next) != null){
            build(list, node);
        }
        return list.toString();
    }

    private void build(List<E> list, ENode<E> node){
        for(Entry<E> entry : node.entrys){
            if(entry == null){
                return;
            }
            list.add(entry.element);
        }
    }
}

4. B*树

B*在B+树的基础上又更进了一步，其在B+树的非根和非叶子结点之间增加了指向兄弟的指针。

对于B*的分裂，当一个结点满时：

如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；

如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

因此，B*树分配新结点的概率比B+树要低，但空间使用率更高，将结点的最低利用率从1/2提高到2/3。

参考：