很楠不爱3

这个屌丝很懒，什么也没留下！

热门标签

第十三课常见的非二叉树：B树、B+树、B*树

作者：很楠不爱3 | 2024-03-01 00:02:14

踩

非二叉树

1 B树

1.1 背景

磁盘由一个单片或者一组多个盘片组成盘组，每个盘片有两个面，然后盘面上有许多称为磁道的圆圈，数据就是存储在这些磁道上的，磁盘驱动器进行数据读写时，盘片绕着中间的主轴旋转，当磁道绕过读写头（磁头：可以简单理解为连接磁盘和内存的其中一端，就是移动臂的一端），就可以进行数据读写了，磁盘上数据必须用一个三维地址唯一标示：柱面号、盘面号、块号(磁道上的盘块)，读写磁盘分三个步骤：
（1）定位或者查找柱面
移动臂根据柱面号使磁头移动到所需要的柱面上，一般是盘组，所以这里就缺点了每个盘面上位置一样的磁道
（2）根据盘面号来确定指定盘面上的磁道
（3）盘片开始旋转，将指定块号的磁道段移动至磁头下

时间分析：步骤1是查找时间，代价最高，达到0.1s左右，步骤3是等待时间，这个比较快，旋转一圈大约0.0083s，传输时间：数据从总线传输到内存

磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间Ts。所以就出现了B数。

1.2 定义

因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，所以B-树就是B数，并不是另外一种树。

1.2.1 用阶定义:

B 树又叫平衡多路查找树, 一棵m阶的B 树特性如下：

（1）树中每个结点最多含有m个孩子（m>=2）；

（2）除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；

（3）若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；

（4）所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；（读者反馈@冷岳：这里有错，叶子节点只是没有孩子和指向孩子的指针，这些节点也存在，也有元素。@研究者July：其实，关键是把什么当做叶子结点，因为如红黑树中，每一个NULL指针即当做叶子结点，只是没画出来而已）。

（5）每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，…，Kn，Pn)。其中：
a) Ki (i=1…n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

注：节点的关键字数比孩子数少一个

1.2.2 用度定义

B树中每一个结点能包含的关键字数有一个上界和下界。这个下界可以用一个称作B树的最小度数（最小度数即内节点中节点最小孩子数目）m（m>=2）表示，用关键字，也就是度来讨论：
（1）每个非根的内结点至少有m个子女，每个非根的结点必须至少含有m-1个关键字，如果树是非空的，则根结点至少包含一个关键字；

（2）每个结点可包含至多2m-1个关键字。所以一个内结点至多可有2m个子女。如果一个结点恰好有2m-1个关键字，我们就说这个结点是满的（而稍后介绍的B树作为B树的一种常用变形，B树中要求每个内结点至少为2/3满，而不是像这里的B树所要求的至少半满）；

（3）当关键字数m=2（t=2的意思是，mmin=2，m可以>=2）时的B树是最简单的，但他也不是二叉树

结合背景，我们知道B树中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小，根据磁盘驱动(disk drives)的不同，一般块的大小在1k~4k左右)；假设一个盘块正好存放一个B树的节点，那么查找某个节点的数据，就需要进行磁盘IO一次盘块到内存，那么树的高度就相当于IO的次数了，这样树的高度降低了，这就意味着查找一个元素只要很少结点从外存磁盘中读入内存（这个过程就是磁盘IO），很快访问到要查找的数据，就是说利用B树可以大大降低磁盘IO的次数，因为一个节点可以存很多东西，大大降低了树的高度。

1.3 常用操作

1.3.1 插入

注意： Max(keyNum)=M-1
分裂:插入一个关键码，导致关键码数大于节点最大允许的关键字数M-1，那么就要将该节点进行分裂为两个节点，然后将排在中间的关键码提升到父节点中去。

插入只发生在叶节点：
（1）若该结点中关键码个数小于M-1，则直接插入。

（2）如该结点中关键码个数等于M-1，则将引起结点的分裂。以中间关键码为界将结点一分为二，产生一个新结点，并把中间关键码插入到父结点（h-1层）中。

（3）向父亲结点插入中间关键字的时候，重复以上两个步骤最坏情况一直分裂到根结点，建立一个新的根结点，整个B树增加一层

1.3.2 删除

注意： Min(keyNum)=M/2-1

合并：如果一个节点删除某个关键码后，该节点的关键码数小于最小的关键码数M/2-1，如果不在叶子节点，他的前驱或者后继就是他的继任者，继任者取代他后，删除他的继任者，而他的继任者一定在叶子节点，所以删除最终要考虑的就是在叶子怎么去删除一个节点：
如果兄弟等于M/2-1就合并，就是将父节点中的关键码下降做为中间关键码，并且和删除关键码的节点和他的兄弟节点进行合并成一个节点；否则就不需合并，说明某个兄弟的关键码数大于最小的M/2-1,只需要将父关键码下降到删除节点中，将兄弟节点提升到父节点中即可

1）删除操作的两个步骤
　第一步骤：在树中查找被删关键字K所在的地点
　第二步骤：进行删去K的操作

（2）删去K的操作
　B-树是二叉排序树的推广，中序遍历B-树同样可得到关键字的有序序列（具体遍历算法【参见练习】）。任一关键字K的中序前趋(后继)必是K的左子树(右子树)中最右(左)下的结点中最后(最前)一个关键字。若被删关键字K所在的结点非树叶，则用K的中序前趋(或后继)S代K，然后从叶子中删去S,那么就相等于我们要考虑的就是在叶子删除一个节点（可能是自己活着他的继任者）。从叶子*x开始删去某关键字K的三种情形为：

1）情形一：若x->keynum>Min，则只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作结束。

2）情形二：若x->keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。若x的左(或右)邻兄弟结点y中的关键字数目大于Min，则将y中的最大(或最小)关键字上移至双亲结点parent中，而将parent中相应的关键字下移至x中。显然这种移动使得双亲中关键字数目不变；y被移出一个关键字，故其keynum减1，因它原大于Min，故减少1个关键字后keynum仍大于等于Min；而x中已移入一个关键字，故删K后x中仍有Min个关键字。涉及移动关键字的三个结点均满足B-树的性质(3)。请读者验证，上述操作后仍满足B-树的性质(1)。移动完成后，删除过程亦结束。

