B-树java简单实现

1、Entry 存放节点数据

 

public class Entry<K,V> {

	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;
	}
}

2、BTreeNode类，存放节点信息

 

 

public class BTreeNode<K,V> {

	private List<Entry<K,V>> entrys;      //当前节点数据
	private boolean isLeaf;     //时候有叶子节点
	private List<BTreeNode<K,V>> childNodes;    //孩子节点
	private int t = 4;         //
	private int minKey = t-1;      //叶子节点的最小值
	private int maxKey = 2*t-1;     //叶子节点的最大值，用于分裂节点
	
	public BTreeNode() {
		entrys = new ArrayList<Entry<K,V>>();
		childNodes = new ArrayList<BTreeNode<K,V>>();
	}
	public BTreeNode(List<Entry<K, V>> entrys, List<BTreeNode<K, V>> childNodes) {
		this.entrys = entrys;
		this.childNodes = childNodes;
	}
	public BTreeNode(List<Entry<K, V>> entrys, boolean isLeaf,
			List<BTreeNode<K, V>> childNodes) {
		this(entrys,childNodes);
		this.isLeaf = isLeaf;
	}
	/**
	 * 当前节点的size
	 * @return
	 */
	public int size() {
		return entrys.size();
	}
	
	public void set(Entry<K,V> entry,int index) {
		entrys.set(index, entry);
	}
	/**
	 * 返回index处数据
	 * @param index
	 * @return
	 */
	public Entry<K,V> getEntry(int index) {
		return entrys.get(index);
	}
	/**
	 * 返回index处的子节点
	 * @param index
	 * @return
	 */
	public BTreeNode<K,V> getChild(int index) {
		return childNodes.get(index);
	}
	/**
	 * 分割节点
	 * @param parentNode
	 * @param index
	 */
	public void splitNode(BTreeNode<K,V> parentNode,int index) {
		assert entrys.size() > maxKey;
		
		BTreeNode<K,V> anotherNodes = new BTreeNode<K,V>();
		anotherNodes.setLeaf(this.isLeaf);
		for(int i=t;i<maxKey;i++) {
			anotherNodes.putEntry(entrys.get(i));
		}
		Entry<K,V> 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<maxKey;i++) {
				anotherNodes.addChild(childNodes.get(i));
			}
			for(int i=t;i<maxKey;i++) {
				anotherNodes.removeChild(i);
			}
		}
		parentNode.insertEntry(entry,index);
		parentNode.insertChild(anotherNodes,index+1);
	}
	/**
	 * 删除当前数据
	 * @param index
	 * @return
	 */
	public Entry<K,V> removeEntry(int index) {
		return entrys.remove(index);
	}
	/**
	 * 删除子节点
	 * @param index
	 */
	public void removeChild(int index) {
		childNodes.remove(index);
	}
	/**
	 * 新增子节点
	 * @param childNode
	 */
	public void addChild(BTreeNode<K,V> childNode) {
		childNodes.add(childNode);
	}
	/**
	 * 在index处新增数据
	 * @param childNode
	 * @param index
	 */
	public void addChild(BTreeNode<K,V> childNode,int index) {
		childNodes.add(index, childNode);
	}
	/**
	 * 添加子节点
	 * @param childNode
	 * @param index
	 */
	public void insertChild(BTreeNode<K,V> childNode,int index) {
		List<BTreeNode<K,V>> newChildsNode = new ArrayList<BTreeNode<K,V>>();
		for(int i=0;i<index;i++) {
			newChildsNode.add(childNodes.get(i));
		}
		newChildsNode.add(childNode);
		for(int i=index;i<childNodes.size();i++) {
			newChildsNode.add(childNodes.get(i));
		}
		childNodes.clear();
		childNodes = newChildsNode;
	}
	/**
	 * 添加当前节点的数据
	 * 若k一样则更新V
	 * @param entry
	 */
	public void putEntry(Entry<K,V> entry) {
		SearchResult<V> result = searchKey(entry);
		if(result.isExist()) {
			Entry<K,V> 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<K,V> entry) {
		SearchResult<V> result = searchKey(entry);
		if(result.isExist()) {
			return false;
		}
		insertEntry(entry,result.getIndex());
		return true;
	}
	/**
	 * 在index位置新增数据
	 * @param entry
	 * @param index
	 */
	public void insertEntry(Entry<K,V> entry,int index) {
		List<Entry<K,V>> newTreeNode = new ArrayList<Entry<K,V>>();
		for(int i=0;i<index;i++) {
			newTreeNode.add(entrys.get(i));
		}
		newTreeNode.add(entry);
		for(int i=index;i<entrys.size();i++) {
			newTreeNode.add(entrys.get(i));
		}
		entrys.clear();
		entrys = newTreeNode;
	}
	/**
	 * 查询
	 * @param entry
	 * @return
	 */
	public SearchResult<V> searchKey(Entry<K,V> entry) {
		if(entrys.size()==0) {
			return new SearchResult<V>(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<K,V> 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<V>(isExist, mid,v);
		}else {
			return new SearchResult<V>(isExist,low,entry.getV());
		}
	}
	
	public int compare(K k1,K k2) {
		return ((Comparable<K>)k1).compareTo(k2);
	}
	
	public List<Entry<K, V>> getEntrys() {
		return entrys;
	}
	public void setEntrys(List<Entry<K, V>> entrys) {
		this.entrys = entrys;
	}
	public boolean isLeaf() {
		return isLeaf;
	}
	public void setLeaf(boolean isLeaf) {
		this.isLeaf = isLeaf;
	}
	public List<BTreeNode<K, V>> getChildNodes() {
		return childNodes;
	}
	public void setChildNodes(List<BTreeNode<K, V>> childNodes) {
		this.childNodes = childNodes;
	}
	
}

 3、SearchResult搜索节点

public class SearchResult<V> {

	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;
	}
}

 4、tree树

