btree.java

java版b树源码

        file.writeNode(temp);
        btreeLevel++;
        nodeSum++;
        return(temp);
    }
    /**
     * 删除一个键
     * @param key 要删除的键值
     * @param t 从哪棵树删
     * @return 返回删除之后的根节点
     */
    public Node delete(long key, Node t) throws IOException, KeyNotFoundException {
        level=btreeLevel;
        internalDelete(key, t);
        if (t.numKeys == 0)
    /* 根节点的子节点合并导致根节点键的数目随之减少，
     * 当根节点中没有键的时候，只有它的最左子树可能非空 */
            t=freeRoot(t);
        return t;
    }
    
    void internalDelete(long key, Node t) throws IOException, KeyNotFoundException {
        
        int i,j,m;
        Node l,r;
        int lvl;
        
        level--;
        if (level < 0) {
            //Error(0,key); /* 在整个树中未找到要删除的键 */
            flag = 0;
//            return;
            throw new KeyNotFoundException();
        }
        j=t.numKeys-1;
        for(i=0; i<j; ) {
            m=(j+i)/2;
            if (key > t.keys[m])
                i=m+1;
            else
                j=m;
        }
        if (key == t.keys[ i ]) { /* 找到要删除的键 */
            
            if (level == 0) { /* 有子树为空则这个键位于叶子节点 */
                delFromNode(t,i);
                btreeCount--;
                flag = 1;
                /* 指示上层节点本子树的键数量减少 */
                return;
            } else { /* 这个键位于非叶节点 */
                lvl = level-1;
                /* 找到前驱节点 */
                r = file.loadNode(t.childrenPointers[ i ]);
                while (lvl > 0)  {
                    r = file.loadNode(r.childrenPointers[r.numKeys]);
                    lvl--;
                }
                t.keys[ i ]=r.keys[r.numKeys-1];
                t.valuePointers[ i ]=r.valuePointers[r.numKeys-1];
                r.valuePointers[r.numKeys-1]=0;
                key = r.keys[r.numKeys-1];
                file.writeNode(t);
                file.writeNode(r);
            }
        } else if (key > t.keys[ i ]) /* i == t.numKeys-1 时有可能出现 */
            i++;
        internalDelete(key, file.loadNode(t.childrenPointers[ i ]));
        
        /* 调整平衡 */
        if (flag == 0)
            return;
        if ( file.loadNode(t.childrenPointers[ i ]).numKeys < Node.MIN_KEY_AMOUNT) {
            if (i == t.numKeys) /* 在最右子树中发生了删除 */
                i--; /* 调整最右键的左右子树平衡 */
            l =  file.loadNode(t.childrenPointers[ i]);
            r = file.loadNode(t.childrenPointers[ i+1 ]);
            if (r.numKeys > Node.MIN_KEY_AMOUNT)
                moveLeftNode(t,i);
            else if(l.numKeys >  Node.MIN_KEY_AMOUNT)
                moveRightNode(t,i);
            else {
                joinNode(t,i);
                /* 继续指示上层节点本子树的键数量减少 */
                return;
            }
            flag = 0;
            /* 指示上层节点本子树的键数量没有减少，删除过程结束 */
        }
        
    }
    
    private Node freeRoot(Node t) throws IOException {
        Node temp;
        temp = file.loadNode(t.childrenPointers[0]);
        file.deleteNode(t);
        btreeLevel--;
        nodeSum--;
        return temp;
    }
    
    private void delFromNode(Node t, int d) throws IOException {
        int i;
        /* 把所有大于要删除的键值的键左移 */
        for(i=d; i < t.numKeys-1; i++) {
            t.keys[ i ] = t.keys[i+1];
            t.valuePointers[ i ] = t.valuePointers[i+1];
        }
        t.numKeys--;
        file.writeNode(t);
    }
    
    private void moveLeftNode(Node t, int d) throws IOException {
        Node l,r;
        int m; /* 应转移的键的数目 */
        int i,j;
        l = file.loadNode(t.childrenPointers[d]);
        r = file.loadNode(t.childrenPointers[d+1]);
        m = (r.numKeys - l.numKeys)/2;
        
        /* 把这个键下移到它的左子树 */
        l.keys[l.numKeys] = t.keys[d];
        l.valuePointers[l.numKeys] = t.valuePointers[d];
    /* 把右子树的最左子树转移成左子树的最右子树
     * 从右子树向左子树移动 m-1 个键+子树对 */
        for (j=m-2,i=l.numKeys+m-1; j >= 0; j--,i--) {
            l.keys[ i ] = r.keys[ j ];
            l.valuePointers[ i ] = r.valuePointers[ j ];
            l.childrenPointers[ i ] = r.childrenPointers[ j ];
        }
        l.childrenPointers[l.numKeys+m] = r.childrenPointers[m-1];
        /* 把右子树的最左键提升到这个键的位置上 */
        t.keys[d] = r.keys[m-1];
        t.valuePointers[d] = r.valuePointers[m-1];
        /* 把右子树中的所有键值和子树左移 m 个位置 */
        r.childrenPointers[0] = r.childrenPointers[m];
        for (i=0; i<r.numKeys-m; i++) {
            r.keys[ i ] = r.keys[i+m];
            r.valuePointers[ i ] = r.valuePointers[i+m];
            r.childrenPointers[ i ] = r.childrenPointers[i+m];
        }
        r.childrenPointers[r.numKeys-m] = r.childrenPointers[r.numKeys];
        l.numKeys+=m;
        r.numKeys-=m;
        file.writeNode(l);
        file.writeNode(r);
        file.writeNode(t);
    }
    
    private void joinNode(Node t, int d) throws IOException {
        Node l,r;
        int i,j;
        l = file.loadNode(t.childrenPointers[d]);
        r = file.loadNode(t.childrenPointers[d+1]);
        
        l.keys[l.numKeys] = t.keys[d];
        l.valuePointers[l.numKeys] = t.valuePointers[d];
        /* 把右子树中的所有键值和子树转移到左子树 */
        for (j=r.numKeys-1,i=l.numKeys+r.numKeys; j >= 0 ; j--,i--) {
            l.keys[ i ] = r.keys[j];
            l.valuePointers[ i ] = r.valuePointers[j];
            l.childrenPointers[ i ] = r.childrenPointers[j];
        }
        l.childrenPointers[l.numKeys+r.numKeys+1] = r.childrenPointers[r.numKeys];
        l.numKeys += r.numKeys+1;
        /* 释放右子树的节点 */
        file.deleteNode(r);
        /* 把这个键右边的键和对应的右子树左移 */
        for (i=d; i < t.numKeys-1; i++) {
            t.keys[ i ] = t.keys[i+1];
            t.valuePointers[ i ] = t.valuePointers[i+1];
            t.childrenPointers[i+1] = t.childrenPointers[i+2];
        }
        t.numKeys--;
        file.writeNode(t);
        file.writeNode(l);
        nodeSum--;
        
    }
    
    private void moveRightNode(Node t, int d) throws IOException {
        Node l,r;
        int m; /* 应转移的键的数目 */
        int i,j;
        l = file.loadNode(t.childrenPointers[d]);
        r = file.loadNode(t.childrenPointers[d+1]);
        
        m = (l.numKeys - r.numKeys)/2;
        /* 把右子树中的所有键值和子树右移 m 个位置 */
        r.childrenPointers[r.numKeys+m]=r.childrenPointers[r.numKeys];
        for (i=r.numKeys-1; i>=0; i--) {
            r.keys[i+m] = r.keys[ i ];
            r.valuePointers[i+m] = r.valuePointers[ i ];
            r.childrenPointers[i+m] = r.childrenPointers[ i ];
        }
        /* 把这个键下移到它的右子树 */
        r.keys[m-1] = t.keys[d];
        r.valuePointers[m-1] = t.valuePointers[d];
        /* 把左子树的最右子树转移成右子树的最左子树 */
        r.childrenPointers[m-1] = l.childrenPointers[l.numKeys];
        /* 从左子树向右子树移动 m-1 个键+子树对 */
        for (i=l.numKeys-1,j=m-2; j>=0; j--,i--) {
            r.keys[j] = l.keys[ i ];
            r.valuePointers[j] = l.valuePointers[ i ];
            r.childrenPointers[j] = l.childrenPointers[ i ];
        }
        /* 把左子树的最右键提升到这个键的位置上 */
        t.keys[d] = l.keys[ i ];
        t.valuePointers[d] = l.valuePointers[ i ];
        l.numKeys-=m;
        r.numKeys+=m;
        file.writeNode(r);
        file.writeNode(l);
        file.writeNode(t);
    }
    
    /**
     * 关闭树，释放资源
     */
    public void close() throws IOException {
        file.close();
    }
    
    public int height() {
        return btreeLevel;
    }
    
    public int count() {
        return btreeCount;
    }
}