3）情形三：若x及其相邻的左右兄弟(也可能只有一个兄弟)中的关键字数目均为最小值Min，则上述的移动操作就不奏效，此时须x和左或右兄弟合并。不妨设x有右邻兄弟y(对左邻兄弟的讨论与此类似)，在x中删去K后，将双亲结点parent中介于x和y之间的关键字K，作为中间关键字，与并x和y中的关键字一起"合并"为一个新的结点取代x和y。因为x和y原各有Min个关键字，从双亲中移人的K’抵消了从x中删除的K，故新结点中恰有2Min(即2「m/2」-2≤m-1)个关键字，没有破坏B-树的性质(3)。但由于K’从双亲中移到新结点后，相当于从parent中删去了K’，若parent->keynum原大于Min，则删除操作到此结束；否则，同样要通过移动parent的左右兄弟中的关键字或将*parent与其左右兄弟合并的方法来维护B-树性质。最坏情况下，合并操作会向上传播至根，当根中只有一个关键字时，合并操作将会使根结点及其两个孩子合并成一个新的根，从而使整棵树的高度减少一层。如图:

1.4 代码实现

/**
*定义B树的节点
*/
class BTNode<K extends Comparable<K>, V> {
 
	// 构成B树的最小度数
	public final static int MIN_DEGREE = 3;
	// 除根节点外，每个结点中总键数的下限
	public final static int LOWER_BOUND_KEYNUM = MIN_DEGREE - 1;
	// 包含根节点外，每个结点中总键数的上限
	public final static int UPPER_BOUND_KEYNUM = (MIN_DEGREE * 2) - 1;
 
	protected boolean mIsLeaf;// 标记此节点是否为叶子结点
	protected int mCurrentKeyNum;// 此节点的键数量计数器
	protected BTKeyValue<K, V>[] mKeys;// 用于存键值对的数组
	protected BTNode<K, V>[] mChildren;// 用于存子结点的数组
 
	/**
	 * 构造函数
	 */
	@SuppressWarnings("unchecked")
	public BTNode() {
		mIsLeaf = true;
		mCurrentKeyNum = 0;
		mKeys = new BTKeyValue[UPPER_BOUND_KEYNUM];
		mChildren = new BTNode[UPPER_BOUND_KEYNUM + 1];
	}
 
	protected static BTNode<?, ?> getChildNodeAtIndex(BTNode<?, ?> btNode, int keyIdx, int nDirection) {
		if (btNode.mIsLeaf) {
			return null;
		}
		keyIdx += nDirection;
		if ((keyIdx < 0) || (keyIdx > btNode.mCurrentKeyNum)) {
			throw new IllegalArgumentException();
		}
 
		return btNode.mChildren[keyIdx];
	}
 
	/**
	 * 返回btNode节点中位于keyIdx位上的键左边的子结点
	 * @param btNode
	 * @param keyIdx
	 * @return
	 */
	protected static BTNode<?, ?> getLeftChildAtIndex(BTNode<?, ?> btNode, int keyIdx) {
		return getChildNodeAtIndex(btNode, keyIdx, 0);
	}
 
	/**
	 * 返回btNode节点中位于keyIdx位上的键右边的子结点
	 * @param btNode
	 * @param keyIdx
	 * @return
	 */
	protected static BTNode<?, ?> getRightChildAtIndex(BTNode<?, ?> btNode, int keyIdx) {
		return getChildNodeAtIndex(btNode, keyIdx, 1);
	}
 
	/**
	 * @param parentNode
	 * @param keyIdx
	 * @return 返回父结点的keyIdx位上的子结点的左兄弟结点
	 */
	protected static BTNode<?, ?> getLeftSiblingAtIndex(BTNode<?, ?> parentNode, int keyIdx) {
		return getChildNodeAtIndex(parentNode, keyIdx, -1);
	}
 
	/**
	 * 
	 * @param parentNode
	 * @param keyIdx
	 * @return	返回父结点的keyIdx位上的子结点的右兄弟结点
	 */
	protected static BTNode<?, ?> getRightSiblingAtIndex(BTNode<?, ?> parentNode, int keyIdx) {
		return getChildNodeAtIndex(parentNode, keyIdx, 1);
	}
	
	
	/**
	 * 判断父结点的keyIdx位上的子结点是否存在左兄弟结点
	 * @param parentNode
	 * @param keyIdx
	 * @return
	 */
	protected static boolean hasLeftSiblingAtIndex(BTNode<?, ?> parentNode, int keyIdx) {
		if (keyIdx - 1 < 0) {
			return false;
		} else {
			return true;
		}
	}
	
	/**
	 * 判断父结点的keyIdx位上的子结点是否存在右兄弟结点
	 * @param parentNode
	 * @param keyIdx
	 * @return
	 */
	protected static boolean hasRightSiblingAtIndex(BTNode<?, ?> parentNode, int keyIdx) {
		if (keyIdx + 1 > parentNode.mCurrentKeyNum) {
			return false;
		} else {
			return true;
		}
	}
}


/**
 * 定义存键值对
 * 
 */
class BTKeyValue<K extends Comparable<K>, V> {
 
	protected K mKey;
	protected V mValue;
 
	public BTKeyValue(K mKey, V mValue) {
		super();
		this.mKey = mKey;
		this.mValue = mValue;
	}
}


/**
*定义B树
*/

public class BTree<K extends Comparable<K>, V> {

   //定义根节点
   private BTNode mRoot;


	/**
	 * 查找
	 * 
	 * @param key
	 * @return 若键存在，则返回键所对应的值。若键不存在，则抛出异常。
	 */
	public V search(K key) {
 
		checkKey(key);
 
		BTNode<K, V> currentNode = mRoot;
 
		// 迭代查找每一个可能存储key的结点
		while (currentNode != null) {
			int possibleIdx = binarySearch(currentNode, key);
			BTKeyValue<K, V> possibleKeyValue = null;
			// 判断二分查找返回位置索引处的元素是否为查找的元素，若是则返回其值，如不是，则迭代到下一个可能的结点中查找
			if (possibleIdx < currentNode.mCurrentKeyNum && key.compareTo(
                                                (possibleKeyValue = currentNode.mKeys[possibleIdx]).mKey) == 0) {
				return possibleKeyValue.mValue;
			} else {
				currentNode = currentNode.mChildren[possibleIdx];
			}
		}
		return null;
	}
	
	
    /**
	 * 插入
	 * 
	 * @param key   键不允许为null
	 * @param value
	 */
	public void insert(K key, V value) {
 
		checkKey(key);
 
		if (mRoot == null) {
			mRoot = createNode();
		}
		// 使用递归的方法将键-值对插入到BTree结构中
		mRoot = insert(mRoot, key, value);
 
	}
	
	/**
	 * 删除
	 * @param key
	 * @return
	 */
	public V deleteKey(K key) {
 
		checkKey(key);
 
		V v = search(key);
		// 递归的删除键key
		mRoot = deleteKey(mRoot, key);
		return v;
	}
 
 
 	/**
	 * 用二分查找法查找结点中键的位置，若找到返回键的位置，若没找到，则返回键应该插入的位置
	 * 
	 * @param btNode
	 * @param key
	 * @return
	 */
	private int binarySearch(BTNode<K, V> btNode, K key) {
		BTKeyValue<K, V>[] keys = btNode.mKeys;
		int lo = 0;
		int hi = btNode.mCurrentKeyNum - 1;
		while (lo <= hi) {
			int mid = (hi - lo) / 2 + lo;
			int cmp = key.compareTo(keys[mid].mKey);
			if (cmp == 0) {
				return mid;
			} else if (cmp > 0) {
				lo = mid + 1;
			} else if (cmp < 0) {
				hi = mid - 1;
			}
		}
		return lo;
	}

