B+树的创建java源码

源码中包含了class NOde，class BTree，class TreePrinter 主要实现了B+树的创建，节点的插入，以及BTree的遍历

import java.util.*;


////// DisposeRoot ///////中的key参数有些问题

public class BTree {
  //用于记录每个节点中的键值数量
  public int keyAmount;
  //树的根节点
  public Node root;

  public BTree（int keyAmount） {
    this.keyAmount = keyAmount;
    this.root = new Node（keyAmount）;
  }



  //在B树中插入叶节点/////////////////////////////////////////////////////////////
  public void insert（long keyobject pointer）
  {
    //找到应该插入的节点，即找到叶子节点
    Node theNode = search（keyroot）;

    //在叶节点中找到空闲空间，有的话就把键放在那里
    if（ !isFull（theNode） ）
    {
      putKeyToNode（keypointertheNode）;
    }else{
      //如果在适当的叶节点没有空间，就把该叶节点分裂成两个，并正确分配键值
      Node newNode = separateLeaf（keypointertheNode）;
      //如果分裂的是根节点，就新建一个新的根节点将新建的节点作为他的根节点
	  //原来的根节点，和分裂的节点分别作为新根节点的左右孩子，此时新根只有一个元素
      if（ isRoot（theNode） ）
      {
        DisposeRoot（theNodenewNodenewNode.keys[0]）;
      }else{
        //将新建立的节点的指针插入到上层节点
        insertToInnerNode（theNode.parentnewNodenewNode.keys[0]）;
      }
    }
  }




  //用于寻找键值key所在的或key应该插入的节点
  //key为键值curNode为当前节点--一般从root节点开始
  public Node search（long keyNode curNode）
  {
    if （isLeaf（curNode））
      return curNode;

    for （int i = 0; i < this.keyAmount; i++）
    {
        if （key < curNode.keys[i]） //判断是否是第一个值
          return search（key （Node） curNode.pointer[i]）;
        else if （key >= curNode.keys[i]） {
          if （i == curNode.keyAmount - 1） //如果后面没有值
          {
            //如果key比最后一个键值大则给出最后一个指针进行递归查询
            return search（key（Node） curNode.pointer[curNode.keyAmount]）;
          }
          else {
            if （key < curNode.keys[i + 1]）
              return search（key （Node） curNode.pointer[i + 1]）;
          }
        }
    }
    //永远也不会到达这里
    return null;
  }




	//把键值放到叶节点中--这个函数不进行越界检查////////////////////////////////////////
  private void putKeyToNode（long keyobject pointerNode theNode）
  {
    int position = getInsertPosition（keytheNode）;
    //进行搬迁动作--------叶节点的搬迁
    if（ isLeaf（theNode） ）
    {
        if（theNode.keyAmount <= position）
        {
           theNode.add（keypointer）;
           return;
        }
        else{
            for （int j = theNode.keyAmount - 1; j >= position; j--） {
              theNode.keys[j + 1] = theNode.keys[j];
              theNode.pointer[j + 1] = theNode.pointer[j];
            }
            theNode.keys[position] = key;
            theNode.pointer[position] = pointer;
        }
     }else{
          //内部节点的搬迁----有一定的插入策略：
          //指针的插入比数据的插入多出一位
          for （int j = theNode.keyAmount - 1; j >= position; j--） {
            theNode.keys[j + 1] = theNode.keys[j];
            theNode.pointer[j + 2] = theNode.pointer[j+1];
          }
          theNode.keys[position] = key;
          theNode.pointer[position+1] = pointer;
        }
    //键值数量加1
    theNode.keyAmount++;
  }



 //将对应的叶节点进行分裂并正确分配键值，返回新建的节点///////////////////////////////
  private Node separateLeaf

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       9016  2011-11-07 20:53  BTree.java

     文件        972  2011-11-07 20:41  Node.java

     文件       1424  2011-11-07 20:21  Test.java

     文件       1623  2011-11-07 11:07  TreePrinter.java

----------- ---------  ---------- -----  ----

                13035                    4