btree.java

java版b树源码

/*
 * Node.java
 *
 * Created on 2006年11月18日, 上午11:09
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package btree;

import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.RandomAccessFile;

/**
 * 用来作为数据库的索引的核心类
 * @author Andy
 */
public class BTree {
    private int flag; /* 节点增减标志 */
    private int btreeLevel = 0; /* 多路树的高度 */
    private int btreeCount = 0; /* 多路树的键总数 */
    private int nodeSum = 0;  /* 多路树的节点总数 */
    private int level; /* 当前访问的节点所处的高度 */
    private Node newTree; /* 在节点分割的时候指向新建的节点 */
    
    private long insValue; /* 与要插的键相对应的值 */
    private long insKey; /* 要插入的键 */
    
    private NodeOperator file;/*文件操作类*/
    
    public BTree(String idxFile) throws  IOException {
        try {
            file=new NodeOperator(idxFile);
        } catch (FileNotFoundException ex) {
            ex.printStackTrace();
        }
    }
    
    /**
     * 搜索树中的节点
     * @param key 要搜索的键值
     * @param t 要搜索的起始点
     * @return 返回结果和所在节点的位置
     */
    public Result search(long key,Node t) throws IOException {
        int i,j,m;
        level=btreeLevel-1;
        while (level >= 0){
            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 ]){
                Result r=new Result();
                r.btreeDisp = i;
                r.resultNode=t;
                return r;
            }
            if (key > t.keys[ i ]) /* i == t.numKeys-1 时有可能出现 */
                i++;
            long pos = t.childrenPointers [i];
            t=file.loadNode(pos);
            level--;
        }
        return null;
    }
    /**
     * 插入一个节点
     * @param key 要插入的键值
     * @param val 插入的值
     * @param t 要插入的位置
     * @return 返回插入后的根节点
     */
    public Node insert(long key,long val,Node t) throws IOException, KeyExistsException {
        insValue=val;
        
        level=btreeLevel;
        internalInsert(key, t);
        if (flag == 1)  /* 根节点满之后，它被分割成两个半满节点 */
            t=newRoot(t);    /* 树的高度增加 */
        return t;
    }
    
    private void internalInsert(long key,Node t) throws IOException, KeyExistsException {
        int i,j,m;
        
        level--;
        if (level < 0){ /* 到达了树的底部: 指出要做的插入 */
            newTree = null; /* 这个键没有对应的子树 */
            insKey = key; /* 导致底层的叶子节点增加键值+空子树对 */
            btreeCount++;
            flag = 1; /* 指示上层节点把返回的键插入其中 */
            return;
        }
        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 ]) {
            //Error(1,key); /* 键已经在树中 */
            flag = 0;
            throw new KeyExistsException();
//            flag = 0;
//            return;
        }
        if (key > t.keys[ i ]) /* i == t.numKeys-1 时有可能出现 */
            i++;
        Node n=file.loadNode( t.childrenPointers[ i ]);
        internalInsert(key,n);
        
        if (flag == 0)
            return;
        /* 有新键要插入到当前节点中 */
        if (t.numKeys < 2*Node.MIN_KEY_AMOUNT) {/* 当前节点未满 */
            insInNode(t, i); /* 把键值+子树对插入当前节点中 */
            flag = 0; /* 指示上层节点没有需要插入的键值+子树，插入过程结束 */
        } else /* 当前节点已满，则分割这个页面并把键值+子树对插入当前节点中 */
            splitNode(t, i); /* 继续指示上层节点把返回的键值+子树插入其中 */
    }
    
    private void insInNode(Node t, int d) throws IOException {
        int i;
        /* 把所有大于要插入的键值的键和对应的右子树右移 */
        for(i = t.numKeys; i > d; i--){
            t.keys[ i ] = t.keys[i-1];
            t.valuePointers[ i ] = t.valuePointers[i-1];
            t.childrenPointers[i+1] = t.childrenPointers[ i ];
        }
        /* 插入键和右子树 */
        t.keys[ i ] = insKey;
        if(newTree!=null)
            t.childrenPointers[i+1] = newTree.pointer;
        t.valuePointers[ i ] = insValue;
        t.numKeys++;
        file.writeNode(t);
    }
    
    private void splitNode(Node t, int d) throws IOException {
        int i,j;
        Node temp;
        long tempK;
        long tempV;
        /* 建立新节点 */
        temp = new Node();
        temp.pointer=file.getAvailableFilePointer();
    /*
     *   +---+--------+-----+-----+--------+-----+
     *   | 0 | ...... |  M  | M+1 | ...... |2*M-1|
     *   +---+--------+-----+-----+--------+-----+
     *   |<-      M+1     ->|<-        M-1     ->|
     */
        if (d > Node.MIN_KEY_AMOUNT) { /* 要插入当前节点的右半部分 */
            /* 要插入当前节点的右半部分 */
        /* 把从 2*M-1 到 M+1 的 M-1 个键值+子树对转移到新节点中,
         * 并且为要插入的键值+子树空出位置 */
            for(i=2*Node.MIN_KEY_AMOUNT-1,j=Node.MIN_KEY_AMOUNT-1; i>=d; i--,j--) {
                temp.keys[j] = t.keys[ i ];
                temp.valuePointers[j] = t.valuePointers[ i ];
                temp.childrenPointers[j+1] = t.childrenPointers[i+1];
            }
            for(i=d-1,j=d-Node.MIN_KEY_AMOUNT-2; j>=0; i--,j--) {
                temp.keys[j] = t.keys[ i ];
                temp.valuePointers[j] = t.valuePointers[ i ];
                temp.childrenPointers[j+1] = t.childrenPointers[i+1];
            }
            /* 把节点的最右子树转移成新节点的最左子树 */
            temp.childrenPointers[0] = t.childrenPointers[Node.MIN_KEY_AMOUNT+1];
            /* 在新节点中插入键和右子树 */
            temp.keys[d-Node.MIN_KEY_AMOUNT-1] = insKey;
            if(newTree!=null)
                temp.childrenPointers[d-Node.MIN_KEY_AMOUNT] = newTree.pointer;
            temp.valuePointers[d-Node.MIN_KEY_AMOUNT-1] = insValue;
            /* 设置要插入上层节点的键和值 */
            insKey = t.keys[Node.MIN_KEY_AMOUNT];
            insValue = t.valuePointers[Node.MIN_KEY_AMOUNT];
            
        } else {
            /* d <= M */
            /* 把从 2*M-1 到 M 的 M 个键值+子树对转移到新节点中 */
            for(i=2*Node.MIN_KEY_AMOUNT-1,j=Node.MIN_KEY_AMOUNT-1; j>=0; i--,j--) {
                temp.keys[j] = t.keys[ i ];
                temp.valuePointers[j] = t.valuePointers[ i ];
                temp.childrenPointers[j+1] = t.childrenPointers[i+1];
            }
            if (d == Node.MIN_KEY_AMOUNT) /* 要插入当前节点的正中间 */
            {
                /* 把要插入的子树作为新节点的最左子树 */
                if(newTree!=null)
                    temp.childrenPointers[0] = newTree.pointer;
            }
            /* 直接把要插入的键和值返回给上层节点 */
            else { /* (d<Node.MIN_KEY_AMOUNT) 要插入当前节点的左半部分 */
                /* 把节点当前的最右子树转移成新节点的最左子树 */
                temp.childrenPointers[0] = t.childrenPointers[Node.MIN_KEY_AMOUNT];
                /* 保存要插入上层节点的键和值 */
                tempK = t.keys[Node.MIN_KEY_AMOUNT-1];
                tempV = t.valuePointers[Node.MIN_KEY_AMOUNT-1];
                /* 把所有大于要插入的键值的键和对应的右子树右移 */
                for(i=Node.MIN_KEY_AMOUNT-1; i>d; i--) {
                    t.keys[ i ] = t.keys[i-1];
                    t.valuePointers[ i ] = t.valuePointers[i-1];
                    t.childrenPointers[i+1] = t.childrenPointers[ i ];
                }
                /* 在节点中插入键和右子树 */
                t.keys[d] = insKey;
                if(newTree!=null)
                    t.childrenPointers[d+1] = newTree.pointer;
                t.valuePointers[d] = insValue;
                /* 设置要插入上层节点的键和值 */
                insKey = tempK;
                insValue = tempV;
            }
        }
        t.numKeys =Node.MIN_KEY_AMOUNT;
        temp.numKeys = Node.MIN_KEY_AMOUNT;
        file.writeNode(t);
        file.writeNode(temp);
        newTree = temp;
        nodeSum++;
    }
    
    private Node newRoot(Node t) throws IOException {
        Node temp=new Node();
        temp.numKeys = 1;
        temp.childrenPointers[0] = t.pointer;
        
        if(newTree!=null)
            temp.childrenPointers[1] = newTree.pointer;
        
        temp.keys[0] = insKey;
        temp.valuePointers[0] = insValue;
        temp.pointer=file.getAvailableFilePointer();