1-Relational Database/1-Relational DB Concepts/B-Tree & B+ Tree/java/BTreeBase.java
/**
     * Private helper method to percolate up.
     * @param curr current node
     * @param path path along which to find the leaf
     * @param pastInsertPositions insert positions along path
     */
Private helper method to percolate up.
@param curr current node
@param path path along which to find the leaf
@param pastInsertPositions insert positions along path
Private helper method to percolate up . @param curr current node @param path path along which to find the leaf @param pastInsertPositions insert positions along path
protected void percolateUp(Node curr, Stack<Node> path, Stack<Integer> pastInsertPositions) {
        int mid = curr.size() / 2;
        Entry midEntry = curr.getEntry(mid);
        Node leftChild = new Node(ORDER, Arrays.copyOfRange(curr.getEntries(), 0, mid),
                Arrays.copyOfRange(curr.getChildren(), 0, mid + 1));
        Node rightChild = new Node(ORDER, Arrays.copyOfRange(curr.getEntries(), mid + 1, curr.size()),
                Arrays.copyOfRange(curr.getChildren(), mid + 1, curr.size() + 1));
        if (curr == root) {
            root = new Node(ORDER, new Entry[]{midEntry}, new Node[]{leftChild, rightChild});
            return;
        }
        Node parent = path.pop();
        Integer pastInsertPos = pastInsertPositions.pop();
        parent.insertEntry(pastInsertPos, midEntry, leftChild, rightChild);
        if (parent.isOverflowed()) {
            BTreeBase.this.percolateUp(parent, path, pastInsertPositions);
        }
    }
protected void percolateUp ( Node curr , Stack < Node > path , Stack < Integer > pastInsertPositions ) { int mid = curr . size ( ) / 2 ; Entry midEntry = curr . getEntry ( mid ) ; Node leftChild = new Node ( ORDER , Arrays . copyOfRange ( curr . getEntries ( ) , 0 , mid ) , Arrays . copyOfRange ( curr . getChildren ( ) , 0 , mid + 1 ) ) ; Node rightChild = new Node ( ORDER , Arrays . copyOfRange ( curr . getEntries ( ) , mid + 1 , curr . size ( ) ) , Arrays . copyOfRange ( curr . getChildren ( ) , mid + 1 , curr . size ( ) + 1 ) ) ; if ( curr == root ) { root = new Node ( ORDER , new Entry [ ] { midEntry } , new Node [ ] { leftChild , rightChild } ) ; return ; } Node parent = path . pop ( ) ; Integer pastInsertPos = pastInsertPositions . pop ( ) ; parent . insertEntry ( pastInsertPos , midEntry , leftChild , rightChild ) ; if ( parent . isOverflowed ( ) ) { BTreeBase . this . percolateUp ( parent , path , pastInsertPositions ) ; } }
Private helper method to percolate up.
Private helper method to percolate up .
// curr is overflowed. // -> Percolate up the middle index entry of curr // Insert into this parent node first, and if the parent node is overflowed, keep percolating up