B-ツリーjavaシンプル実装

public class Entry {

	private K k;
	private V v;
	
	public Entry(K k, V v) {
		this.k = k;
		this.v = v;
	}
	public K getK() {
		return k;
	}
	public void setK(K k) {
		this.k = k;
	}
	public V getV() {
		return v;
	}
	public void setV(V v) {
		this.v = v;
	}
}

public class BTreeNode {

	private List> entrys;      //      
	private boolean isLeaf;     //       
	private List> childNodes;    //    
	private int t = 4;         //
	private int minKey = t-1;      //        
	private int maxKey = 2*t-1;     //        ，      
	
	public BTreeNode() {
		entrys = new ArrayList>();
		childNodes = new ArrayList>();
	}
	public BTreeNode(List> entrys, List> childNodes) {
		this.entrys = entrys;
		this.childNodes = childNodes;
	}
	public BTreeNode(List> entrys, boolean isLeaf,
			List> childNodes) {
		this(entrys,childNodes);
		this.isLeaf = isLeaf;
	}
	/**
	 *      size
	 * @return
	 */
	public int size() {
		return entrys.size();
	}
	
	public void set(Entry entry,int index) {
		entrys.set(index, entry);
	}
	/**
	 *   index   
	 * @param index
	 * @return
	 */
	public Entry getEntry(int index) {
		return entrys.get(index);
	}
	/**
	 *   index     
	 * @param index
	 * @return
	 */
	public BTreeNode getChild(int index) {
		return childNodes.get(index);
	}
	/**
	 *     
	 * @param parentNode
	 * @param index
	 */
	public void splitNode(BTreeNode parentNode,int index) {
		assert entrys.size() > maxKey;
		
		BTreeNode anotherNodes = new BTreeNode();
		anotherNodes.setLeaf(this.isLeaf);
		for(int i=t;i entry = entrys.get(t-1);
		for(int i=maxKey-1;i>=t-1;--i) {
			entrys.remove(i);
		}
		if(!this.isLeaf) {
			
			for(int i=t;i removeEntry(int index) {
		return entrys.remove(index);
	}
	/**
	 *      
	 * @param index
	 */
	public void removeChild(int index) {
		childNodes.remove(index);
	}
	/**
	 *      
	 * @param childNode
	 */
	public void addChild(BTreeNode childNode) {
		childNodes.add(childNode);
	}
	/**
	 *  index     
	 * @param childNode
	 * @param index
	 */
	public void addChild(BTreeNode childNode,int index) {
		childNodes.add(index, childNode);
	}
	/**
	 *      
	 * @param childNode
	 * @param index
	 */
	public void insertChild(BTreeNode childNode,int index) {
		List> newChildsNode = new ArrayList>();
		for(int i=0;i entry) {
		SearchResult result = searchKey(entry);
		if(result.isExist()) {
			Entry searchEntry = entrys.get(result.getIndex());
			searchEntry.setV(entry.getV());
			entrys.set(result.getIndex(), searchEntry);
		}else {
			insertEntry(entry,result.getIndex());
		}
	}
	/**
	 *     
	 * @param entry
	 * @return
	 */
	public boolean insertEntry(Entry entry) {
		SearchResult result = searchKey(entry);
		if(result.isExist()) {
			return false;
		}
		insertEntry(entry,result.getIndex());
		return true;
	}
	/**
	 *  index      
	 * @param entry
	 * @param index
	 */
	public void insertEntry(Entry entry,int index) {
		List> newTreeNode = new ArrayList>();
		for(int i=0;i searchKey(Entry entry) {
		if(entrys.size()==0) {
			return new SearchResult(false,0,entry.getV());
		}
		int low = 0;
		int high = entrys.size()-1;
		int mid = 0;
		boolean isExist = false;
		V v = null;
		while(low<=high) {
			mid = (low+high)/2;
			Entry searchEntry = entrys.get(mid);
			int compareInt = compare(entry.getK(), searchEntry.getK());
			if(compareInt==0) {
				isExist = true;
				v = searchEntry.getV();
				break;
			}else if(compareInt>0) {
				low = mid+1;
			}else {
				high = mid-1;
			}
		}
		if(isExist) {
			return new SearchResult(isExist, mid,v);
		}else {
			return new SearchResult(isExist,low,entry.getV());
		}
	}
	
	public int compare(K k1,K k2) {
		return ((Comparable)k1).compareTo(k2);
	}
	
	public List> getEntrys() {
		return entrys;
	}
	public void setEntrys(List> entrys) {
		this.entrys = entrys;
	}
	public boolean isLeaf() {
		return isLeaf;
	}
	public void setLeaf(boolean isLeaf) {
		this.isLeaf = isLeaf;
	}
	public List> getChildNodes() {
		return childNodes;
	}
	public void setChildNodes(List> childNodes) {
		this.childNodes = childNodes;
	}
	
}

public class SearchResult {

	private boolean isExist;   //        
	private int index;     //             
	private V v;      //      
	
	public SearchResult(boolean isExist, int index, V v) {
		this.isExist = isExist;
		this.index = index;
		this.v = v;
	}
	public SearchResult(boolean isExist, int index) {
		this.isExist = isExist;
		this.index = index;
	}
	public boolean isExist() {
		return isExist;
	}
	public void setExist(boolean isExist) {
		this.isExist = isExist;
	}
	public int getIndex() {
		return index;
	}
	public void setIndex(int index) {
		this.index = index;
	}
	public V getV() {
		return v;
	}
	public void setV(V v) {
		this.v = v;
	}
}

public class BTree {

	private BTreeNode root;     //   
	private int t = 4;
	private int minKey = t-1;      //      
	private int maxKey = 2*t-1;    //      ，    
	/**
	 *        
	 *       
	 * @param k
	 * @param v
	 */
	public void insert(K k,V v) {
		if(root.size()==maxKey) {
			BTreeNode newRoot = new BTreeNode();
			newRoot.addChild(root);
			newRoot.setLeaf(false);
			root.splitNode(newRoot, 0);
			root = newRoot;
		}
		insertNode(root,new Entry(k,v));
	}
	/**
	 *        
	 *  node    
	 * @param node
	 * @param entry
	 */
	public void insertNode(BTreeNode node,Entry entry) {
		if(node.isLeaf()) {    //         
			node.insertEntry(entry);
		}else {   //          
			//      
			SearchResult result = node.searchKey(entry);
			if(result.isExist()) {
				return;
			}
			//       ，     
			BTreeNode childNode = node.getChild(result.getIndex());
			//        ，    
			if(childNode.size()==maxKey) {
				childNode.splitNode(node, result.getIndex());
				Entry entryAt = node.getEntry((result.getIndex()));
				if(node.compare(entry.getK(), entryAt.getK())>0) {
					childNode = node.getChild(result.getIndex()+1);
				}
			}
			//    
			insertNode(childNode,entry);
		}
	}
	/**
	 *     
	 * @param node
	 * @param entry
	 * @return
	 */
	public Entry delete(BTreeNode node,Entry entry) {
		SearchResult result = node.searchKey(entry);
		//      
		if(result.isExist()) {
			if(node.isLeaf()) {
				node.removeEntry(result.getIndex());
			}else {
				//      ，         ，               
				BTreeNode leftChildNode = node.getChild(result.getIndex());
				if(leftChildNode.size()>=t) {
					node.removeEntry(result.getIndex());
					Entry leftMaxEntry = leftChildNode.getEntry(leftChildNode.size()-1);
					node.insertEntry(leftMaxEntry, result.getIndex());
					return delete(leftChildNode,leftMaxEntry);
				}else { //      ，      
					BTreeNode rightChildNode = node.getChild(result.getIndex()+1);
					if(rightChildNode.size()>=t) {
						node.removeEntry(result.getIndex());
						Entry rightMinEntry = rightChildNode.getEntry(0);
						node.insertEntry(rightMinEntry, result.getIndex());
						return delete(rightChildNode,rightMinEntry);
					}else {  //        ,       
						Entry deleteEntry = node.removeEntry(result.getIndex());
						node.removeChild(result.getIndex()+1);
						leftChildNode.insertEntry(deleteEntry);
						for(Entry tempEntry:rightChildNode.getEntrys()) {
							leftChildNode.insertEntry(tempEntry);
						}
						if(!rightChildNode.isLeaf()) {
							for(BTreeNode tempNode:rightChildNode.getChildNodes()) {
								leftChildNode.addChild(tempNode);
							}
						}
						return delete(leftChildNode,entry);
					}
				}
			}
		}else {  //        ，        
			if(node.isLeaf()) {
				return null;
			}
			BTreeNode childNode = node.getChild(result.getIndex());
			//            
			if(childNode.size()>=t) {
				return delete(childNode,entry);
			}
			//          ,      （            ）
			BTreeNode fillChildNode = null;
			int fillChildIndex = -1;
			//     
			if(result.getIndex() rightChildNode = node.getChild(result.getIndex()+1);
				if(rightChildNode.size()>=t) {					
					fillChildNode = rightChildNode;
					fillChildIndex = result.getIndex()+1;
				}
			}
			//     
			if(fillChildNode==null) {
				if(result.getIndex()>0) {
					BTreeNode leftChildNode = node.getChild(result.getIndex()-1);
					if(leftChildNode.size()>=t) {
						fillChildNode = leftChildNode;
						fillChildIndex = result.getIndex()-1;
					}
				}
			}
			//       
			if(fillChildNode!=null) {
				//        
				if(fillChildIndex > result.getIndex()) {
					Entry firstEntry = fillChildNode.getEntry(0);
					fillChildNode.removeEntry(0);
					childNode.insertEntry(firstEntry);
					if(!fillChildNode.isLeaf()) {
					   childNode.addChild(fillChildNode.getChild(0));
					   fillChildNode.removeChild(0);
					}
				}else {  //        
					Entry lastEntry = fillChildNode.getEntry(fillChildNode.size()-1);
					childNode.insertEntry(lastEntry, 0);
					if(!fillChildNode.isLeaf()) {
						childNode.addChild(fillChildNode.getChild(fillChildNode.size()-1));
						fillChildNode.removeChild(fillChildNode.size()-1);
					}
					fillChildNode.removeEntry(fillChildNode.size()-1);
				}
				return delete(fillChildNode,entry);
			}else {    //        
				if(result.getIndex() rightNode = node.getChild(result.getIndex()+1);
					//Entry newTopEntry = rightNode.removeEntry(rightNode.getEntrys().size()-1);
					Entry oldTopEntry = node.removeEntry(result.getIndex());
				//	node.insertEntry(newTopEntry,result.getIndex());
					childNode.insertEntry(oldTopEntry);
					node.removeChild(result.getIndex()+1);
					
					for(Entry tempEntry:rightNode.getEntrys()) {
						childNode.insertEntry(tempEntry);
					}
					if(!rightNode.isLeaf()) {
						for(BTreeNode tempNode:node.getChildNodes()) {
							node.addChild(tempNode);
						}
					}
				}else {   //         
					BTreeNode leftNode = node.getChild(result.getIndex()-1);
					//Entry newTopEntry = leftNode.removeEntry(0);
					Entry oldTopEntry = node.removeEntry(result.getIndex());
					//node.insertEntry(newTopEntry, result.getIndex());
					childNode.insertEntry(oldTopEntry);
					
				    List> entryList = leftNode.getEntrys();
					for(int i=entryList.size()-1;i>=0;i--) {
						node.insertEntry(entryList.get(i), 0);
					}
					if(!leftNode.isLeaf()) {
						List> bTreeList = leftNode.getChildNodes();
						for(int i=bTreeList.size()-1;i>=0;i--) {
							node.addChild(bTreeList.get(i), 0);
						}
					}
				}
				if(node==root&&node.size()==0) {
					root = childNode;
				}
				/*if(root.size()==0) {
					root = childNode;
				}*/
				return delete(childNode,entry);
			}
		}
		return null;
	}
	
	public BTreeNode getRoot() {
		return root;
	}
	public void setRoot(BTreeNode root) {
		this.root = root;
	}
	
	public void printTree(BTreeNode node) {
		boolean flag = node.isLeaf();
		System.out.println("*********    ***********");
		for(Entry entry:node.getEntrys()) {
			System.out.println("       :K="+entry.getK()+",V="+entry.getV());
		}
		System.out.println("***********    ************");
		if(!flag) {
                    System.out.println("       ");
			for(BTreeNode tempNode:node.getChildNodes()) {
				printTree(tempNode);
			}
                     System.out.println("       ");
		}
	}

	public static void main(String[] args) {
		BTree btree = new BTree();
		BTreeNode root = new BTreeNode();
		root.setLeaf(true);
		btree.setRoot(root);
		btree.insertTreeCommon(btree);
		
		btree.delete(btree.getRoot(), new Entry("B","B"));
		
		btree.printTree(btree.getRoot());
	}
	
	public void insertTreeCommon(BTree btree) {
		btree.insert("A", "A");
		btree.insert("B", "B");
		btree.insert("C", "C");
		btree.insert("D", "D");
		btree.insert("E", "E");
		btree.insert("F", "F");
		btree.insert("G", "G");
		btree.insert("H", "H");
		btree.insert("I", "I");
		btree.insert("J", "J");
		btree.insert("K", "K");
		btree.insert("L", "L");
		btree.insert("M", "M");
		btree.insert("N", "N");
	}
}