bplustreefactory.java~6~

B＋树实现源码

package bplustree;

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

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) )
      insertToRightPlace(key,pointer,rightLeaf);
    else{
      if( rightLeaf.equals(root) )//如果试图插入键到根节点中且根节点没有空间
      {

      }else//插入的位置不是根节点
      {

      }
    }

  }

  //将已满的叶节点分裂：返回分裂后的第二个节点，并改变第一个节点的内容
  private Node seperateNode(Node old,boolean leaf)
  {
    //先前节点后来因该有(n+1)/2取上界个键－值针对
    int oldNodeSize = (int)com.xuedi.maths.NumericalBound.getBound(0,(this.amountOfKeys+1)/2);

    Node newNode = new Node(amountOfKeys);

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

    return newNode;
  }

  //将键值和指针插入到叶子节点中合适的位置
  private void insertToRightPlace(long key,long pointer,Node node)
  {
    //将数据插入到相应的位置
    int position = com.xuedi.maths.NumDataSequenceInsert.sequenceInsert(node.keys,key,node.keyAmount-1);
    if(position != -1)

    //node.pointer.add(counter,new Long(pointer));
  }

  //找到适合插入的节点;currentNode--当前的查找结点
  public Node searchForRightNode(long key,Node currentNode)
  {
    //如果当前节点是叶子的话的话就返回该节点
    if( isLeaf(currentNode) )
      return currentNode;
    else{
      ListIterator itor = currentNode.keys.listIterator();

      //记录键值(指针)的位置
      int  counter = -1;
      long temp1,temp2;

      while(itor.hasNext())
      {
        counter++;
        temp1 = ( (Long)itor.next() ).longValue();
        if(key < temp1)//判断是否是第一个值
          return searchForRightNode(key,(Node)currentNode.pointer.get(counter) );
        else if(key >= temp1){
          if( !itor.hasNext())//如果后面没有值
          {
            //如果key比最后一个键值大,则给出最后一个指针进行递归查询
            return searchForRightNode(key,(Node)currentNode.pointer.get(this.amountOfKeys) );
          }else{
            temp2 = ( (Long)itor.next() ).longValue();
            if(key < temp2)
              return searchForRightNode(key,(Node)currentNode.pointer.get(counter+1) );
            else
              itor.previous(); //回退一个
          }
        }
      }

    }
    return null;
  }

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

  //判断某个节点是否是叶子结点
  private boolean isLeaf(Node node)
  {
    if(node.keys.size() == 0 || node.pointer.size() == 0)
      return true;

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

    return true;
  }

}