	/**
	 * 递归插入方法
	 * 
	 * @param x     要插入到的结点
	 * @param key
	 * @param value
	 * @return
	 */
	private BTNode<K, V> insert(BTNode<K, V> x, K key, V value) {
 
		// 1.首先判断此节点是否已经为满，若满，则将此节点分裂
		if (x.mCurrentKeyNum == BTNode.UPPER_BOUND_KEYNUM) {
			x = split(x);
		}
		// 2.对没有满的结点进行键值对的查找，找出可能的键值对索引，和可能的键值对
		int possibleIdx = binarySearch(x, key);
		/*
		 * 由于第一步操作会确定当前节点为非满结点，故不用担心数组越界问题(不然试想，当此结点已满，且要插入的键大于此节点中所有键，
		 * 故possibleIdx的值会等于UPPER_BOUND_KEYNUM，故造成越界)
		 */
		BTKeyValue<K, V> possibleKeyValue = x.mKeys[possibleIdx];
		/*
		 * 3.判断可能的键值对中的键是否与要插入的键相同（当要插入的键大于当前结点中所有的键时，possibleKeyValue取值为x.mKeys[x.
		 * mCurrentKeyNum]为null，故要判断possibleKeyValue的值是否为空，以防止空指针异常）
		 * 如果相同则直接替换当前值为插入值，并返回当前结点(用于更新)
		 */
		if (possibleKeyValue != null && key.compareTo(possibleKeyValue.mKey) == 0) {
			possibleKeyValue.mValue = value;
			return x;
		}
		/*
		 * 4.当前节点为叶子节点时，直接插入（由于在最前边进行了当前结点是否为满的判断，并做了相应的处理，故到此步插入键值对后，此节点最多为满，且不会溢出）
		 * 当前结点不为叶子结点时，递归到下一个可能的结点继续寻找、插入
		 */
		if (x.mIsLeaf) {
			// 4.1
			for (int i = x.mCurrentKeyNum; i > possibleIdx; i--) {
				x.mKeys[i] = x.mKeys[i - 1];
			}
			x.mKeys[possibleIdx] = new BTKeyValue<>(key, value);
			x.mCurrentKeyNum++;
			mSize++;
		} else {
			// 4.2
			BTNode<K, V> t = insert(x.mChildren[possibleIdx], key, value);
			/*
			 * 4.3判断当返回的结点中的键值对数量为1时，说明返回的结点经过了分裂，故需要将其合并到当前节点中（同上理，合并后，当前结点最多为满）
			 */
			if (t.mCurrentKeyNum == 1) {
				// 4.3.1移动当前节点中的键值对为要合并的键值对腾出地方，并存入
				for (int i = x.mCurrentKeyNum; i > possibleIdx; i--) {
					x.mKeys[i] = x.mKeys[i - 1];
				}
				x.mKeys[possibleIdx] = t.mKeys[0];
				// 4.3.2移动当前节点中的子结点为要合并的子结点腾出地方，并存入
				for (int i = x.mCurrentKeyNum + 1; i > possibleIdx + 1; i--) {
					x.mChildren[i] = x.mChildren[i - 1];
				}
				x.mChildren[possibleIdx] = t.mChildren[0];
				x.mChildren[possibleIdx + 1] = t.mChildren[1];
				// 4.3.3更新当前结点的键值对计数器
				x.mCurrentKeyNum++;
			}
		}
		return x;
	}



	/**
	 * @param x
	 * @param key
	 * @return
	 */
	private BTNode<K, V> deleteKey(BTNode<K, V> x, K key) {
 
		// 1.获取要删除的键可能处在当前结点上的索引位置
		int possibleIdx = binarySearch(x, key);
 
		// 2.根据当前结点是否为叶子结点分情况讨论
		if (x.mIsLeaf == true) {
			// 2.1当前结点为叶子节点
 
			if (possibleIdx < x.mCurrentKeyNum && key.compareTo(x.mKeys[possibleIdx].mKey) == 0) {
				// 2.1.1判断在当前结点上possible索引位置上的键是否与要删除的键相等（前提是possible索引小于当前节点键的数量，负责会出现空指针异常）
				// 如果相等，则直接删除此键，否则，此键不存在树中，不做任何操作
 
				for (int i = possibleIdx; i < x.mCurrentKeyNum - 1; i++) {
					x.mKeys[i] = x.mKeys[i + 1];
				}
				x.mKeys[x.mCurrentKeyNum - 1] = null;
				x.mCurrentKeyNum--;
				mSize--;
			}
		} else {
			// 2.2当前结点不为子结点
			if (possibleIdx < x.mCurrentKeyNum && key.compareTo(x.mKeys[possibleIdx].mKey) == 0) {
				// 2.2.1判断在当前结点上possible索引位置上的键是否与要删除的键相等（前提是possible索引小于当前节点键的数量，负责会出现空指针异常）
				// 如果成立，用possible索引处的子结点的最大键替换要删除的键
 
				// 1）记住possilbe索引处子结点的最大键
				BTKeyValue<K, V> keyNeedToSwim = maxKey(x.mChildren[possibleIdx]);
 
				// 2）将1）中记住的键删除
				x = deleteKey(x, keyNeedToSwim.mKey);
 
				// 3）将key替换为记住的键
				possibleIdx = binarySearch(x, key);
				x.mKeys[possibleIdx] = keyNeedToSwim;
 
			} else {
				// 2.2.2
				// 如果不成立，递归的在possible索引处子结点上删除键key
 
				// 递归删除
				BTNode<K, V> t = deleteKey(x.mChildren[possibleIdx], key);
 
				// 检测删除后返回结点的状态，如果不满足键数量>=最低度数-1，则酌情旋转或合并
				if (t.mCurrentKeyNum < BTNode.LOWER_BOUND_KEYNUM) {
					// 不满足键数量>=最低度数-1
 
					// 判断返回结点的兄弟结点的状况，若兄弟结点的键数量>最低度数-1，则旋转（向兄弟结点借键），若兄弟结点的键数量<=最低度数-1，则与兄弟结点合并
					if (BTNode.hasLeftSiblingAtIndex(x, possibleIdx)) {
						if (BTNode.getLeftSiblingAtIndex(x, possibleIdx).mCurrentKeyNum > BTNode.LOWER_BOUND_KEYNUM) {
							leftRotate(x, possibleIdx);
						} else {
							leftMerge(x, possibleIdx);
						}
					} else if (BTNode.hasRightSiblingAtIndex(x, possibleIdx)) {
						if (BTNode.getRightSiblingAtIndex(x, possibleIdx).mCurrentKeyNum > BTNode.LOWER_BOUND_KEYNUM) {
							rightRotate(x, possibleIdx);
						} else {
							rightMerge(x, possibleIdx);
						}
					}
 
					// 判断删完后根节点是否没有键存在，若没有，则将根节点重新赋值
					if (x == mRoot && x.mCurrentKeyNum == 0) {
						x = x.mChildren[0];
					}
				}
			}
		}
		return x;
	}


