B-tree series

B Trees

It's a balanced tree , be called B Trees .
A tree M rank (M>2) Of B Trees , It's a balanced M Road balance search tree .

B Implementation of tree ：

public class BTreeNode {
    
    // One B- In the tree node , Can save key The upper limit of the number of 
    public static final int KEY_LIMIT = 4;
    //KEY_LIMIT+1: It is because the insertion space is full and will not be split , Insert one more key bring >4 Will split 
    public long[] keyList = new long[KEY_LIMIT+1];
    // Record currently owned key The number of 
    public int size = 0;
    // Range 
    public BTreeNode[] childList = new BTreeNode[KEY_LIMIT+2];


    public BTreeNode parent = null;

    @Override
    public String toString() {
    
        return String.format("%d: %s", size, Arrays.toString(Arrays.copyOf(keyList, size)));
    }
    /** *  lookup key In which sub tree  */
    public BTreeNode findKey(long key) {
    
        if (key > keyList[size-1]) {
    // Last number 
            return childList[size];
        }
        for (int i = 0; i < size; i++) {
    
            if (key == keyList[i]) {
    
                return this;
            } else if (key < keyList[i]) {
    
                // The first one is greater than key Keyword element of 
                return childList[i];
            }
        }
        return null;
    }

    public InsertResult insertKeyWithChild(long key, BTreeNode node) {
    
        // 1.  Give Way  key  Insert in order  keyList  in 
        int index = insertIntoKeyList(key);
        // 2.  according to  index  Conduct  child  Insertion 
        // childList[0, size]
        // [0, index]  Immobility 
        // [index + 1] Location   To insert  node  The subscript 
        // [index + 1, size]  Moved to  [index + 2, size + 1]  Element number  == size - index
        System.arraycopy(childList,index+1,childList,index+2,size-index);
        childList[index+1] = node;
        size++;
        // 2.  Determine whether it is necessary to split 
        // 3.  If necessary , Split nodes 
        if (shouldSplit()) {
    
            return splitNotLeaf();
        }
        return null;
    }

    // Splitting of non leaf nodes 
    private InsertResult splitNotLeaf() {
    
        int size = this.size;
        //1. Find the middle 
        int index = size / 2;
        //2. Save what you want to split key
        InsertResult result = new InsertResult();
        result.key = keyList[index];
        /** * 3.  Handle  key  Division  *  Which?  key  It should be left in the current node  [0,index)  altogether index individual  *  Which one?  key  It is split  key [index] *  Which?  key  It should be in the new node  (index,size)  altogether size-index-1 individual  */
        // take (index,size) In position key Move to the new node 
        BTreeNode node = new BTreeNode();// Create a new node 
        System.arraycopy(keyList,index+1,node.keyList,0,size-index-1);
        node.size = size-index-1;

        // hold  [index,size) be-all key Reset to 0, Reset size
        Arrays.fill(keyList,index,size,0);
        this.size = index;
        //4. Split non leaf nodes 
        System.arraycopy(this.childList, index + 1, node.childList, 0, size - index);
        //[index + 1, size + 1)
        Arrays.fill(this.childList, index + 1, size + 1, null);
        for (int i = 0; i < size - index; i++) {
    
            node.childList[i].parent = node;
        }

        /** * 5. Dealing with split parent problem  * 1)this.parent unchanged , Division does not affect the relationship between father and son  * 2)node.parent and this The same father  */
        node.parent = this.parent;
        result.node = node;
        return result;
    }

    public static class InsertResult{
    
        public long key;  // Split key
        public BTreeNode node;// Split new nodes 

    }
    public InsertResult insertKey(long key) {
    
        //key  Insert in order  keyList  in 
        insertIntoKeyList(key);
        size++;
        // Decide whether to split 
        if (shouldSplit( )) {
    
            return splitLeaf();
        }
        return null;
    }
    // Node splitting 
    private InsertResult splitLeaf() {
    
        int size = this.size;
        //1. Find the middle 
        int index = size / 2;
        //2. Save what you want to split key
        InsertResult result = new InsertResult();
        result.key = keyList[index];
        /** * 3.  Handle  key  Division  *  Which?  key  It should be left in the current node  [0,index)  altogether index individual  *  Which one?  key  It is split  key [index] *  Which?  key  It should be in the new node  (index,size)  altogether size-index-1 individual  */
        // take (index,size) In position key Move to the new node 
        BTreeNode node = new BTreeNode();// Create a new node 
        System.arraycopy(keyList,index+1,node.keyList,0,size-index-1);
        node.size = size-index-1;

        // hold  [index,size) be-all key Reset to 0, Reset size
        Arrays.fill(keyList,index,size,0);
        this.size = index;

        //4. Split leaf nodes , If childList == null, There is no need to split 

        /** * 5. Dealing with split parent problem  * 1)this.parent unchanged , Division does not affect the relationship between father and son  * 2)node.parent and this The same father  */
        node.parent = this.parent;
        result.node = node;
        return result;
    }

