爱威尔-java从2-3-4树到B-tree的原理与实现再到B+tree的了解

2-3-4树存在的意义其实很明显了就是为B-tree做准备的或者说是特殊的B-tree，而且用途也没有B-tree多，所以说了解2-3-4树是为了更好地了解和理解B-tree的。 
 B-tree在应用中多么？其实在现在存储数据结构里面用的也不是很多，而用的更多的是B-tree的变形树比如B+tree，这个在关系型数据库领域可谓是大放异彩。 
 Mysql、oracle、db2等无不都是使用的B+tree来做数据索引的，网上也有一些理论性的文章但是在我看来也不是很明白，（也许是我还没有理解透彻） 
 而随之而来的的NoSql世界却出现了LSM-tree这样的一个数据结构来实现数据的持久化，自从hbase出现以来大家开始关注而且做得越开越好，成为了NOSQL领域的高性能的代名词没有LSM-tree就别提什么高性能，发展到16 17年出现的NewSql数据库其底层也是LSM-tree为基础的索引，没想到现在的大部分nosql数据库都是使用该算法作为基础，而且正在引领下一代newsql数据库的发展。 
 <img src="93/20180406140420_764.jpg" alt=""> 
 
 
<pre class="prettyprint lang-java">package weir.suanfa.tree234;
/**
 * 封装数据识别项
* @author weir 
* 2018年4月5日 上午10:35:32 
*
 */
public class KeyItem {

private int id;
	private int data;

public KeyItem(int id) {
		super();
		this.id = id;
	}

public int getId() {
		return id;
	}

public void setId(int id) {
		this.id = id;
	}

public int getData() {
		return data;
	}

public void setData(int data) {
		this.data = data;
	}

@Override
	public String toString() {
		return "KeyItem [id=" + id + ", data=" + data + "]";
	}

}

package weir.suanfa.tree234;
/**
 * 2-3-4树的节点对象
* @author weir 
* 2018年4月5日 上午10:34:06 
*
 */