	/**
	 * @return
	 */
	public BTKeyValue<K, V> minKey() {
		return minKey(mRoot);
	}
 
	/**
	 * @param x
	 * @return
	 */
	private BTKeyValue<K, V> minKey(BTNode<K, V> x) {
		if (x == null) {
			return null;
		}
		if (x.mChildren[0] != null) {
			return minKey(x.mChildren[0]);
		} else {
			return x.mKeys[0];
		}
	}
 
	/**
	 * @return
	 */
	public BTKeyValue<K, V> maxKey() {
		return maxKey(mRoot);
	}
 
	/**
	 * @param x
	 * @return
	 */
	private BTKeyValue<K, V> maxKey(BTNode<K, V> x) {
		if (x == null) {
			return null;
		}
		if (x.mChildren[x.mCurrentKeyNum] != null) {
			return maxKey(x.mChildren[x.mCurrentKeyNum]);
		} else {
			return x.mKeys[x.mCurrentKeyNum - 1];
		}
	}
/**
	 * 将满结点x分裂为含有一个键值对的父结点和两个子结点，并返回父结点的链接
	 * 
	 * @param x
	 * @return
	 */
	private BTNode<K, V> split(BTNode<K, V> x) {
		int mid = x.mCurrentKeyNum / 2;
 
		BTNode<K, V> left = new BTNode<>();
		for (int i = 0; i < mid; i++) {
			left.mKeys[i] = x.mKeys[i];
			left.mChildren[i] = x.mChildren[i];
		}
		left.mChildren[mid] = x.mChildren[mid];
		left.mIsLeaf = x.mIsLeaf;
		left.mCurrentKeyNum = mid;
 
		BTNode<K, V> right = new BTNode<>();
		for (int i = mid + 1; i < x.mCurrentKeyNum; i++) {
			right.mKeys[i - mid - 1] = x.mKeys[i];
			right.mChildren[i - mid - 1] = x.mChildren[i];
		}
		right.mChildren[x.mCurrentKeyNum - mid - 1] = x.mChildren[x.mCurrentKeyNum];
		right.mIsLeaf = x.mIsLeaf;
		right.mCurrentKeyNum = x.mCurrentKeyNum - mid - 1;
 
		BTNode<K, V> top = new BTNode<>();
		top.mCurrentKeyNum = 1;
		top.mIsLeaf = false;
		top.mKeys[0] = x.mKeys[mid];
		top.mChildren[0] = left;
		top.mChildren[1] = right;
		return top;
	}


/**
	 * 从右结点借一个键值对过来
	 * 
	 * @param x
	 * @param possibleIdx
	 * @return
	 */
	private BTNode<K, V> rightRotate(BTNode<K, V> x, int possibleIdx) {
 
		// 获取右节点和右节点中最小的键值对
		BTNode<K, V> rightNode = x.mChildren[possibleIdx + 1];
		BTKeyValue<K, V> rightKey = rightNode.mKeys[0];
		// 获取右节点中最小的结点
		BTNode<K, V> rightFirstNode = rightNode.mChildren[0];
		// 获取父结点交换位置的键值对
		BTKeyValue<K, V> topKey = x.mKeys[possibleIdx];
		// 获取需补齐键值对的节点，并将父结点交换位置的键值对加到此节点的最高位
		BTNode<K, V> possibleNode = x.mChildren[possibleIdx];
		possibleNode.mKeys[possibleNode.mCurrentKeyNum] = topKey;
		// 将右节点中最小的结点添加到此节点
		possibleNode.mChildren[possibleNode.mCurrentKeyNum + 1] = rightFirstNode;
		possibleNode.mCurrentKeyNum++;
 
		// 将父结点拿走键值对的位置填上右节点提出的键值对
		x.mKeys[possibleIdx] = rightKey;
		// 将右节点提出的键值对和最小结点在右节点中删除
		for (int i = 1; i < rightNode.mCurrentKeyNum; i++) {
			rightNode.mKeys[i - 1] = rightNode.mKeys[i];
		}
		rightNode.mKeys[rightNode.mCurrentKeyNum - 1] = null;
		for (int i = 1; i < rightNode.mCurrentKeyNum + 1; i++) {
			rightNode.mChildren[i - 1] = rightNode.mChildren[i];
		}
		rightNode.mChildren[rightNode.mCurrentKeyNum] = null;
		rightNode.mCurrentKeyNum--;
		return x;
	}
 
	/**
	 * ‘
	 * 
	 * @param x           父结点
	 * @param possibleIdx 需要补充键值对的子结点的索引
	 * @return
	 */
	private BTNode<K, V> leftRotate(BTNode<K, V> x, int possibleIdx) {
 
		// 获取左节点和左节点中最大的键值对
		BTNode<K, V> leftNode = x.mChildren[possibleIdx - 1];
		BTKeyValue<K, V> leftKey = leftNode.mKeys[leftNode.mCurrentKeyNum - 1];
		// 获取左节点中最大的结点
		BTNode<K, V> leftLastNode = leftNode.mChildren[leftNode.mCurrentKeyNum];
		// 获取父结点交换位置的键值对
		BTKeyValue<K, V> topKey = x.mKeys[possibleIdx - 1];
		// 获取需补齐键值对的节点，并移动其中的键值对将最低位空出来：以用来填充从父结点交换过来的键值对
		BTNode<K, V> possibleNode = x.mChildren[possibleIdx];
		for (int i = possibleNode.mCurrentKeyNum; i > 0; i--) {
			possibleNode.mKeys[i] = possibleNode.mKeys[i - 1];
		}
		// 同理对此节点的子结点
		for (int i = possibleNode.mCurrentKeyNum + 1; i > 0; i--) {
			possibleNode.mChildren[i] = possibleNode.mChildren[i - 1];
		}
		// 填充键值对和其带过来的链接，并将键数量计数器加1
		possibleNode.mKeys[0] = topKey;
		possibleNode.mChildren[0] = leftLastNode;
		possibleNode.mCurrentKeyNum++;
		// 将父结点拿走键值对的位置填上左节点提出的键值对
		x.mKeys[possibleIdx - 1] = leftKey;
		// 将左节点提出的键值对和子结点在左节点中删除
		leftNode.mKeys[leftNode.mCurrentKeyNum - 1] = null;
		leftNode.mChildren[leftNode.mCurrentKeyNum] = null;
		leftNode.mCurrentKeyNum--;
		return x;
	}

/**
	 * 合并父结点中位于possibleIdx和possibleIdx+1处的俩结点（由此可见可用执行做合并来完成右合并同样的任务）
	 * 
	 * @param x
	 * @param possibleIdx
	 * @return
	 */
	private BTNode<K, V> rightMerge(BTNode<K, V> x, int possibleIdx) {
		return leftMerge(x, possibleIdx + 1);
	}
 
