bplustreefactory.java

B＋树实现源码

package bplustree;

import java.util.*;
import com.xuedi.IO.*;
import com.xuedi.util.RondamStringCreator;

import java.io.*;

public class BPlusTreeFactory {

  Frame1 frame;
  HashSet[] hs;
  ObjectFile of;
  //保存每个节点的健-指针对的数量
  int amountOfKeys;
  //树的根节点
  Node root;

  public BPlusTreeFactory(Frame1 frame,HashSet[] hs,ObjectFile of,int nodeCap) {
    this.frame = frame;
    this.hs = hs;
    this.of = of;
    this.amountOfKeys = nodeCap;
    root = new Node(nodeCap);
  }

  public Node newInstance()
  {
    //指向文件的指针
    long pointer;

    frame.jTextArea1.append("\n正在生成B+树...");

    for(int i = 0; i < hs.length; i++)
    {
      Iterator itor = hs[i].iterator();
      long temp;
      while(itor.hasNext())
      {
        try{

          temp = ( (Long) itor.next()).longValue();
          //得到新生的对象在文件中的指针
          pointer = of.writeObject(new StudentInfo(temp,RondamStringCreator.rondamString()));

          //将新的键-指针对插入
          insertNewKey(temp,pointer);

        }catch(IOException ioe)
        {
          frame.FileNotCreateException();
        }
      }
    }

    frame.jTextArea1.append("\n成功正在生成B+树并将文件写入到磁盘！");
    return root;
  }

  //在树中插入新的健--指针对
  private void insertNewKey(long key,long pointer)
  {
    //找到合适的叶子节点
    Node rightLeaf = searchForRightNode(key,root);
    if( !isFull(rightLeaf) )
      insertToLeaf(key,pointer,rightLeaf);
    else{
      seperateLeafNode(rightLeaf,key,pointer);
    }

  }

  //给内部节点中的自己点重新定向自己的父亲
  private void pointerRedirect(Node node)
  {
    for(int i = 0; i <= node.keyAmount; i++)
    {
      ((Node)node.pointer[i]).parent = node;
    }
  }

  //分裂中间结点//////////////////////////////////////////有问题就出在这个函数里!!!!!!!!
  private void InnerNodeOperation(Node upperNode,long key,Node lowerNode)
  {
    //若还有空间就直接插入
    if(upperNode.keyAmount < this.amountOfKeys)
    {
      insertToInnerNode(key,upperNode,lowerNode);
      lowerNode.parent = upperNode;
      pointerRedirect(upperNode);
      upperNode.keyAmount++;
      return;
    }
    //没有空间就必须分裂
    //生成新节点，它是newNode的兄弟，在old的右边
    Node newNode = new Node(this.amountOfKeys);

    //(n+1)/2取上界
    int oldNodePointerSize = (int)com.xuedi.maths.NumericalBound.getBound(0,(float)(this.amountOfKeys+1)/2);
    //n/2取上界
    int oldNodeKeySize     = (int)com.xuedi.maths.NumericalBound.getBound(0,(float)(this.amountOfKeys+1)/2);
    int newNodeKeySize     = (int)com.xuedi.maths.NumericalBound.getBound(1,(float)(this.amountOfKeys)/2);

    //将(n+1)/2取上界个指针留在old中，其余移动到新节点中
    int j = 1;
    for(int i = oldNodePointerSize; i <= amountOfKeys; i++)
    {
      newNode.pointer[j] = upperNode.pointer[i];
      j++;
    }
    newNode.pointer[0] = lowerNode;

    //将后n/2取下届个键值移动到新节点中
    j = 0;
    for(int k = oldNodeKeySize; k <= this.amountOfKeys-1; k++)
    {
      newNode.keys[j] = upperNode.keys[k];
      j++;
    }
    newNode.keyAmount   = newNodeKeySize;
    upperNode.keyAmount = oldNodeKeySize;

    //重定向父节点指针
    pointerRedirect(upperNode);
    pointerRedirect(newNode);

    //进行更改指针///////////////////////////////////////////////////////////////////////////
    if(upperNode.equals(root))
    {
      if( isFull(upperNode) )
      {
        Node newRoot = new Node(this.amountOfKeys);
        newRoot.pointer[0] = upperNode;
        newRoot.pointer[1] = newNode;

        upperNode.parent = newRoot;
        newNode.parent = newRoot;
        newRoot.keyAmount = 1;
        newRoot.keys[0] = key;
        root = newRoot;
      }
    }else
      InnerNodeOperation(upperNode.parent,lowerNode.keys[0],upperNode);
  }