public class Node234 {
 /**
 * 存放多个识别数据项（最多3个）
 */
	private KeyItem[] items = new KeyItem[3];
	/**
	 * 存放多个子节点对象（最多四个）
	 */
	private Node234[] childNode = new Node234[4];
	/**
	 * 父节点对象
	 */
	private Node234 parent = null;
	/**
	 * 记录当前节点存放多少个识别数据项
	 */
	private int numItems;
	/**
	 * 给本节点新加入一个识别数据项
	 * @param newItem
	 * @return
	 */
	public int insertKeyItem(KeyItem newItem) {
		numItems++;
		//这里为什么从后往前找和比较？
		for (int i = 2; i >=0; i--) {
			if (this.items[i] == null) {
				continue;
			}else {
				//如果新加入的大
				if (this.items[i].getId() < newItem.getId()) { items[i+1] = newItem; return i+1; }else { items[i+1] = items[i]; } } } items[0] = newItem; return 0; } /** * 给本节点删除一个识别数据项（删除最后一个） * @param newItem * @return */ public KeyItem removeKeyItem() { KeyItem ki = items[this.numItems-1]; items[this.numItems-1] = null; this.numItems--; return ki; } /** * 给本节点查找一个识别数据项 * @param newItem * @return */ public int findKeyItem(int key) { for (int i = 0; i < 3; i++) { if (items[i]==null) { break; }else if (items[i].getId() == key) { return i; } } return -1; } /** * 给本节点连接一个子节点 * @param childIndex * @param childNode */ public void connectChild(int childIndex,Node234 childNode) { this.childNode[childIndex] = childNode; if (childNode!=null) { childNode.setParent(this); } } /** * 给本节点断开一个子节点 * @param childIndex * @return */ public Node234 disconnectChild(int childIndex) { Node234 n = this.childNode[childIndex]; this.childNode[childIndex] = null; return n; } /** * 获取一个子节点 * @param childIndex * @return */ public Node234 getChild(int childIndex) { return this.childNode[childIndex]; } /** * 获取父节点 * @param childIndex * @return */ public Node234 getParent() { return this.parent; } /** * 判断是否是叶子节点（第一个位置是否为空） * @return */ public boolean isLeaf() { return this.childNode[0]==null; } /** * 判断本节点的识别数据项是否已经满了 * @return */ public boolean isFull() { return this.numItems == 3; } public KeyItem[] getItems() { return items; } public void setItems(KeyItem[] items) { this.items = items; } public Node234[] getChildNode() { return childNode; } public void setChildNode(Node234[] childNode) { this.childNode = childNode; } public int getNumItems() { return numItems; } public void setNumItems(int numItems) { this.numItems = numItems; } public void setParent(Node234 parent) { this.parent = parent; } public void printNode() { for (int i = 0; i < this.numItems; i++) { System.out.println(this.items[i].getId()+","); } System.out.println("-----"); } } package weir.suanfa.tree234; /** * 2-3-4树的操作 * @author weir * 2018年4月5日 上午10:58:56 * */ public class Tree234 { private Node234 root = new Node234(); /** * 这里查找的是索引key * @param key * @return */ public int find(int key) { Node234 current = root; int childIndex; while (true) { childIndex = current.findKeyItem(key); if (childIndex>=0) {
				return childIndex;
			}else if (current.isLeaf()) {
				return -1;
			}else {
				current = getNext(current, key);
			}
		}
	}
	/**
	 * 查找下一个节点
	 * @param node
	 * @param key
	 * @return
	 */
	private Node234 getNext(Node234 node,int key) {
		int i = 0;
		for (i=0; i < node.getNumItems(); i++) { if (key<node.getitems()[i].getid()) {="" return="" node.getchild(i);="" }="" **="" *="" 插入一个识别数据="" @param="" id="" public="" void="" insert(int="" id)="" 1：插入到未满的叶节点里面，直接插入数据即可，顶多会引起同一节点内数据项的="" 移动，以保持数据项的顺序="" 2：插入到未满的子节点里面，子节点的编号就要发生变化，以此来保证树的结构="" 3：插入到已满的节点中，这就需要做节点分裂，算法如下：="" （1）创建一个空节点，放置到分裂节点的右边="" （2）最大数据项移动到新节点，中间数据项移动到父节点，最小的数据项不动="" （3）重新设置最大和中间数据项的父子节点关系="" 4：插入到已满的根节点中，这就需要做根节点分裂，算法如下：="" （1）创建一个空节点，作为分裂节点的父节点="" （2）再创建一个空节点，作为分裂节点的兄弟节点="" （3）最大数据项移动到新的兄弟节点中，中间数据项移动到新的父节点，最小的数="" 据项不动="" （4）重新设置最大和中间数据项的父子节点关系="" node234="" current="root;" keyitem="" newitem="new" keyitem(id);="" 查找要插入的位置="" while="" (true)="" if="" (current.isfull())="" 满了="" 1.需要做节点分裂="" this.splitnode(current);="" 2.查找current="" 2.1="" 先得到current的父节点，因为本节点分裂了="" 2.2="" 再从新查找下一个节点="" id);="" }else="" (current.isleaf())="" break;="" current.insertkeyitem(newitem);="" 分裂节点="" private="" splitnode(node234="" node)="" 记录原始数据，并断开关系="" key2,key3;="" parent,child3,child4;="" key3="node.removeKeyItem();" key2="node.removeKeyItem();" child3="node.disconnectChild(2);" child4="node.disconnectChild(3);" 创建一个兄弟节点="" rightnode="new" node234();="" 如果是根节点分裂，需要创建新的parent，并维护关系="" (node="=" root)="" root="new" parent="root;" root.connectchild(0,="" node);="" 中间数据项移动到父节点="" int="" itemindex="parent.insertKeyItem(key2);" 维护parent中的child节点的关系="" num="parent.getNumItems();" for="" (int="" i="num-1;">
 itemIndex; i--) {
			//先断开，再重新加入
			Node234 temp = parent.disconnectChild(i);
			parent.connectChild(i+1, temp);
		}
		
		//把兄弟节点加入父节点
		parent.connectChild(itemIndex+1, rightNode);
		
		
		//维护新的兄弟节点
		rightNode.insertKeyItem(key3);
		rightNode.connectChild(0, child3);
		rightNode.connectChild(1, child4);
		
	}
	
	public void printTree(Node234 node) {
		node.printNode();
		for (int i = 0; i 
 <node.getnumitems()+1; i++)="" {="" node234="" child="node.getChild(i);" if="" (child="=null)" return;="" }else="" printtree(child);="" }="" public="" static="" void="" main(string[]="" args)="" tree234="" tree234();="" tree234.insert(20);="" tree234.insert(10);="" tree234.insert(15);="" tree234.insert(19);="" tree234.insert(8);="" tree234.insert(13);="" tree234.insert(30);="" tree234.insert(40);="" tree234.insert(50);="" tree234.insert(38);="" tree234.printtree(tree234.root);="">
 <="" pre=""> 
 <img src="93/20180406140600_412.jpg" alt="">

<pre class="prettyprint lang-java">package weir.suanfa.btree;
/**
 * 封装数据识别项
* @author weir 
* 2018年4月5日 上午10:35:32 
*
 */
public class KeyItem {

private int id;
	private int data;

public KeyItem(int id) {
		super();
		this.id = id;
	}

public int getId() {
		return id;
	}

public void setId(int id) {
		this.id = id;
	}

public int getData() {
		return data;
	}

public void setData(int data) {
		this.data = data;
	}

@Override
	public String toString() {
		return "KeyItem [id=" + id + ", data=" + data + "]";
	}

}

package weir.suanfa.btree;

public class BTreeNode {
	/**
	 * B树的阶数
	 */
	private int m = 0;
 /**
 * 存放识别数据项
 */
	private KeyItem[] items = null;
	/**
	 * 存放子节点对象
	 */
	private BTreeNode[] childNode = null;
	/**
	 * 父节点对象
	 */
	private BTreeNode parent = null;
	/**
	 * 记录当前节点存放多少个识别数据项
	 */
	private int numItems;
	/**
	 * 构造方法传递阶数
	 * @param m
	 */
	public BTreeNode(int m) {
		this.m = m;
		//这里是为什么？
		items = new KeyItem[m-1];
		childNode = new BTreeNode[m];
	}
	/**
	 * 根据索引获取相应的识别数据项
	 * @param index
	 * @return
	 */
	public KeyItem getItem(int index) {
		return items[index];
	}
	
	/**
	 * 给本节点新加入一个识别数据项
	 * @param newItem
	 * @return
	 */
	public int insertKeyItem(KeyItem newItem) {
		numItems++;
		for (int i = (m-2); i >=0; i--) {
			if (this.items[i] == null) {
				continue;
			}else {
				//如果新加入的大
				if (this.items[i].getId() < newItem.getId()) { items[i+1] = newItem; return i+1; }else { items[i+1] = items[i]; } } } items[0] = newItem; return 0; } /** * 给本节点删除一个识别数据项 * @param newItem * @return */ public KeyItem removeKeyItem() { KeyItem ki = items[this.numItems-1]; items[this.numItems-1] = null; this.numItems--; return ki; } /** * 按照索引删除某个keyItem * @param index */ public void removeKeyItem(int index) { //依次向前移动一个覆盖 for (int i = index+1; i < this.numItems; i++) { this.items[i-1] = this.items[i]; } //把最后一个值为 null this.items[this.numItems-1] = null; this.numItems--; } /** * 删除节点所有的keyItem */ public void remveAll() { for (int i = 0; i < this.numItems; i++) { this.items[i] = null; } this.numItems = 0; } /** * 给本节点查找一个识别数据项 * @param newItem * @return */ public int findKeyItem(int key) { for (int i = 0; i < (m-1); i++) { if (items[i]==null) { break; }else if (items[i].getId() == key) { return i; } } return -1; } /** * 给本节点连接一个子节点 * @param childIndex * @param childNode */ public void connectChild(int childIndex,BTreeNode childNode) { this.childNode[childIndex] = childNode; if (childNode!=null) { childNode.setParent(this); } } /** * 给本节点断开一个子节点 * @param childIndex * @return */ public BTreeNode disconnectChild(int childIndex) { BTreeNode n = this.childNode[childIndex]; this.childNode[childIndex] = null; return n; } /** * 获取一个子节点 * @param childIndex * @return */ public BTreeNode getChild(int childIndex) { return this.childNode[childIndex]; } /** * 获取父节点 * @param childIndex * @return */ public BTreeNode getParent() { return this.parent; } /** * 判断是否是叶子节点 * @return */ public boolean isLeaf() { return this.childNode[0]==null; } /** * 判断本节点的识别数据项是否已经满了 * @return */ public boolean isFull() { return this.numItems == m-1; } public KeyItem[] getItems() { return items; } public void setItems(KeyItem[] items) { this.items = items; } public BTreeNode[] getChildNode() { return childNode; } public void setChildNode(BTreeNode[] childNode) { this.childNode = childNode; } public int getNumItems() { return numItems; } public void setNumItems(int numItems) { this.numItems = numItems; } public void setParent(BTreeNode parent) { this.parent = parent; } public int getM() { return m; } public void setM(int m) { this.m = m; } public void printNode() { for (int i = 0; i < this.numItems; i++) { System.out.print(this.items[i].getId()+","); } System.out.println("-----"); } } package weir.suanfa.btree; import java.util.ArrayList; import java.util.List; public class BTree { /** * B树的阶数 */ private int m = 0; private BTreeNode root = null; public BTree(int m) { this.m = m; root = new BTreeNode(m); } /** * 查找 * @param key * @return */ public Object[] find(int key) { //返回对象加索引 Object[] obj = new Object[2]; BTreeNode current = root; int childIndex; while (true) { childIndex = current.findKeyItem(key); if (childIndex >= 0) {
				obj[0] = current;
				obj[1] = childIndex;
				return obj;
			} else if (current.isLeaf()) {
				return null;
			} else {
				current = getNext(current, key);
			}
		}
	}