public class BTree<K,V> {

	private BTreeNode<K,V> 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<K,V> newRoot = new BTreeNode<K,V>();
			newRoot.addChild(root);
			newRoot.setLeaf(false);
			root.splitNode(newRoot, 0);
			root = newRoot;
		}
		insertNode(root,new Entry<K,V>(k,v));
	}
	/**
	 * 把数据放入树中
	 * 从node节点判断
	 * @param node
	 * @param entry
	 */
	public void insertNode(BTreeNode<K,V> node,Entry<K,V> entry) {
		if(node.isLeaf()) {    //当前节点为叶子节点
			node.insertEntry(entry);
		}else {   //当前节点为非叶子节点
			//验证是否存在
			SearchResult<V> result = node.searchKey(entry);
			if(result.isExist()) {
				return;
			}
			//当前节点不存在，查询子节点
			BTreeNode<K,V> childNode = node.getChild(result.getIndex());
			//子节点若达到上限，则先分裂
			if(childNode.size()==maxKey) {
				childNode.splitNode(node, result.getIndex());
				Entry<K,V> 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<K,V> delete(BTreeNode<K,V> node,Entry<K,V> entry) {
		SearchResult<V> result = node.searchKey(entry);
		//当前节点存在
		if(result.isExist()) {
			if(node.isLeaf()) {
				node.removeEntry(result.getIndex());
			}else {
				//当前节点存在，若左节点大于最小值，则从左节点补充当前节点的父节点
				BTreeNode<K,V> leftChildNode = node.getChild(result.getIndex());
				if(leftChildNode.size()>=t) {
					node.removeEntry(result.getIndex());
					Entry<K,V> leftMaxEntry = leftChildNode.getEntry(leftChildNode.size()-1);
					node.insertEntry(leftMaxEntry, result.getIndex());
					return delete(leftChildNode,leftMaxEntry);
				}else { //左节点不满足，从右节点补充
					BTreeNode<K,V> rightChildNode = node.getChild(result.getIndex()+1);
					if(rightChildNode.size()>=t) {
						node.removeEntry(result.getIndex());
						Entry<K,V> rightMinEntry = rightChildNode.getEntry(0);
						node.insertEntry(rightMinEntry, result.getIndex());
						return delete(rightChildNode,rightMinEntry);
					}else {  //左右节点都不满足,则和右节点合并
						Entry<K,V> deleteEntry = node.removeEntry(result.getIndex());
						node.removeChild(result.getIndex()+1);
						leftChildNode.insertEntry(deleteEntry);
						for(Entry<K,V> tempEntry:rightChildNode.getEntrys()) {
							leftChildNode.insertEntry(tempEntry);
						}
						if(!rightChildNode.isLeaf()) {
							for(BTreeNode<K,V> tempNode:rightChildNode.getChildNodes()) {
								leftChildNode.addChild(tempNode);
							}
						}
						return delete(leftChildNode,entry);
					}
				}
			}
		}else {  //当前节点不存在 ，下一步查询子节点
			if(node.isLeaf()) {
				return null;
			}
			BTreeNode<K,V> childNode = node.getChild(result.getIndex());
			//若子节点的个数大于最小值
			if(childNode.size()>=t) {
				return delete(childNode,entry);
			}
			//子节点个数小于最小值,寻找填充节点（填充节点的个数大于最小值）
			BTreeNode<K,V> fillChildNode = null;
			int fillChildIndex = -1;
			//寻找右节点
			if(result.getIndex()<node.size()) {
				BTreeNode<K,V> rightChildNode = node.getChild(result.getIndex()+1);
				if(rightChildNode.size()>=t) {					
					fillChildNode = rightChildNode;
					fillChildIndex = result.getIndex()+1;
				}
			}
			//寻找左节点
			if(fillChildNode==null) {
				if(result.getIndex()>0) {
					BTreeNode<K,V> leftChildNode = node.getChild(result.getIndex()-1);
					if(leftChildNode.size()>=t) {
						fillChildNode = leftChildNode;
						fillChildIndex = result.getIndex()-1;
					}
				}
			}
			//找到满足的节点
			if(fillChildNode!=null) {
				//满足节点为右节点
				if(fillChildIndex > result.getIndex()) {
					Entry<K,V> firstEntry = fillChildNode.getEntry(0);
					fillChildNode.removeEntry(0);
					childNode.insertEntry(firstEntry);
					if(!fillChildNode.isLeaf()) {
					   childNode.addChild(fillChildNode.getChild(0));
					   fillChildNode.removeChild(0);
					}
				}else {  //满足节点为左节点
					Entry<K,V> 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()<node.size()) {   //当前节点存在右节点
					BTreeNode<K,V> rightNode = node.getChild(result.getIndex()+1);
					//Entry<K,V> newTopEntry = rightNode.removeEntry(rightNode.getEntrys().size()-1);
					Entry<K,V> oldTopEntry = node.removeEntry(result.getIndex());
				//	node.insertEntry(newTopEntry,result.getIndex());
					childNode.insertEntry(oldTopEntry);
					node.removeChild(result.getIndex()+1);
					
					for(Entry<K,V> tempEntry:rightNode.getEntrys()) {
						childNode.insertEntry(tempEntry);
					}
					if(!rightNode.isLeaf()) {
						for(BTreeNode<K,V> tempNode:node.getChildNodes()) {
							node.addChild(tempNode);
						}
					}
				}else {   //当前节点存在左节点
					BTreeNode<K,V> leftNode = node.getChild(result.getIndex()-1);
					//Entry<K,V> newTopEntry = leftNode.removeEntry(0);
					Entry<K,V> oldTopEntry = node.removeEntry(result.getIndex());
					//node.insertEntry(newTopEntry, result.getIndex());
					childNode.insertEntry(oldTopEntry);
					
				    List<Entry<K,V>> entryList = leftNode.getEntrys();
					for(int i=entryList.size()-1;i>=0;i--) {
						node.insertEntry(entryList.get(i), 0);
					}
					if(!leftNode.isLeaf()) {
						List<BTreeNode<K,V>> 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<K, V> getRoot() {
		return root;
	}
	public void setRoot(BTreeNode<K, V> root) {
		this.root = root;
	}
	
	public void printTree(BTreeNode<String,String> node) {
		boolean flag = node.isLeaf();
		System.out.println("*********节点开始***********");
		for(Entry<String,String> entry:node.getEntrys()) {
			System.out.println("当前节点的数据:K="+entry.getK()+",V="+entry.getV());
		}
		System.out.println("***********节点结束************");
		if(!flag) {
                    System.out.println("查询子节点开始");
			for(BTreeNode<String,String> tempNode:node.getChildNodes()) {
				printTree(tempNode);
			}
                     System.out.println("查询子节点结束");
		}
	}

	public static void main(String[] args) {
		BTree<String,String> btree = new BTree<String,String>();
		BTreeNode<String,String> root = new BTreeNode<String,String>();
		root.setLeaf(true);
		btree.setRoot(root);
		btree.insertTreeCommon(btree);
		
		btree.delete(btree.getRoot(), new Entry<String,String>("B","B"));
		
		btree.printTree(btree.getRoot());
	}
	
	public void insertTreeCommon(BTree<String,String> 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");
	}
}