  //将已满的叶节点分裂：返回分裂后的第二个节点，并改变第一个节点的内容
  //注意：这里的pointer是正数，指向文件中的对象的位置
  private Node seperateLeafNode(Node old,long key,long pointer)
  {
      //把要插入的数值插入到源结点使键值达到n+1个
      int position = -1;
      boolean mustMove = false;
      for (int i = 0; i < this.amountOfKeys; i++) {
        position++;
        if (old.keys[i] > key)
        {
          mustMove = true;
          break;
        }
      }

      //进行搬迁动作--指针要比数据多移动一位
      for (int j = this.amountOfKeys - 1; j >= position; j--) {
        old.keys[j + 1] = old.keys[j];
        old.pointer[j+2] = old.pointer[j+1];
      }
      old.pointer[position+1] = old.pointer[position];

      old.keys[position] = key;
      old.pointer[position] = new Long(pointer);
      //插入动作结束

    //先前节点后来因该有(n+1)/2取上界个键－值针对
    int oldNodeSize = (int)com.xuedi.maths.NumericalBound.getBound(0,(float)(this.amountOfKeys+1)/2);

    Node newNode = new Node(amountOfKeys);

    for(int k = oldNodeSize; k <= amountOfKeys; k++)
    {
      newNode.add(old.keys[k],old.pointer[k]);
    }
    old.keyAmount = oldNodeSize;

    //更改指针
    newNode.pointer[this.amountOfKeys] = old.pointer[this.amountOfKeys+1];
    old.pointer[this.amountOfKeys]     = newNode;

    //如果要分裂的是根节点
    if(old.equals(root))
    {
      Node newRoot = new Node(this.amountOfKeys);
      newRoot.parent = null;
      old.parent = newRoot;
      newNode.parent = newRoot;
      root = newRoot;

      root.keyAmount = 1;
      root.keys[0] = newNode.keys[0];
      root.pointer[0] = old;
      root.pointer[1] = newNode;
    }else{
      //递归向上分裂
      InnerNodeOperation(old.parent,newNode.keys[0],newNode);
    }
    return newNode;
  }

  //将键值和指针插入到叶子节点中合适的位置
  //若数组已满返回false///////////////////////////////////////////////////////////////////////////////
  private boolean insertToLeaf(long key,long pointer,Node node)
  {

    //将数据插入到相应的位置
    int position = 0;
    if(node.keyAmount == node.keys.length-1)
      return false;
    else{
      for (int i = 0; i < node.keyAmount; i++) {
        if (node.keys[i] > key)
          break;
        position++;
      }
      if(node.keyAmount <= position)
      {
        node.add(key,new Long(pointer));
      }else{
        //进行搬迁动作
        for (int j = node.keyAmount-1; j >= position; j--) {
          node.keys[j + 1] = node.keys[j];
          node.pointer[j + 1] = node.pointer[j];
        }
        node.keys[position] = key;
        node.pointer[position] = new Long(pointer);
        node.keyAmount++;
      }

      return true;
    }
  }

  //将对应的值插入到内部节点--注意，这里不判断越界的情况
  private void insertToInnerNode(long key,Node upperNode,Node lowerNode)
  {
    int position = 0;
    boolean mustMove = false;
    for (int i = 0; i < upperNode.keyAmount; i++) {
      if (upperNode.keys[i] > key)
      {
        mustMove = true;
        break;
      }
      position++;
    }

      //进行搬迁动作=--有一定的插入策略：
      //指针的插入比数据的插入多出一位
      for (int j = upperNode.keyAmount - 1; j >= position; j--) {
        upperNode.keys[j + 1] = upperNode.keys[j];
        upperNode.pointer[j + 2] = upperNode.pointer[j+1];
      }
      upperNode.keys[position] = key;
      upperNode.pointer[position+1] = (Node)lowerNode;

      return;
  }

  //找到适合插入的节点;currentNode--当前的查找结点
  public Node searchForRightNode(long key,Node currentNode)
  {

    //如果当前节点是叶子的话的话就返回该节点
    //if( isLeaf(currentNode) )
    if( isLeaf(currentNode) )
      return currentNode;
    else{
      for(int i = 0; i < this.amountOfKeys; i++)
      {
        if(key < currentNode.keys[i])//判断是否是第一个值
          return searchForRightNode(key,(Node)currentNode.pointer[i] );
        else if(key >= currentNode.keys[i]){
          if( i == currentNode.keyAmount-1)//如果后面没有值
          {
            //如果key比最后一个键值大,则给出最后一个指针进行递归查询
            return searchForRightNode(key,(Node)currentNode.pointer[currentNode.keyAmount] );
          }else{
            if(key < currentNode.keys[i+1])
              return searchForRightNode(key,(Node)currentNode.pointer[i+1] );
          }
        }
      }

    }
    return null;
  }

  //判断某个结点是否已经装满了
  private boolean isFull(Node node)
  {
    if(node.keyAmount >= this.amountOfKeys)
      return true;
    else
      return false;
  }

  //判断某个节点是否是叶子结点
  private  boolean isLeaf(Node node)
  {
    //int i = 0;
    if(node.keyAmount == 0)
      return true;

    //如果向下的指针是Node型，则肯定不是叶子节点
    if(node.pointer[0] instanceof Node)
      return false;

    return true;
  }

}