indexblock.java

一个用java编写的从底层开始设计的小型数据库管理系统

                }
                offset += keyByteAndNullFlagLength; 
            }
            break;
        default:
            System.out.println("illegal argument");
            break;
        }
	}
    
    
    /**
     * 下面是B+树的操作
     * 
     * 根节点分裂时用来初始化
     * @param key
     * @param lessPointer
     * @param greaterPointer
     */
    public void initializeRootNode(DataItem key,
            int lessPointer, int greaterPointer) {
        keyArray[0] = key;
        pointerArray[0] = lessPointer;
        pointerArray[1] = greaterPointer;
        keyNum++;
    }
    
    /**
     * 查找叶节点中相等的值的位置
     * @param key
     * @return -1 如果不存在，在pointerArray中的位置
     */
    public int findLeafItem(DataItem key) {
        for (int j = 0; j < keyNum; j++) {
            if (keyArray[j].equals(key))
                return j;
        }
        return -1;
    }
    
    /**
     * 查找内部节点中下一个节点的位置
     * @param key
     * @return 在pointerArray中的位置
     */
    public int locateInternalItem(DataItem key) {
        boolean processNull = false;
        int d = -1;
        for (int j = 0; j < keyNum; j++) {
            if (processNull) {
                if (keyArray[j] != null) {
                    if (keyArray[j].compareTo(key) > 0)
                        return d;
                    else
                        processNull = false;
                }
            }
            else if (keyArray[j] == null) {
                d = j;
                processNull = true;
            }
            else if (keyArray[j].compareTo(key) > 0)
                return j;
        }
        return processNull ? d : keyNum;
    }
    
    /**
     * 查找内部节点中下一个节点的位置
     * @param pointer
     * @return 在pointerArray中的位置
     */
    public int locateInternalPointer(int pointer) {
        for (int j = 0; j <= keyNum; j++) {
            if (pointerArray[j] == pointer)
                return j;
        }
        return -1;
    }
    
    /**
     * 调用时不论是否满，之后再检查
     * 叶节点中指向下一节点的指针始终在pointerArray的最后一个位置
     * @param newItem
     * @return
     */
    public void insertLeafItem(DataItem newItem, int pointer) {
        keyNum++; // 节点数加一
        for (int j = keyNum - 2; j > -1; j--) {
            if (keyArray[j].compareTo(newItem) > 0) {
                keyArray[j + 1] = keyArray[j];
                pointerArray[j + 1] = pointerArray[j];
            }
            else {
                keyArray[j + 1] = newItem;
                pointerArray[j + 1] = pointer;
                return;
            }
        }
        keyArray[0] = newItem;
        pointerArray[0] = pointer;
    }
    
    /**
     * 调用时不论是否满，之后再检查
     * 内部节点的第一个指针始终不变
     * @param newItem
     * @param pointer
     * @param loc 插入位置，之前已经确定
     */
    public void insertInternalItem(DataItem newItem, int pointer, int loc) {
        keyNum++; // 节点数加一
        for (int j = keyNum - 2; j >= loc; j--) {
            keyArray[j + 1] = keyArray[j];
            pointerArray[j + 2] = pointerArray[j + 1];
        }
        keyArray[loc] = newItem;
        pointerArray[loc + 1] = pointer;
    }
    
    /**
     * 删除一个键
     * @param item
     * @return 键对应的指针, -1 没有这个键
     */
    public int deleteItem(DataItem item) {
        int j = 0, loc = -1;
        for (; j < keyNum; j++) {
            if (keyArray[j].equals(item)) {
                loc = pointerArray[j];
                keyArray[j] = null;
                keyNum--;
                break;
            }
        }
        for (; j < keyNum; j++) {
            pointerArray[j] = pointerArray[j + 1];
            keyArray[j] = keyArray[j + 1];
        }
        if (loc != -1) {
            keyArray[j] = null;
        }
        return loc;
    }
    
    /**
     * 拆分叶节点
     * @param newNode
     * @param newNodePointer 新节点的指针,用于顺序指针
     * @return null 新节点中无新键
     */
    public DataItem splitLeafNode(IndexBlock newNode, int newNodePointer) {
        // 调整键数
        newNode.keyNum = (short)(keyNum / 2);
        keyNum = (short)((keyNum + 1) / 2);
        
        // 复制键和指针
        System.arraycopy(keyArray, keyNum,
                newNode.keyArray, 0, newNode.keyNum);
        Arrays.fill(keyArray, keyNum, keyArray.length, null);
        System.arraycopy(pointerArray, keyNum,
                newNode.pointerArray, 0, newNode.keyNum);
        
        // 将叶节点的顺序指针放在pointerArray的最后一个位置
        int nextNodePointer = pointerArray.length - 1;
        newNode.pointerArray[nextNodePointer] = pointerArray[nextNodePointer];
        
        // 将顺序指针指向newNode
        pointerArray[nextNodePointer] = newNodePointer;
        
        // 寻找新键
        DataItem lastItem = keyArray[keyNum - 1];
        for (int i = 0; i < newNode.keyNum; i++) {
            if ( ! newNode.keyArray[i].equals(lastItem))
                return newNode.keyArray[i];
        }
        return null;
    }
    
    /**
     * 拆分内部节点
     * @param newNode
     * @return 拆分出的独立键值
     */
    public DataItem splitInternalNode(IndexBlock newNode) {
        // 复制键和指针
        System.arraycopy(keyArray, (keyNum + 2) / 2,
                newNode.keyArray, 0, (keyNum - 1) / 2);
        System.arraycopy(pointerArray, (keyNum + 2) / 2,
                newNode.pointerArray, 0, (keyNum + 1) / 2);
        
        // 调整键数
        newNode.keyNum = (short)((keyNum - 1) / 2);
        keyNum = (short)(keyNum / 2);
        
        // 独立节电加入上层节点,寻找非null新键
        DataItem splitKey = keyArray[keyNum];
        Arrays.fill(keyArray, keyNum, keyArray.length, null);
        
        // 保证非null
        if (splitKey == null) {
            for (int i = 0; i < newNode.keyNum; i++) {
                if (newNode.keyArray[i] != null)
                    return newNode.keyArray[i];
            }
        }
        return splitKey;
    }
    
    /**
     * @return 顺序指针,只在叶节点中有意义
     */
    public int nextLeafNode() {
        return pointerArray[pointerArray.length - 1];
    }
    
    /**
     * 超出B+ tree定义
     * @return
     */
    public boolean isBeyondSpace() {
        return keyNum == keyArray.length;
    }
    
    /**
     * 只在叶节点中用,全部键小于等于key
     * 必须keyNum != 0
     * @param key
     * @return
     */
    public boolean isTotalLessOrEqual(DataItem key) {
        return keyArray[keyNum - 1].compareTo(key) <= 0;
    }
    
    /**
     * 只在叶节点中用,存在键小于key
     * 必须keyNum != 0
     * @param key
     * @return
     */
    public boolean hasLessOrEqual(DataItem key) {
        return keyArray[0].compareTo(key) <= 0;
    }
    
    public int getItemNum() {
        return keyNum;
    }
    
    public int getPointerAt(int num) {
        return pointerArray[num];
    }
    
    public void setKeyAt(int num, DataItem key) {
        keyArray[num] = key;
    }
    
    public DataItem getKeyAt(int num) {
        return keyArray[num];
    }
    
    public DataItem getRepresentKey(DataItem old) {
        if (old == null) {
            return null;
        }
        
        for (int j = 0; j < keyNum; j++) {
            if (keyArray[j] != null
                    && keyArray[j].compareTo(old) >= 0)
                return keyArray[j];
        }
        return null;
    }
    
    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append(" keyNum = " + keyNum + " : ");
        for (int j = 0; j < keyNum; j++)
            sb.append(keyArray[j]);
        return sb.toString();
    }
}