    // Decide whether to split 
    private boolean shouldSplit() {
    
        return size > KEY_LIMIT;
    }

    //key  Insert in order  keyList  in 
    private int insertIntoKeyList(long key) {
    
        int i;
        for (i = size-1; i >= 0; i--) {
    
            if (keyList[i] < key) {
    
                break;
            }
            // Move the value back one space , Continue to find 
            keyList[i+1] = keyList[i];
        }
        keyList[i+1] = key;
        return i+1;
    }
}

public class BTree {
    
    //B- Root node of tree 
    public BTreeNode root = null;

    //B- In the tree key The number of 
    public int size = 0;

    public boolean insert(long key) {
    
        if (insertWithoutSize(key)) {
    
            size++;
            return true;
        }
        return false;
    }

    private boolean insertWithoutSize(long key) {
    
        // Determine whether it is an empty tree 
        if(root == null) {
    
            root = new BTreeNode();
            root.keyList[0] = key;
            root.size = 1;
            return true;
        }
        // It's not an empty tree 
        BTreeNode cur = root;
        while (true) {
    
            BTreeNode node = cur.findKey(key);
            if (node == cur) {
    
                //key It's just cur In nodes 
                // You can't insert it repeatedly 
                return false;
            } else if (node == null) {
    
                //cur That's the leaf node , Directly inserted into the 
                break;
            } else {
    
                // Find a child , and cur It's not a leaf 
                cur = node;
            }
        }
        // Conduct key Insertion 
        BTreeNode.InsertResult result = cur.insertKey(key);
        while (true) {
    
            if (result == null) {
    
                // No node splitting occurred during insertion 
                return true;
            }
            // It means there is a split 
            // It needs to be split up key Insert the corresponding node with the new node 
            BTreeNode parent = cur.parent;
            if (parent == null) {
    
                //cur Root node 
                // The root node split 
                //  Need a new root node , To preserve the split  key
                root = new BTreeNode();
                root.keyList[0] = result.key;
                root.size = 1;
                root.childList[0] = cur;
                root.childList[1] = result.node;
                //  Because originally  current  It is the root node. , So its  parent == null
                //  Naturally split nodes , So did I  null
                //  So set a new parent node for them 
                cur.parent = result.node.parent = root;
                return true;
            }
            // Not root insertion 
            result = parent.insertKeyWithChild(result.key,result.node);
            cur = parent;
        }
    }
}

B+ Trees

B+ Tree search and B- The trees are basically the same , The difference is that B+ Only when the tree reaches the leaf node can it hit (B- Trees can hit in non leaf nodes ).

key Must keep a copy in the leaves . Leaf nodes are linked by a chain structure .
The database often needs all key Scan .

B+ Characteristics of trees ：
(1) All keywords appear in the linked list of leaf nodes ( Dense index ), And the nodes in the linked list are ordered .
(2) It is impossible to hit... In a non leaf node .
(3) A non leaf node is the index of a leaf node ( Sparse index ), Leaf nodes are equivalent to the data layer that stores data .
(4) More suitable for file index system

B+ Trees and B- The difference between trees ：
B- Trees ： Multiple search trees , Each node stores M/2 To M Key words , Non leaf nodes store nodes that point to keyword ranges ; All keywords appear in the whole tree , And only once , Non leaf nodes can hit ;
B+ Trees ： stay B- On the basis of trees , Add a linked list pointer to the leaf node , All keywords appear in the leaf node , The non leaf node is used as the index of the leaf node ;B+ The tree always hits the leaf node .