key。*
* @param key - 给定的键值
*/
public void insert(Integer key)
{
if(root.size() == maxKeySize) // 如果根节点满了，则B树长高
{
BTreeNode newRoot = new BTreeNode();
newRoot.setLeaf(false);
newRoot.addChild(root);
splitNode(newRoot, root, 0);
root = newRoot;
}
insertNotFull(root, key);
}
/**
* 从B树中删除一个给定的
key。*
* @param key - 给定的键值
*/
public void delete(Integer key)
{
// root的情况还需要做一些特殊处理
delete(root, key);
}
/**
* 从以给定
node为根的子树中删除指定的key。*
* 删除的实现思想请参考《算法导论》第二版的第18章。
*
* TODO 需要重构，代码太长了
*
* @param node - 给定的节点
* @param key - 给定的键值
*/
public void delete(BTreeNode node, Integer key)
{
// 该过程需要保证，对非根节点执行删除操作时，其关键字个数至少为t。
assert node.size() >= t || node == root;
SearchResult result = node.searchKey(key);
/*
* 因为这是查找成功的情况，0 <= result.getIndex() <= (node.size() - 1)，
* 因此(result.getIndex() + 1)不会溢出。
*/
if(result.getResult())
{
// 1.如果关键字在节点node中，并且是叶节点，则直接删除。
if(node.isLeaf())
node.removeKey(result.getIndex());
else
{
// 2.a 如果节点node中前于key的子节点包含至少t个关键字
BTreeNode leftChildNode = node.childAt(result.getIndex());
if(leftChildNode.size() >= t)
{
// 使用leftChildNode中的最后一个键值代替node中的key
node.removeKey(result.getIndex());
node.insertKey(leftChildNode.keyAt(leftChildNode.size() - 1), result.getIndex());
delete(leftChildNode, leftChildNode.keyAt(leftChildNode.size() - 1));
// node.
}
else
{
// 2.b 如果节点node中后于key的子节点包含至少t个关键字
if(rightChildNode.size() >= t)
{
// 使用rightChildNode中的第一个键值代替node中的key
node.removeKey(result.getIndex());
node.insertKey(rightChildNode.keyAt(0), result.getIndex());
delete(rightChildNode, rightChildNode.keyAt(0));
}
else // 2.c 前于key和后于key的子节点都只包含t-1个关键字
{
node.removeKey(result.getIndex());
node.removeChild(result.getIndex() + 1);
// 将key和rightChildNode中的键值合并进leftChildNode
leftChildNode.addKey(key);
for(int i = 0; i < rightChildNode.size(); ++ i)
leftChildNode.addKey(rightChildNode.keyAt(i));
// 将rightChildNode中的子节点合并进leftChildNode，如果有的话
if(!rightChildNode.isLeaf())
{
for(int i = 0; i <= rightChildNode.size(); ++ i)
leftChildNode.addChild(rightChildNode.childAt(i));
}
delete(leftChildNode, key);
}
}
}
}
else
{
/*
* 因为这是查找失败的情况，0 <= result.getIndex() <= node.size()，
* 因此(result.getIndex() + 1)会溢出。
*/
if(node.isLeaf()) // 如果关键字不在节点node中，并且是叶节点，则什么都不做，因为该关键字不在该B树中
{
logger.info("The key: " + key + " isn't in this BTree.");
return;
}
BTreeNode childNode = node.childAt(result.getIndex());
if(childNode.size() >= t)
delete(childNode, key); // 递归删除
else // 3
{
// 先查找右边的兄弟节点
BTreeNode siblingNode = null;
int siblingIndex = -1;
if(result.getIndex() < node.size()) // 存在右兄弟节点
{
if(node.childAt(result.getIndex() + 1).size() >= t)
{
siblingNode = node.childAt(result.getIndex() + 1);
siblingIndex = result.getIndex() + 1;
}
}
// 如果右边的兄弟节点不符合条件，则试试左边的兄弟节点
if(siblingNode == null)
{
if(result.getIndex() > 0) // 存在左兄弟节点
{
if(node.childAt(result.getIndex() - 1).size() >= t)
{
siblingNode = node.childAt(result.getIndex() - 1);
siblingIndex = result.getIndex() - 1;
}
}
}
// 3.a 有一个相邻兄弟节点至少包含t个关键字
if(siblingNode != null)