btree.java

用JAVA实现的miniSQL

    		else{
    			if(add>0){
    				if(!N.isleaf){
    					Long Pm = brotherN.address.getLast();
    					Keyword Km_1= brotherN.keyentry.getLast();
    					brotherN.address.removeLast();
    					brotherN.keyentry.removeLast();
    					brotherN.indexno--;
    					N.address.addFirst(Pm);
    					N.keyentry.addFirst(newK);
    					N.indexno++;
    					BtreeNode tempNode = getNode(Pm.longValue());
    					tempNode.parent = N.getAddress();
    					tempNode.updata();
    					parent.keyentry.set(parent.search(newK),Km_1);
    					N.updata();
    					brotherN.updata();
    					parent.updata();
    				}
    				else{
    					Keyword Km_1 = brotherN.keyentry.getLast();
    					Long Pm_1 = brotherN.address.get(brotherN.indexno-1);
    					brotherN.address.remove(brotherN.indexno-1);
    					brotherN.keyentry.removeLast();
    					brotherN.indexno--;
    				    N.address.addFirst(Pm_1);
    				    N.keyentry.addFirst(Km_1);
    				    N.indexno++;
    				    parent.keyentry.set(parent.search(newK),Km_1);
    				    parent.updata();
    				    N.updata();
    				    brotherN.updata();
    				}
    			}
    			else{
    				if(!N.isleaf){
    					Long Pm = brotherN.address.getFirst();
    					Keyword Km_1= brotherN.keyentry.getFirst();
    					brotherN.address.removeFirst();
    					brotherN.keyentry.removeFirst();
    					brotherN.indexno--;
    					N.address.addLast(Pm);
    					N.keyentry.addLast(newK);
    					N.indexno++;
    					BtreeNode tempNode = getNode(Pm.longValue());
    					tempNode.parent = N.getAddress();
    					tempNode.updata();
    					parent.keyentry.set(parent.search(newK),Km_1);
    					N.updata();
    					brotherN.updata();
    					parent.updata();
    				}
    				else{
    					Keyword Km_1 = brotherN.keyentry.getFirst();
    					Long Pm_1 = brotherN.address.getFirst();
    					brotherN.address.removeFirst();
    					brotherN.keyentry.removeFirst();
    					brotherN.indexno--;
    				    N.address.add(N.indexno, Pm_1);
    				    N.keyentry.addLast(Km_1);
    				    N.indexno++;
    				    parent.keyentry.set(parent.search(newK),brotherN.keyentry.getFirst());
    				    parent.updata();
    				    N.updata();
    				    brotherN.updata();
    				}
    			}
    		}
    	}
    }
    public BtreeNode insertsearch(Keyword key) {
    	BtreeNode b = null;
    	try{
    	    buffer.getBlock(new File(index),(rootpos-1024)/4096 , 1024);
    	    b = new BtreeNode(buffer.list.getFirst());
    	    long pos = 0;
            while(!b.isleaf){
        	    pos = b.address.get(b.searchchild(key)).longValue();
        	    buffer.getBlock(new File(index),(pos-1024)/4096 , 1024);
    	        b = new BtreeNode(buffer.list.getFirst());
            }
        }catch(Exception e){
        	System.out.println("搜索错误");
        }
        return b;
    }
    public BtreeNode getNode(long address){
    	BtreeNode b = null;
    	try{
    	    buffer.getBlock(new File(index),(address-1024)/4096 , 1024);
    	    b = new BtreeNode(buffer.list.getFirst());
    	}catch(Exception e){
    		System.out.println("取块错误");
    	}
    	return b;
    }
    public BtreeNode newNode(boolean isleaf, int type, int length, long parent){
    	byte[] temp = new byte[4096];
    	Block bl = new Block(index, (newpos-1024)/4096, 1024 , temp);
    	buffer.list.addFirst(bl);
    	BtreeNode newnode= new BtreeNode(isleaf, type, length, parent, bl);
    	nodenumber++;
    	newpos=newpos+4096;
    	if(newpos == 5120)
    		newnode.address.add(new Long(-1));
    	newnode.updata();
    	return newnode;
    }
    public void updata(){
    	try{
    	    RandomAccessFile indexfile = new RandomAccessFile(new File(index),"rws");
    	    indexfile.writeLong(total);
    	    indexfile.write(type);
    	    indexfile.write(length/2);
    	    indexfile.writeLong(rootpos);
    	    indexfile.writeInt(heigth);
    	    indexfile.writeLong(nodenumber);
    	    indexfile.writeLong(newpos);
    	    indexfile.close();
    	}catch(Exception e){
    		System.out.println("B+tree升级失败");
    	}
    }
    public long search(Keyword K){
    	BtreeNode b = insertsearch(K);
    	long a;
    	if(b==null)
    		return -1;
    	if(b.search(K)>=0)
    	   a = b.address.get(b.search(K)).longValue();
    	else
    	   a = -1;
    	return a;
    }
    public LinkedList<Long> searchbetween(Keyword K1, Keyword K2){
    	if(K1.compareTo(K2)>0){
    		Keyword T=K1;
    		K1 = K2;
    		K2 = T;
    	}
    	BtreeNode b1 = insertsearch(K1);
    	BtreeNode b2 = insertsearch(K2);
    	int p1 = b1.searchlarge(K1);
    	int p2 = b2.searchless(K2);
    	LinkedList<Long> list = new LinkedList<Long>();
    	int p = p1;
        while(b1.blk.blockno!=b2.blk.blockno){
    	    for(int i=p;i<b1.indexno;i++)
    	    	list.add(b1.address.get(i));
    	    buffer.getBlock(new File(index), (b1.address.getLast().longValue()-1024)/4096, 1024);
    	    b1 = new BtreeNode(buffer.list.getFirst());
    	    p=0;
        }
        for(int i=p;i<p2;i++)
        	list.add(b2.address.get(i));
        return list;
    }
    public LinkedList<Long> searchless(Keyword K){
    	BtreeNode b = null;
    	try{
    	    buffer.getBlock(new File(index),(rootpos-1024)/4096 , 1024);
    	    b = new BtreeNode(buffer.list.getFirst());
    	    long pos = 0;
            while(!b.isleaf){
        	    pos = b.address.getFirst().longValue();
        	    buffer.getBlock(new File(index),(pos-1024)/4096 , 1024);
    	        b = new BtreeNode(buffer.list.getFirst());
            }
        }catch(Exception e){
        	System.out.println("搜索错误");
        }
        LinkedList<Long> list = new LinkedList<Long>();
        BtreeNode b2 = insertsearch(K);
        int p2= b2.searchless(K);
        int p = 0;
        while(b.blk.blockno!=b2.blk.blockno){
    	    for(int i=p;i<b.indexno;i++)
    	    	list.add(b.address.get(i));
    	    buffer.getBlock(new File(index), (b.address.getLast().longValue()-1024)/4096, 1024);
    	    b = new BtreeNode(buffer.list.getFirst());
    	    p=0;
        }
        for(int i=p;i<p2;i++)
        	list.add(b2.address.get(i));
        return list;
    }
    public LinkedList<Long> searchlarge(Keyword K){
    	BtreeNode b = null;
    	try{
    	    buffer.getBlock(new File(index),(rootpos-1024)/4096 , 1024);
    	    b = new BtreeNode(buffer.list.getFirst());
    	    long pos = 0;
            while(!b.isleaf){
        	    pos = b.address.getLast().longValue();
        	    buffer.getBlock(new File(index),(pos-1024)/4096 , 1024);
    	        b = new BtreeNode(buffer.list.getFirst());
            }
        }catch(Exception e){
        	System.out.println("搜索错误");
        }
        LinkedList<Long> list = new LinkedList<Long>();
        BtreeNode b1 = insertsearch(K);
        int p2= b1.searchlarge(K);
        int p = p2;
        while(b.blk.blockno!=b1.blk.blockno){
    	    for(int i=p;i<b1.indexno;i++)
    	    	list.add(b1.address.get(i));
    	    buffer.getBlock(new File(index), (b1.address.getLast().longValue()-1024)/4096, 1024);
    	    b1 = new BtreeNode(buffer.list.getFirst());
    	    p=0;
        }
        for(int i=p;i<b.indexno;i++)
        	list.add(b.address.get(i));
        return list;
    }
    public long getMinAddress(){
    	BtreeNode b = null;
    	try{
    	    buffer.getBlock(new File(index),(rootpos-1024)/4096 , 1024);
    	    b = new BtreeNode(buffer.list.getFirst());
    	    long pos = 0;
            while(!b.isleaf){
        	    pos = b.address.getFirst().longValue();
        	    buffer.getBlock(new File(index),(pos-1024)/4096 , 1024);
    	        b = new BtreeNode(buffer.list.getFirst());
            }
        }catch(Exception e){
        	System.out.println("搜索错误");
        }
        return b.address.getFirst().longValue();
    }
}