/**
	 * 查找下一个节点
	 * 
	 * @param node
	 * @param key
	 * @return
	 */
	private BTreeNode getNext(BTreeNode node, int key) {
		int i = 0;
		for (i = 0; i < node.getNumItems(); i++) { if (key < node.getItems()[i].getId()) { return node.getChild(i); } } return node.getChild(i); } /** * 插入一个识别数据 * * @param id */ public void insert(int id) { BTreeNode current = root; KeyItem newItem = new KeyItem(id); boolean needInsert = true; // 查找要插入的位置 while (true) { current = this.findCurrent(current, id); if (current.isFull()) {// 满了 needInsert = false; // 1.需要做节点分裂 //这里为什么把newItem传进去 this.splitNode(current, newItem); current = current.getParent(); } else if (current.isLeaf()) { break; } } if (needInsert) { current.insertKeyItem(newItem); } } /** * 查找需要添加数据的叶子节点 * * @param current * @param id * @return */ private BTreeNode findCurrent(BTreeNode current, int id) { while (true) { if (current.isLeaf()) { break; } else { current = this.getNext(current, id); } } return current; } /** * 分裂节点 * * @param current */ private KeyItem splitNode(BTreeNode node, KeyItem newItem) { // 1.先把newItem加入node，好计算中间元素 KeyItem[] newKeyItems = new KeyItem[node.getNumItems() + 1]; //1.1现在入原来的 for (int i = 0; i < node.getNumItems(); i++) { newKeyItems = this.insertKeyItem(newKeyItems, node.getItem(i)); } //1.2加入新的 newKeyItems = this.insertKeyItem(newKeyItems, newItem); // 计算中间索引位置 int middleIndex = (node.getM() + 1) / 2 - 1; // 2.开始移动识别数据 // 记录原始数据，并断开关系 KeyItem[] rightItems = new KeyItem[node.getM() - middleIndex - 1]; BTreeNode[] childs = new BTreeNode[node.getM() - middleIndex - 1]; BTreeNode parent; // 将一半较大的数据移动到新节点 for (int i = 0; i < rightItems.length; i++) { rightItems[i] = newKeyItems[middleIndex + i + 1]; } // 一般较小的数据不动，还在node里面 node.remveAll(); for (int i = 0; i < middleIndex; i++) { node.insertKeyItem(newKeyItems[i]); } // 设置移动到右边的child for (int i = (childs.length - 1); i >= 0; i--) {
			childs[i] = node.disconnectChild(middleIndex + i + 1);
		}