	/**
	 * 合并父结点中位于possibleIdx和possibleIdx-1处的俩结点
	 * 
	 * @param x
	 * @param possibleIdx
	 * @return
	 */
	private BTNode<K, V> leftMerge(BTNode<K, V> x, int possibleIdx) {
		// 获取左节点
		BTNode<K, V> leftNode = x.mChildren[possibleIdx - 1];
		// 获取父结点要合并到左节点的键值对
		BTKeyValue<K, V> topKey = x.mKeys[possibleIdx - 1];
		// 获取需要合并的结点
		BTNode<K, V> possibleNode = x.mChildren[possibleIdx];
		// 将父结点获取的键值对放入左节点
		leftNode.mKeys[leftNode.mCurrentKeyNum] = topKey;
		// 将需要合并的结点的键值对全部放入左节点
		for (int i = 0; i < possibleNode.mCurrentKeyNum; i++) {
			leftNode.mKeys[i + leftNode.mCurrentKeyNum + 1] = possibleNode.mKeys[i];
		}
		// 同理，将结点链接也移过来
		for (int i = 0; i < possibleNode.mCurrentKeyNum + 1; i++) {
			leftNode.mChildren[i + leftNode.mCurrentKeyNum + 1] = possibleNode.mChildren[i];
		}
		// 更新左节点的键值对计数器
		leftNode.mCurrentKeyNum += 1 + possibleNode.mCurrentKeyNum;
		// 更新父结点
		for (int i = possibleIdx; i < x.mCurrentKeyNum; i++) {
			x.mKeys[i - 1] = x.mKeys[i];
		}
		x.mKeys[x.mCurrentKeyNum - 1] = null;
		for (int i = possibleIdx; i < x.mCurrentKeyNum; i++) {
			x.mChildren[i] = x.mChildren[i + 1];
		}
		x.mChildren[x.mCurrentKeyNum] = null;
		x.mCurrentKeyNum--;
		return x;
	}
	
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578

2 B+树

2.1 定义

是应文件系统所需而产生的一种B-tree的变形树，更适合实际应用中操作系统的文件索引和数据库索引。
（1）有n棵子树的结点中含有n个关键字，这个和B树不同
（2）所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接，而B 树的叶子节点并没有包括全部需要查找的信息

（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字，而B 树的非终节点也包含需要查找的有效信息。

2.2 B+树出现的原因

更适合实际应用中操作系统的文件索引和数据库索引
（1）B±tree的磁盘读写代价更低，提高了磁盘的IO性能
B±tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了

（2）B±tree的查询效率更加稳定
B树没有解决元素遍历的效率低下的问题， B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作

2.3 常用操作

2.3.1 插入

分裂：和B树的一样
当一个结点满（关键码数超过M）,分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针，插入都是在叶子节点

（1）当叶子节点的关键码数不满（超过M），内部节点不满
直接将关键码插入叶子节点
（2）当叶子节点的关键码数满（超过M），内部节点不满
插入后将叶子节点拆分，小于中间关键码的放新的左节点，大于等于中间关键码的放新的右节点，将中间关键码放入内部节点（索引节点）中

（3）当叶子节点的关键码满，内部节点也满
插入后将叶子节点拆分，小于中间关键码的放新的左节点，大于等于中间关键码的放新的右节点，将中间关键码放入内部节点（索引节点）中；继续递归拆分内部节点

2.3.2 删除

合并：和B树的一样
如果一个节点删除某个关键码后，该节点的关键码数小于最小的关键码数M/2，
如果兄弟等于M/2就合并，直接和兄弟节点合并成一个新的节点，同时删除父节点中的关键码；否则就不需要合并，只是需要从兄弟节点借一个节点过来，然后修改父节点的关键码，注意删除一定在叶子节点，因为关键码全都存在叶子节点，内部节点只是存索引

（1）当叶子节点的关键码数不低于填充因子（M/2）,内部节点也是不低于
直接删除关键码，如果该关键码还是内部节点的索引，也要在内部节点删除他

（2）当叶子节点的关键码数低于填充因子（M/2）,内部节点不低于
如果叶子节点的兄弟节点关键码数大于M/2，那么就从兄弟节点借，否则就和他的兄弟节点合并；然后修改内部节点的关键码

（3）当叶子节点的关键码数低于填充因子（M/2）,内部节点也低于
如果叶子节点的兄弟节点关键码数大于M/2，那么就从兄弟节点借，否则就和他的兄弟节点合并；然后修改内部节点的关键码；内部节点也类似处理

2.4 代码实现

/**
 * B+树
 *
 */

public class BPlusTree<K extends Comparable<K>, V> {

    // 根节点
    protected BPlusNode<K, V> root;

    // 阶数，M值
    protected int order;

    // 叶子节点的链表头
    protected BPlusNode<K, V> head;

    // 树高
    protected int height = 0;

    public BPlusNode<K, V> getHead() {
        return head;
    }

    public void setHead(BPlusNode<K, V> head) {
        this.head = head;
    }

    public BPlusNode<K, V> getRoot() {
        return root;
    }

    public void setRoot(BPlusNode<K, V> root) {
        this.root = root;
    }

    public int getOrder() {
        return order;
    }

    public void setOrder(int order) {
        this.order = order;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public int getHeight() {
        return height;
    }

    public V get(K key) {
        return root.get(key);
    }

    public V remove(K key) {
        return root.remove(key, this);
    }

    public void insertOrUpdate(K key, V value) {
        root.insertOrUpdate(key, value, this);
    }

    public BPlusTree(int order) {
        if (order < 3) {
            System.out.print("order must be greater than 2");
            System.exit(0);
        }
        this.order = order;
        root = new BPlusNode<K, V>(true, true);
        head = root;
    }

    public void printBPlusTree() {
        this.root.printBPlusTree(0);
    }
}


class BPlusNode<K extends Comparable<K>, V> {

    // 是否为叶子节点
    protected boolean isLeaf;

    // 是否为根节点
    protected boolean isRoot;

    // 父节点
    protected BPlusNode<K, V> parent;

    // 叶节点的前节点
    protected BPlusNode<K, V> previous;

