frame1.java

B＋树实现源码

package bplustree;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import com.borland.jbcl.layout.*;
import java.util.*;

import com.xuedi.maths.UnduplicateNumbers;
import com.xuedi.IO.ObjectFile;
import com.xuedi.util.*;

import java.io.*;

public class Frame1 extends JFrame {
  //保留一个树
  BTree btree;
  TreePrinter tp;

  JPanel contentPane;
  JLabel jLabel1 = new JLabel();
  JTextField jTextField1 = new JTextField();
  JButton jButton1 = new JButton();
  JButton jButton2 = new JButton();
  JLabel jLabel2 = new JLabel();
  JTextField jTextField2 = new JTextField();
  JLabel jLabel3 = new JLabel();
  JTextField jTextField3 = new JTextField();
  JScrollPane jScrollPane1 = new JScrollPane();
  JLabel jLabel4 = new JLabel();
  JTextField jTextField4 = new JTextField();
  JTextArea jTextArea1 = new JTextArea();
  JLabel jLabel5 = new JLabel();
  JTextField jTextField5 = new JTextField();
  JButton jButton3 = new JButton();
  GridBagLayout gridBagLayout1 = new GridBagLayout();

  //Construct the frame
  public Frame1() {
    enableEvents(AWTEvent.WINDOW_EVENT_MASK);
    try {
      jbInit();
    }
    catch(Exception e) {
      e.printStackTrace();
    }
  }
  //Component initialization
  private void jbInit() throws Exception  {
    contentPane = (JPanel) this.getContentPane();
    jLabel1.setBorder(null);
    jLabel1.setRequestFocusEnabled(true);
    jLabel1.setText("要建立的元组数：");
    contentPane.setLayout(gridBagLayout1);
    this.setSize(new Dimension(529, 398));
    this.setTitle("B+树实现");
    jTextField1.setText("100");
    jButton1.setText("创建");
    jButton1.addActionListener(new Frame1_jButton1_actionAdapter(this));
    jButton2.setText("复位");
    jButton2.addActionListener(new Frame1_jButton2_actionAdapter(this));
    jLabel2.setText("元组数量的取值范围");
    jTextField2.setText("7");
    jLabel3.setText("每个节点能容纳的键的数量");
    jTextField3.setText("2");
    jLabel4.setText("桶的数量");
    jTextField4.setText("1");
    jTextArea1.setDoubleBuffered(true);
    jLabel5.setText("要查找的键值");
    jTextField5.setText("");
    jButton3.setText("开始查找");
    jButton3.addActionListener(new Frame1_jButton3_actionAdapter(this));
    contentPane.add(jButton1,  new GridBagConstraints(2, 0, 1, 1, 0.0, 0.0
            ,GridBagConstraints.CENTER, GridBagConstraints.NONE, new Insets(4, 33, 0, 61), 33, 4));
    contentPane.add(jButton2,  new GridBagConstraints(2, 1, 1, 1, 0.0, 0.0
            ,GridBagConstraints.CENTER, GridBagConstraints.NONE, new Insets(18, 33, 0, 61), 33, 4));
    contentPane.add(jScrollPane1,  new GridBagConstraints(0, 5, 3, 1, 1.0, 1.0
            ,GridBagConstraints.CENTER, GridBagConstraints.BOTH, new Insets(21, 6, 16, 12), 507, 106));
    jScrollPane1.getViewport().add(jTextArea1, null);
    contentPane.add(jTextField1,  new GridBagConstraints(1, 0, 1, 1, 1.0, 0.0
            ,GridBagConstraints.WEST, GridBagConstraints.HORIZONTAL, new Insets(4, 11, 0, 0), 103, 5));
    contentPane.add(jTextField2,  new GridBagConstraints(1, 1, 1, 1, 1.0, 0.0
            ,GridBagConstraints.WEST, GridBagConstraints.HORIZONTAL, new Insets(19, 11, 0, 0), 109, 5));
    contentPane.add(jTextField3,  new GridBagConstraints(1, 2, 1, 1, 1.0, 0.0
            ,GridBagConstraints.WEST, GridBagConstraints.HORIZONTAL, new Insets(24, 11, 0, 0), 121, 5));
    contentPane.add(jTextField4,  new GridBagConstraints(1, 3, 1, 1, 1.0, 0.0
            ,GridBagConstraints.WEST, GridBagConstraints.HORIZONTAL, new Insets(23, 11, 0, 0), 121, 5));
    contentPane.add(jTextField5,  new GridBagConstraints(1, 4, 1, 1, 1.0, 0.0
            ,GridBagConstraints.WEST, GridBagConstraints.HORIZONTAL, new Insets(23, 11, 0, 0), 139, 5));
    contentPane.add(jButton3,  new GridBagConstraints(2, 2, 1, 1, 0.0, 0.0
            ,GridBagConstraints.CENTER, GridBagConstraints.NONE, new Insets(21, 33, 0, 61), 11, 4));
    contentPane.add(jLabel2,  new GridBagConstraints(0, 0, 1, 1, 0.0, 0.0
            ,GridBagConstraints.WEST, GridBagConstraints.NONE, new Insets(4, 25, 0, 28), 37, 12));
    contentPane.add(jLabel5,  new GridBagConstraints(0, 4, 1, 1, 0.0, 0.0
            ,GridBagConstraints.WEST, GridBagConstraints.NONE, new Insets(23, 25, 0, 0), 98, 14));
    contentPane.add(jLabel4,  new GridBagConstraints(0, 3, 1, 1, 0.0, 0.0
            ,GridBagConstraints.WEST, GridBagConstraints.NONE, new Insets(22, 25, 0, 28), 92, 12));
    contentPane.add(jLabel3,  new GridBagConstraints(0, 2, 1, 1, 0.0, 0.0
            ,GridBagConstraints.WEST, GridBagConstraints.NONE, new Insets(22, 25, 0, 28), 4, 12));
    contentPane.add(jLabel1,  new GridBagConstraints(0, 1, 1, 1, 0.0, 0.0
            ,GridBagConstraints.WEST, GridBagConstraints.NONE, new Insets(17, 25, 0, 28), 48, 12));
  }
  //Overridden so we can exit when window is closed
  protected void processWindowEvent(WindowEvent e) {
    super.processWindowEvent(e);
    if (e.getID() == WindowEvent.WINDOW_CLOSING) {
      System.exit(0);
    }
  }
  //清理对话框的全部内容
  void jButton2_actionPerformed(ActionEvent e) {
    this.jTextField1.setText(""+100000);
    this.jTextField2.setText(""+10000);
    this.jTextField3.setText(""+150);
    this.jTextField4.setText(""+100);
    this.jTextField4.setText("");
    this.jTextArea1.setText("");
    this.btree = null;
    this.tp = null;
  }
  //进行一些错误警告处理
  public void FileNotCreateException()
  {
    JOptionPane.showMessageDialog(this,"数据文件生成失败","IO Error",0);
  }
  //---------------------------------------------------------------------------
  //进行全部创建工作
  void jButton1_actionPerformed(ActionEvent e) {
    long range = Long.parseLong(this.jTextField1.getText().trim());
    long amount= Long.parseLong(this.jTextField2.getText().trim());
    //一个节点的容量
    int  nodeCap= Integer.parseInt(this.jTextField3.getText().trim());
    int  bucketAmount = Integer.parseInt(this.jTextField4.getText().trim());

    ObjectFile of = null;
    HashSet[] hs = null;
    //生成不重复的数据存放在hs中
    try{
      of = new ObjectFile("Student.inf");

      this.jTextArea1.append("正在生成不重复的" + amount + "个数据...");
      hs = UnduplicateNumbers.getUnduplicateNumbers(range, amount, bucketAmount);
      this.jTextArea1.append("\n数字生成完毕!");

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

    //生成B树
    this.btree = new BTree(nodeCap);
    //指向文件的指针
    long pointer;
    this.jTextArea1.append("\n正在生成B+树...");
    for(int i = 0; i < hs.length; i++)
    {
      Iterator itor = hs[i].iterator();
      long temp;
      long counter = 0;
      while(itor.hasNext())
      {
        counter++;
        try{
          temp = ( (Long) itor.next()).longValue();
          //得到新生的对象在文件中的指针
          pointer = of.writeObject(new StudentInfo(temp,RondamStringCreator.rondamString()));
          //将新的键-指针对插入
          btree.insert(temp,new Long(pointer) );

        }catch(IOException ioe)
        {
          this.FileNotCreateException();
        }
      }
    }
    this.jTextArea1.append("\n成功正在生成B+树并将文件写入到磁盘!");

    //BPlusTreeFactory bFactory = new BPlusTreeFactory(this,hs,of,nodeCap);
    //Node bTree = bFactory.newInstance();
    this.jTextArea1.append("\n根含有"+ btree.root.keyAmount+"个元素!");

    this.jTextArea1.append("\n开始打印生成的树(在控制台显示)...");
    TreePrinter tp = new TreePrinter(this,btree.root);
    tp.printAllTree();
    this.jTextArea1.append("\n打印完成!");
    this.jTextArea1.append("\n树共有"+(tp.layers+1)+"层!");
  }
  //////////////////////////////////////////////////////////////////////////////
  void jButton3_actionPerformed(ActionEvent e) {///////////////////////////////
    long key = Long.parseLong(this.jTextField5.getText().trim());
    this.jTextArea1.append("\n开始打印查找路径...\n");
    Node result = search(key,this.btree.root);
    for(int i = 0; i < result.keyAmount; i++)
    {
      if( key == result.keys[i] )
      {
        this.jTextArea1.append("\n该数据在这棵树中!");
        return;
      }
    }
    this.jTextArea1.append("\n该数据不在这棵树中!");
  }

  //打印一个结点的内容
  private void printNode(Node node)
  {
    for(int i = 0; i < node.keyAmount; i++)
    {
      this.jTextArea1.append(node.keys[i]+",");
      //System.out.print(node.keys[i]+",");
    }
    this.jTextArea1.append("-->");
  }
  //带有打印的查找函数
  public Node search(long key,Node curNode)
  {
    printNode(curNode);
    if (isLeaf(curNode))
    {
      return curNode;
    }

    for (int i = 0; i < this.btree.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  boolean isLeaf(Node node)
 {
   //int i = 0;
   if(node.keyAmount == 0)
     return true;

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

   return true;
 }

  //---------------------------------------------------------------------------
}

class Frame1_jButton2_actionAdapter implements java.awt.event.ActionListener {
  Frame1 adaptee;

  Frame1_jButton2_actionAdapter(Frame1 adaptee) {
    this.adaptee = adaptee;
  }
  public void actionPerformed(ActionEvent e) {
    adaptee.jButton2_actionPerformed(e);
  }
}

class Frame1_jButton1_actionAdapter implements java.awt.event.ActionListener {
  Frame1 adaptee;

  Frame1_jButton1_actionAdapter(Frame1 adaptee) {
    this.adaptee = adaptee;
  }
  public void actionPerformed(ActionEvent e) {
    adaptee.jButton1_actionPerformed(e);
  }
}

class Frame1_jButton3_actionAdapter implements java.awt.event.ActionListener {
  Frame1 adaptee;

  Frame1_jButton3_actionAdapter(Frame1 adaptee) {
    this.adaptee = adaptee;
  }
  public void actionPerformed(ActionEvent e) {
    adaptee.jButton3_actionPerformed(e);
  }
}