// 创建一个兄弟节点
		BTreeNode rightNode = new BTreeNode(m);
		// 如果是根节点，需要创建新的parent，并维护关系
		if (node == root) {
			root = new BTreeNode(m);
			parent = root;
			root.connectChild(0, node);
		} else {
			parent = node.getParent();
		}

// 中间数据项移动到父节点
		boolean needSplitParent = false;
		KeyItem parentOldKeyItem = null;
		BTreeNode parentOldChildNode = null;
		if (parent.isFull()) {
			needSplitParent = true;
			// 把parent的最后一个keyItem和最后一个child都先删除了，
			// 在分裂parent节点的时候再加入回来
			parentOldKeyItem = parent.removeKeyItem();
			parentOldChildNode = parent.getChild(m - 1);
		}
        //记录上升节点，想想这里是为什么？
		KeyItem upKeyItem = newKeyItems[middleIndex];
		int itemIndex = parent.insertKeyItem(newKeyItems[middleIndex]);

// 维护parent中的child节点的关系
		int num = parent.getNumItems();
		for (int i = num - 1; i > itemIndex; i--) {
			// 先断开，再重新加入
			BTreeNode temp = parent.disconnectChild(i);
			parent.connectChild(i + 1, temp);
		}

// 把兄弟节点加入父节点
		parent.connectChild(itemIndex + 1, rightNode);