    // 叶节点的后节点
    protected BPlusNode<K, V> next;

    // 节点的关键字列表
    protected List<Entry<K, V>> entries;

    // 子节点列表
    protected List<BPlusNode<K, V>> children;

    public BPlusNode(boolean isLeaf) {
        this.isLeaf = isLeaf;
        entries = new ArrayList();

        if (!isLeaf) {
            children = new ArrayList();
        }
    }

    public BPlusNode(boolean isLeaf, boolean isRoot) {
        this(isLeaf);
        this.isRoot = isRoot;
    }

    public V get(K key) {
        //如果是叶子节点 
        if (isLeaf) {
            int low = 0, high = entries.size() - 1, mid;
            int comp;
            while (low <= high) {
                mid = (low + high) / 2;
                comp = entries.get(mid).getKey().compareTo(key);
                if (comp == 0) {
                    return entries.get(mid).getValue();
                } else if (comp < 0) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            //未找到所要查询的对象 
            return null;
        }
        //如果不是叶子节点 
        //如果key小于节点最左边的key，沿第一个子节点继续搜索 
        if (key.compareTo(entries.get(0).getKey()) < 0) {
            return children.get(0).get(key);
            //如果key大于等于节点最右边的key，沿最后一个子节点继续搜索 
        } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {
            return children.get(children.size() - 1).get(key);
            //否则沿比key大的前一个子节点继续搜索 
        } else {
            int low = 0, high = entries.size() - 1, mid = 0;
            int comp;
            while (low <= high) {
                mid = (low + high) / 2;
                comp = entries.get(mid).getKey().compareTo(key);
                if (comp == 0) {
                    return children.get(mid + 1).get(key);
                } else if (comp < 0) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return children.get(low).get(key);
        }
    }

    public void insertOrUpdate(K key, V value, BPlusTree<K, V> tree) {
        //如果是叶子节点 
        if (isLeaf) {
            //不需要分裂，直接插入或更新 
            if (contains(key) != -1 || entries.size() < tree.getOrder()) {
                insertOrUpdate(key, value);
                if (tree.getHeight() == 0) {
                    tree.setHeight(1);
                }
                return;
            }
            //需要分裂 
            //分裂成左右两个节点 
            BPlusNode<K, V> left = new BPlusNode<K, V>(true);
            BPlusNode<K, V> right = new BPlusNode<K, V>(true);
            //设置链接 
            if (previous != null) {
                previous.next = left;
                left.previous = previous;
            }
            if (next != null) {
                next.previous = right;
                right.next = next;
            }
            if (previous == null) {
                tree.setHead(left);
            }

            left.next = right;
            right.previous = left;
            previous = null;
            next = null;

            //复制原节点关键字到分裂出来的新节点 
            copy2Nodes(key, value, left, right, tree);

            //如果不是根节点 
            if (parent != null) {
                //调整父子节点关系 
                int index = parent.children.indexOf(this);
                parent.children.remove(this);
                left.parent = parent;
                right.parent = parent;
                parent.children.add(index, left);
                parent.children.add(index + 1, right);
                parent.entries.add(index, right.entries.get(0));
                entries = null; //删除当前节点的关键字信息
                children = null; //删除当前节点的孩子节点引用

                //父节点插入或更新关键字 
                parent.updateInsert(tree);
                parent = null; //删除当前节点的父节点引用
                //如果是根节点     
            } else {
                isRoot = false;
                BPlusNode<K, V> parent = new BPlusNode<K, V>(false, true);
                tree.setRoot(parent);
                left.parent = parent;
                right.parent = parent;
                parent.children.add(left);
                parent.children.add(right);
                parent.entries.add(right.entries.get(0));
                entries = null;
                children = null;
            }
            return;

        }
        //如果不是叶子节点
        //如果key小于等于节点最左边的key，沿第一个子节点继续搜索 
        if (key.compareTo(entries.get(0).getKey()) < 0) {
            children.get(0).insertOrUpdate(key, value, tree);
            //如果key大于节点最右边的key，沿最后一个子节点继续搜索 
        } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {
            children.get(children.size() - 1).insertOrUpdate(key, value, tree);
            //否则沿比key大的前一个子节点继续搜索 
        } else {
            int low = 0, high = entries.size() - 1, mid = 0;
            int comp;
            while (low <= high) {
                mid = (low + high) / 2;
                comp = entries.get(mid).getKey().compareTo(key);
                if (comp == 0) {
                    children.get(mid + 1).insertOrUpdate(key, value, tree);
                    break;
                } else if (comp < 0) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            if (low > high) {
                children.get(low).insertOrUpdate(key, value, tree);
            }
        }
    }

    private void copy2Nodes(K key, V value, BPlusNode<K, V> left,
                            BPlusNode<K, V> right, BPlusTree<K, V> tree) {
        //左右两个节点关键字长度 
        int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2;
        boolean b = false;//用于记录新元素是否已经被插入
        for (int i = 0; i < entries.size(); i++) {
            if (leftSize != 0) {
                leftSize--;
                if (!b && entries.get(i).getKey().compareTo(key) > 0) {
                    left.entries.add(new SimpleEntry<K, V>(key, value));
                    b = true;
                    i--;
                } else {
                    left.entries.add(entries.get(i));
                }
            } else {
                if (!b && entries.get(i).getKey().compareTo(key) > 0) {
                    right.entries.add(new SimpleEntry<K, V>(key, value));
                    b = true;
                    i--;
                } else {
                    right.entries.add(entries.get(i));
                }
            }
        }
        if (!b) {
            right.entries.add(new SimpleEntry<K, V>(key, value));
        }
    }

    /**
     * 插入节点后中间节点的更新
     */
    protected void updateInsert(BPlusTree<K, V> tree) {

        //如果子节点数超出阶数，则需要分裂该节点    
        if (children.size() > tree.getOrder()) {
            //分裂成左右两个节点 
            BPlusNode<K, V> left = new BPlusNode<K, V>(false);
            BPlusNode<K, V> right = new BPlusNode<K, V>(false);
            //左右两个节点子节点的长度 
            int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2;
            int rightSize = (tree.getOrder() + 1) / 2;
            //复制子节点到分裂出来的新节点，并更新关键字 
            for (int i = 0; i < leftSize; i++) {
                left.children.add(children.get(i));
                children.get(i).parent = left;
            }
            for (int i = 0; i < rightSize; i++) {
                right.children.add(children.get(leftSize + i));
                children.get(leftSize + i).parent = right;
            }
            for (int i = 0; i < leftSize - 1; i++) {
                left.entries.add(entries.get(i));
            }
            for (int i = 0; i < rightSize - 1; i++) {
                right.entries.add(entries.get(leftSize + i));
            }

            //如果不是根节点 
            if (parent != null) {
                //调整父子节点关系 
                int index = parent.children.indexOf(this);
                parent.children.remove(this);
                left.parent = parent;
                right.parent = parent;
                parent.children.add(index, left);
                parent.children.add(index + 1, right);
                parent.entries.add(index, entries.get(leftSize - 1));
                entries = null;
                children = null;

                //父节点更新关键字 
                parent.updateInsert(tree);
                parent = null;
                //如果是根节点     
            } else {
                isRoot = false;
                BPlusNode<K, V> parent = new BPlusNode<K, V>(false, true);
                tree.setRoot(parent);
                tree.setHeight(tree.getHeight() + 1);
                left.parent = parent;
                right.parent = parent;
                parent.children.add(left);
                parent.children.add(right);
                parent.entries.add(entries.get(leftSize - 1));
                entries = null;
                children = null;
            }
        }
    }

    /**
     * 删除节点后中间节点的更新
     */
    protected void updateRemove(BPlusTree<K, V> tree) {

        // 如果子节点数小于M / 2或者小于2，则需要合并节点 
        if (children.size() < tree.getOrder() / 2 || children.size() < 2) {
            if (isRoot) {
                // 如果是根节点并且子节点数大于等于2，OK 
                if (children.size() >= 2) return;
                // 否则与子节点合并 
                BPlusNode<K, V> root = children.get(0);
                tree.setRoot(root);
                tree.setHeight(tree.getHeight() - 1);
                root.parent = null;
                root.isRoot = true;
                entries = null;
                children = null;
                return;
            }
            //计算前后节点  
            int currIdx = parent.children.indexOf(this);
            int prevIdx = currIdx - 1;
            int nextIdx = currIdx + 1;
            BPlusNode<K, V> previous = null, next = null;
            if (prevIdx >= 0) {
                previous = parent.children.get(prevIdx);
            }
            if (nextIdx < parent.children.size()) {
                next = parent.children.get(nextIdx);
            }

            // 如果前节点子节点数大于M / 2并且大于2，则从其处借补 
            if (previous != null
                    && previous.children.size() > tree.getOrder() / 2
                    && previous.children.size() > 2) {
                //前叶子节点末尾节点添加到首位 
                int idx = previous.children.size() - 1;
                BPlusNode<K, V> borrow = previous.children.get(idx);
                previous.children.remove(idx);
                borrow.parent = this;
                children.add(0, borrow);
                int preIndex = parent.children.indexOf(previous);

                entries.add(0, parent.entries.get(preIndex));
                parent.entries.set(preIndex, previous.entries.remove(idx - 1));
                return;
            }

            // 如果后节点子节点数大于M / 2并且大于2，则从其处借补
            if (next != null
                    && next.children.size() > tree.getOrder() / 2
                    && next.children.size() > 2) {
                //后叶子节点首位添加到末尾 
                BPlusNode<K, V> borrow = next.children.get(0);
                next.children.remove(0);
                borrow.parent = this;
                children.add(borrow);
                int preIndex = parent.children.indexOf(this);
                entries.add(parent.entries.get(preIndex));
                parent.entries.set(preIndex, next.entries.remove(0));
                return;
            }

            // 同前面节点合并 
            if (previous != null
                    && (previous.children.size() <= tree.getOrder() / 2
                    || previous.children.size() <= 2)) {
                for (int i = 0; i < children.size(); i++) {
                    previous.children.add(children.get(i));
                }
                for (int i = 0; i < previous.children.size(); i++) {
                    previous.children.get(i).parent = this;
                }
                int indexPre = parent.children.indexOf(previous);
                previous.entries.add(parent.entries.get(indexPre));
                for (int i = 0; i < entries.size(); i++) {
                    previous.entries.add(entries.get(i));
                }
                children = previous.children;
                entries = previous.entries;

                //更新父节点的关键字列表
                parent.children.remove(previous);
                previous.parent = null;
                previous.children = null;
                previous.entries = null;
                parent.entries.remove(parent.children.indexOf(this));
                if ((!parent.isRoot
                        && (parent.children.size() >= tree.getOrder() / 2
                        && parent.children.size() >= 2))
                        || parent.isRoot && parent.children.size() >= 2) {
                    return;
                }
                parent.updateRemove(tree);
                return;
            }

            // 同后面节点合并 
            if (next != null
                    && (next.children.size() <= tree.getOrder() / 2
                    || next.children.size() <= 2)) {
                for (int i = 0; i < next.children.size(); i++) {
                    BPlusNode<K, V> child = next.children.get(i);
                    children.add(child);
                    child.parent = this;
                }
                int index = parent.children.indexOf(this);
                entries.add(parent.entries.get(index));
                for (int i = 0; i < next.entries.size(); i++) {
                    entries.add(next.entries.get(i));
                }
                parent.children.remove(next);
                next.parent = null;
                next.children = null;
                next.entries = null;
                parent.entries.remove(parent.children.indexOf(this));
                if ((!parent.isRoot && (parent.children.size() >= tree.getOrder() / 2
                        && parent.children.size() >= 2))
                        || parent.isRoot && parent.children.size() >= 2) {
                    return;
                }
                parent.updateRemove(tree);
                return;
            }
        }
    }

    public V remove(K key, BPlusTree<K, V> tree) {
        //如果是叶子节点 
        if (isLeaf) {
            //如果不包含该关键字，则直接返回 
            if (contains(key) == -1) {
                return null;
            }
            //如果既是叶子节点又是根节点，直接删除 
            if (isRoot) {
                if (entries.size() == 1) {
                    tree.setHeight(0);
                }
                return remove(key);
            }
            //如果关键字数大于M / 2，直接删除 
            if (entries.size() > tree.getOrder() / 2 && entries.size() > 2) {
                return remove(key);
            }
            //如果自身关键字数小于M / 2，并且前节点关键字数大于M / 2，则从其处借补 
            if (previous != null &&
                    previous.parent == parent
                    && previous.entries.size() > tree.getOrder() / 2
                    && previous.entries.size() > 2) {
                //添加到首位 
                int size = previous.entries.size();
                entries.add(0, previous.entries.remove(size - 1));
                int index = parent.children.indexOf(previous);
                parent.entries.set(index, entries.get(0));
                return remove(key);
            }
            //如果自身关键字数小于M / 2，并且后节点关键字数大于M / 2，则从其处借补 
            if (next != null
                    && next.parent == parent
                    && next.entries.size() > tree.getOrder() / 2
                    && next.entries.size() > 2) {
                entries.add(next.entries.remove(0));
                int index = parent.children.indexOf(this);
                parent.entries.set(index, next.entries.get(0));
                return remove(key);
            }

            //同前面节点合并 
            if (previous != null
                    && previous.parent == parent
                    && (previous.entries.size() <= tree.getOrder() / 2
                    || previous.entries.size() <= 2)) {
                V returnValue = remove(key);
                for (int i = 0; i < entries.size(); i++) {
                    //将当前节点的关键字添加到前节点的末尾
                    previous.entries.add(entries.get(i));
                }
                entries = previous.entries;
                parent.children.remove(previous);
                previous.parent = null;
                previous.entries = null;
                //更新链表 
                if (previous.previous != null) {
                    BPlusNode<K, V> temp = previous;
                    temp.previous.next = this;
                    previous = temp.previous;
                    temp.previous = null;
                    temp.next = null;
                } else {
                    tree.setHead(this);
                    previous.next = null;
                    previous = null;
                }
                parent.entries.remove(parent.children.indexOf(this));
                if ((!parent.isRoot && (parent.children.size() >= tree.getOrder() / 2
                        && parent.children.size() >= 2))
                        || parent.isRoot && parent.children.size() >= 2) {
                    return returnValue;
                }
                parent.updateRemove(tree);
                return returnValue;
            }
            //同后面节点合并
            if (next != null
                    && next.parent == parent
                    && (next.entries.size() <= tree.getOrder() / 2
                    || next.entries.size() <= 2)) {
                V returnValue = remove(key);
                for (int i = 0; i < next.entries.size(); i++) {
                    //从首位开始添加到末尾 
                    entries.add(next.entries.get(i));
                }
                next.parent = null;
                next.entries = null;
                parent.children.remove(next);
                //更新链表 
                if (next.next != null) {
                    BPlusNode<K, V> temp = next;
                    temp.next.previous = this;
                    next = temp.next;
                    temp.previous = null;
                    temp.next = null;
                } else {
                    next.previous = null;
                    next = null;
                }
                //更新父节点的关键字列表
                parent.entries.remove(parent.children.indexOf(this));
                if ((!parent.isRoot && (parent.children.size() >= tree.getOrder() / 2
                        && parent.children.size() >= 2))
                        || parent.isRoot && parent.children.size() >= 2) {
                    return returnValue;
                }
                parent.updateRemove(tree);
                return returnValue;
            }
        }
        /*如果不是叶子节点*/

        //如果key小于等于节点最左边的key，沿第一个子节点继续搜索 
        if (key.compareTo(entries.get(0).getKey()) < 0) {
            return children.get(0).remove(key, tree);
            //如果key大于节点最右边的key，沿最后一个子节点继续搜索 
        } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {
            return children.get(children.size() - 1).remove(key, tree);
            //否则沿比key大的前一个子节点继续搜索 
        } else {
            int low = 0, high = entries.size() - 1, mid = 0;
            int comp;
            while (low <= high) {
                mid = (low + high) / 2;
                comp = entries.get(mid).getKey().compareTo(key);
                if (comp == 0) {
                    return children.get(mid + 1).remove(key, tree);
                } else if (comp < 0) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return children.get(low).remove(key, tree);
        }
    }

    // 判断当前节点是否包含该关键字
    protected int contains(K key) {
        int low = 0, high = entries.size() - 1, mid;
        int comp;
        while (low <= high) {
            mid = (low + high) / 2;
            comp = entries.get(mid).getKey().compareTo(key);
            if (comp == 0) {
                return mid;
            } else if (comp < 0) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    // 插入到当前节点的关键字中
    protected void insertOrUpdate(K key, V value) {
        //二叉查找，插入
        int low = 0, high = entries.size() - 1, mid;
        int comp;
        while (low <= high) {
            mid = (low + high) / 2;
            comp = entries.get(mid).getKey().compareTo(key);
            if (comp == 0) {
                entries.get(mid).setValue(value);
                break;
            } else if (comp < 0) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (low > high) {
            entries.add(low, new SimpleEntry<K, V>(key, value));
        }
    }

    // 删除节点
    protected V remove(K key) {
        int low = 0, high = entries.size() - 1, mid;
        int comp;
        while (low <= high) {
            mid = (low + high) / 2;
            comp = entries.get(mid).getKey().compareTo(key);
            if (comp == 0) {
                return entries.remove(mid).getValue();
            } else if (comp < 0) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return null;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("isRoot: ");
        sb.append(isRoot);
        sb.append(", ");
        sb.append("isLeaf: ");
        sb.append(isLeaf);
        sb.append(", ");
        sb.append("keys: ");
        for (Entry<K, V> entry : entries) {
            sb.append(entry.getKey());
            sb.append(", ");
        }
        sb.append(", ");
        return sb.toString();
    }

    public void printBPlusTree(int index) {
        if (this.isLeaf) {
            System.out.print("层级：" + index + ",叶子节点，keys为: ");
            for (int i = 0; i < entries.size(); ++i)
                System.out.print(entries.get(i) + " ");
            System.out.println();
        } else {
            System.out.print("层级：" + index + ",非叶子节点，keys为: ");
            for (int i = 0; i < entries.size(); ++i)
                System.out.print(entries.get(i) + " ");
            System.out.println();
            for (int i = 0; i < children.size(); ++i)
                children.get(i).printBPlusTree(index + 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707

3 B*树

3.1 定义

B*-tree是B±tree的变体，在B+树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，B树中非根和非叶子结点再增加指向兄弟的指针；B树定义了非叶子结点关键字个数至少为(2/3)*M（M假设为满关键字2m-1），即块的最低使用率为2/3（代替B+树的1/2）（假设一个节点放在一个块）

3.2 常用操作

暂略，稍后补上

3.3 代码实现

暂略，稍后补上

4 对比B树、B+树、B*树

假设是M阶,也就是最多M个孩子
（1）节点的关键字数量
B树：不小于M/2-1
B+树：不小于M/2
B树：不小于2/3
（2）节点的关键字数量和孩子节点数量是否相等
B树：不相等，孩子数=关键码+1
B+树：相等
B树：相等
（3）数据存放方式
B树：存在叶子和内部节点
B+树：只存在叶子，内部节点存放索引范围
B树：只存在叶子，内部节点存放索引范围
（4）链表指针
B树：不使用
B+树：叶子节点使用
B树：内部节点和叶子节点都使用

（5）他们的关系
B树：基础
B+树：基于B树变形
B*树：基于B+树变形

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/169466

第十三课 常见的非二叉树：B树、B+树、B*树

第十三课 常见的非二叉树：B树、B+树、B*树

1 B树

1.1 背景

1.2 定义

1.2.1 用阶定义:

1.2.2 用度定义

1.3 常用操作

1.3.1 插入

1.3.2 删除

1.4 代码实现

2 B+树

2.1 定义

2.2 B+树出现的原因

2.3 常用操作

2.3.1 插入

2.3.2 删除

2.4 代码实现

3 B*树

3.1 定义

3.2 常用操作

3.3 代码实现

4 对比B树、B+树、B*树

第十三课常见的非二叉树：B树、B+树、B*树

第十三课常见的非二叉树：B树、B+树、B*树