// 维护新的兄弟节点
		for (int i = 0; i < rightItems.length; i++) { rightNode.insertKeyItem(rightItems[i]); } for (int i = 0; i < childs.length; i++) { rightNode.connectChild(i, childs[i]); } // 3.处理父节点满的情况 if (needSplitParent) { KeyItem lastUpKeyIte = this.splitNode(parent, parentOldKeyItem); if (lastUpKeyIte.getId() == parentOldKeyItem.getId()) { // 说明是上次删除的parent的最后一个，作为upKeyItem上升了 // 那么，parentOldChildNode就应该作为upKeyItem的第一个child Object[] objs = this.find(upKeyItem.getId()); BTreeNode tempNode = (BTreeNode) objs[0]; // 把原来这个位置后面的数据都想后移动一位 for (int i = 0; i < tempNode.getNumItems(); i++) { tempNode.connectChild(i + 1, tempNode.getChild(i)); } tempNode.connectChild(0, parentOldChildNode); } else { Object[] objs = this.find(parentOldKeyItem.getId()); BTreeNode tempNode = (BTreeNode) objs[0]; int tempIndex = (int) objs[1]; // 把原来这个位置后面的数据都想后移动一位 for (int i = (tempIndex + 1); i < tempNode.getNumItems(); i++) { tempNode.connectChild(i + 1, tempNode.getChild(i)); } tempNode.connectChild(tempIndex + 1, parentOldChildNode); } } return upKeyItem; } /** * 插入并排序 * @param items * @param newItem * @return */ private KeyItem[] insertKeyItem(KeyItem[] items, KeyItem newItem) { for (int i = (items.length - 1); i >= 0; i--) {
			if (items[i] == null) {
				continue;
			} else {
				// 如果新加入的大
				if (items[i].getId() < newItem.getId()) { items[i + 1] = newItem; return items; } else { items[i + 1] = items[i]; } } } items[0] = newItem; return items; } public void printTree(BTreeNode node, int level, int childNumber) { System.out.print("level==" + level + ", child==" + childNumber + " "); node.printNode(); for (int i = 0; i < node.getNumItems() + 1; i++) { BTreeNode child = node.getChild(i); if (child == null) { return; } else { printTree(child, level + 1, i); } } } public void removeKeyItem(int keyItemValue) { // 1：若删除结点为非叶结点，且被删关键字为该结点中第i个关键字key[i]，则可从 // C[i]所指的子树中找出最小关键字Y，代替key[i]的位置，然后在叶结点中删去 // Y。这样一来，就把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关 // 键字的问题了。 Object[] delObj = this.find(keyItemValue); if (delObj != null) { BTreeNode delNode = (BTreeNode) delObj[0]; int delKeyIndex = (int) delObj[1]; if (!delNode.isLeaf()) { BTreeNode nowDelNode = this.findMinKeyItemNode(delNode.getChild(delKeyIndex)); KeyItem minKeyItem = nowDelNode.getItem(0); delNode.getItems()[delKeyIndex] = minKeyItem; this.removeFromLeaf(nowDelNode, 0); } else { this.removeFromLeaf(delNode, delKeyIndex); } } // 2：要删除的关键字在叶子节点上的情况：先把这个关键字删除掉，然后再调整 } private BTreeNode findMinKeyItemNode(BTreeNode node) { if (node != null && node.isLeaf()) { return node; } return this.findMinKeyItemNode(node.getChild(0)); } private void removeFromLeaf(BTreeNode delNode, int delKeyIndex) { // 2：要删除的关键字在叶子节点上的情况：先把这个关键字删除掉，然后再调整 delNode.removeKeyItem(delKeyIndex); // 3：调整情况： this.afterRomve(delNode); } /** * 删除识别数据后的调整 * * @param delNode */ private void afterRomve(BTreeNode delNode) { int n = delNode.getNumItems(); // int minM = (int) (Math.ceil(m/2.0)-1); int minM = (int) (Math.ceil(m / 2)); if (minM % 2 == 0) { minM = minM - 1; } // （1）如果被删关键字所在结点的原关键字个数n≥ceil(m/2)，说明删去该关键字后 // 该结点仍满足B树的定义，直接删除，不做调整 if (n >= minM) {
		}
		// （2）如果被删关键字所在结点的关键字个数n=ceil(m/2)-1，说明删去该关键字后
		// 该结点将不满足B树的定义，需要调整，过程为：如果其左右兄弟结点中有“多
		// 余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目大于
		// ceil(m/2)。则可将右（左）兄弟结点中最小（大）关键字上移至父结点，而将
		// 父结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中
		else if (n == (minM - 1)) {
			BTreeNode rightBrotherNode = this.rightBrotherNode(delNode);
			BTreeNode leftBrotherNode = this.leftBrotherNode(delNode);

if (rightBrotherNode != null && rightBrotherNode.getNumItems() > minM) {

KeyItem right = rightBrotherNode.getItem(0);
				rightBrotherNode.removeKeyItem(0);
				// 在父节点当中查找要插入的位置
				int inParentIndex = delNode.getParent().getNumItems() - 1;
				for (int i = 0; i < delNode.getParent().getNumItems(); i++) { if (delNode.getParent().getItem(i).getId() > right.getId()) {
						inParentIndex = i;
						break;
					}
				}
				delNode.insertKeyItem(delNode.getParent().getItem(inParentIndex));
				delNode.getParent().removeKeyItem(inParentIndex);
				delNode.getParent().insertKeyItem(right);

// 同时原来rightBrotherNode的第一个child，就应该成为delNode里面最大的child
				delNode.getChildNode()[delNode.getNumItems()] = rightBrotherNode.getChild(0);

if (rightBrotherNode.getChild(0) != null) {
					delNode.getChildNode()[delNode.getNumItems()].setParent(delNode);
				}

for (int i = 1; i < (rightBrotherNode.getNumItems() + 2); i++) { rightBrotherNode.getChildNode()[i - 1] = rightBrotherNode.getChild(i); } } else if (leftBrotherNode != null && leftBrotherNode.getNumItems() > minM) {
				BTreeNode leftMaxChild = leftBrotherNode.getChild(leftBrotherNode.getNumItems());
				KeyItem leftMaxKeyItem = leftBrotherNode.removeKeyItem();

// 在父节点当中查找要插入的位置
				int inParentIndex = delNode.getParent().getNumItems() - 1;
				for (int i = 0; i < delNode.getParent().getNumItems(); i++) { if (delNode.getParent().getItem(i).getId() > leftMaxKeyItem.getId()) {
						inParentIndex = i;
						break;
					}
				}

delNode.insertKeyItem(delNode.getParent().getItem(inParentIndex));
				delNode.getParent().removeKeyItem(inParentIndex);
				delNode.getParent().insertKeyItem(leftMaxKeyItem);

// 同时原来leftBrotherNode的最后一个child，就应该成为delNode里面第一个child
				for (int i = (delNode.getNumItems() - 1); i >= 0; i--) {
					delNode.getChildNode()[i + 1] = delNode.getChildNode()[i];
				}

delNode.getChildNode()[0] = leftMaxChild;

if (leftMaxChild != null) {
					leftMaxChild.setParent(delNode);
				}

} else {
				// （3）如果左右兄弟结点中没有“多余”的关键字，需把要删除关键字的结点与其左
				// （或右）兄弟结点以及父结点中分割二者的关键字合并成一个结点，即在删除关
				// 键字后，该结点中剩余的关键字，加上父结点中的关键字Ki一起，合并到Ci所指
				// 的兄弟结点中去。如果因此使父结点中关键字个数小于ceil(m/2)，则对此父结
				// 点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。
				BTreeNode parent = delNode.getParent();
				if (leftBrotherNode != null) {
					
					// 在父节点当中查找分割关键字的位置
					int inParentIndex = 0;
					for (inParentIndex = 0; inParentIndex < delNode.getParent().getNumItems(); inParentIndex++) { if (delNode.getParent().getItem(inParentIndex).getId() > leftBrotherNode.getItem(0).getId()) {
							break;
						}
					}
					
					inParentIndex = (inParentIndex+1 > parent.getNumItems()) ? parent.getNumItems():(inParentIndex+1);
					
					BTreeNode ci = parent.getChild(inParentIndex-1);
					for (int i = 0; i < delNode.getNumItems(); i++) { if (delNode.getItem(i)!=null && delNode.getItem(i).getId()>0) {
							ci.insertKeyItem(delNode.getItem(i));
						}
					}
					
					ci.insertKeyItem(parent.getItem(inParentIndex-1));
					
					int oldNumItems = parent.getNumItems();
					parent.removeKeyItem(inParentIndex-1);
					
					for (int i = inParentIndex; i < oldNumItems; i++) { parent.getChildNode()[i] = parent.getChildNode()[i+1]; parent.getChildNode()[i+1] = null; } if (oldNumItems == inParentIndex) { parent.getChildNode()[oldNumItems] = null; } //ci的children应该是ci原来的child+delNode的child ListtempList = new ArrayList<>();
					for (int i = 0; i < ci.getChildNode().length; i++) { if (ci.getChild(i)==null || ci.getChild(i).getNumItems()==0) { break; } tempList.add(ci.getChild(i)); } for (int i = 0; i < delNode.getChildNode().length; i++) { if (delNode.getChild(i)==null || delNode.getChild(i).getNumItems()==0) { break; } tempList.add(delNode.getChild(i)); } //设置新的ci的children BTreeNode[] ciChildren = new BTreeNode[ci.getNumItems()+1]; for (int i = 0; i < tempList.size(); i++) { ciChildren[i] = tempList.get(i); ciChildren[i].setParent(ci); } ci.setChildNode(ciChildren); //如果父节点是根元素的话，需要设置新的根 if (parent.getNumItems()==0 && parent == root) { root = ci; return; } }else if (rightBrotherNode!=null) { // 在父节点当中查找分割关键字的位置 int inParentIndex = parent.getNumItems()-1; for (int i = 0; i < delNode.getParent().getNumItems(); i++) { if (delNode.getParent().getItem(i).getId() > rightBrotherNode.getItem(0).getId()) {
							inParentIndex = i;
							break;
						}
					}
					
					inParentIndex = (inParentIndex-1 < 0) ? 0:(inParentIndex-1); BTreeNode ci = parent.getChild(inParentIndex+1); for (int i = 0; i < delNode.getNumItems(); i++) { if (delNode.getItem(i)!=null && delNode.getItem(i).getId()>0) {
							ci.insertKeyItem(delNode.getItem(i));
						}
					}
					
					ci.insertKeyItem(parent.getItem(inParentIndex));
					
					int oldNumItems = parent.getNumItems();
					parent.removeKeyItem(inParentIndex);
					
					for (int i = inParentIndex+1; i <= oldNumItems; i++) { parent.getChildNode()[i-1] = parent.getChildNode()[i]; parent.getChildNode()[i] = null; } //ci的children应该是delNode原来的child+ci的child ListtempList = new ArrayList<>();
					
					for (int i = 0; i < delNode.getChildNode().length; i++) { if (delNode.getChild(i)==null || delNode.getChild(i).getNumItems()==0) { break; } tempList.add(delNode.getChild(i)); } for (int i = 0; i < ci.getChildNode().length; i++) { if (ci.getChild(i)==null || ci.getChild(i).getNumItems()==0) { break; } tempList.add(ci.getChild(i)); } //设置新的ci的children BTreeNode[] ciChildren = new BTreeNode[ci.getNumItems()+1]; for (int i = 0; i < tempList.size(); i++) { ciChildren[i] = tempList.get(i); ciChildren[i].setParent(ci); } ci.setChildNode(ciChildren); //如果父节点是根元素的话，需要设置新的根 if (parent.getNumItems()==0 && parent == root) { root = ci; return; } } //递归处理父节点 if (parent!=null) { this.afterRomve(parent); } } } } /** * 获取一个节点的右兄 * * @param node * @return */ private BTreeNode rightBrotherNode(BTreeNode node) { if (node != root) { int nodeIndex = -1; for (int i = 0; i < node.getParent().getChildNode().length; i++) { if (node.getParent().getChild(i) == node) { nodeIndex = i; break; } } if (nodeIndex < (m - 1)) { return node.getParent().getChild(nodeIndex + 1); } } return null; } /** * 获取一个节点的左兄 * * @param node * @return */ private BTreeNode leftBrotherNode(BTreeNode node) { if (node != root) { int nodeIndex = -1; for (int i = 0; i < node.getParent().getChildNode().length; i++) { if (node.getParent().getChild(i) == node) { nodeIndex = i; break; } } if (nodeIndex > 0) {
				return node.getParent().getChild(nodeIndex - 1);
			}
		}
		return null;
	}

public static void main(String[] args) {
		BTree tree234 = new BTree(5);
		tree234.insert(20);
		tree234.insert(10);
		tree234.insert(15);
		tree234.insert(19);
		tree234.insert(8);
		tree234.insert(13);
		tree234.insert(30);
		tree234.insert(40);
		tree234.insert(50);
		tree234.insert(38);
		tree234.insert(9);
		
		tree234.removeKeyItem(8);
		tree234.removeKeyItem(9);
		tree234.removeKeyItem(20);
		tree234.removeKeyItem(19);

tree234.printTree(tree234.root, 0, 0);
	}

}
</pre>

B+tree这里没有实现，不知道大家对于B-tree理解之后能不能自己写出B+tree，后面我们再继续完成B+tree，敬请期待吧！

<h1>
	 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
</h1>

看完你肯定会写代码！

</node.getnumitems()+1;>
 </node.getitems()[i].getid())></pre>