B树的java源码实现 - JAVA

* 将给定的子节点追加到该节点的末尾。
*
* @param child - 给定的子节点
*/
public void addChild(BTreeNode child)
{
children.add(child);
}

/**
* 删除该节点中给定索引位置的子节点。
*

* 你需要自己保证给定的索引是合法的。
*
* @param index - 给定的索引
*/
public void removeChild(int index)
{
children.remove(index);
}

/**
* 将给定的子节点插入到该节点中给定索引
* 的位置。
*
* @param child - 给定的子节点
* @param index - 子节点带插入的位置
*/
public void insertChild(BTreeNode child, int index)
{
List newChildren = new ArrayList();
int i = 0;
for(; i < index; ++ i)
newChildren.add(children.get(i));
newChildren.add(child);
for(; i < children.size(); ++ i)
newChildren.add(children.get(i));
children = newChildren;
}
}

private static final int DEFAULT_T = 2;

/** B树的根节点 */
private BTreeNode root;
/** 根据B树的定义，B树的每个非根节点的关键字数n满足(t - 1) <= n <= (2t - 1) */
private int t = DEFAULT_T;
/** 非根节点中最小的键值数 */
private int minKeySize = t - 1;
/** 非根节点中最大的键值数 */
private int maxKeySize = 2*t - 1;

public BTree()
{
root = new BTreeNode();
root.setLeaf(true);
}

public BTree(int t)
{
this();
this.t = t;
minKeySize = t - 1;
maxKeySize = 2*t - 1;
}

/**
* 搜索给定的key。
*

* TODO 需要重新定义返回结果，应该返回
* key对应的值。
*
* @param key - 给定的键值
* @return TODO 得返回值类型
*/
public int search(Integer key)
{
return search(root, key);
}

/**
* 在以给定节点为根的子树中，递归搜索
* 给定的key
*
* @param node - 子树的根节点
* @param key - 给定的键值
* @return TODO
*/

private static int search(BTreeNode node, Integer key)
{
SearchResult result = node.searchKey(key);
if(result.getResult())
return result.getIndex();
else
{
if(node.isLeaf())
return -1;
else
search(node.childAt(result.getIndex()), key);

}
return -1;
}

/**
* 分裂一个满子节点childNode。
*

* 你需要自己保证给定的子节点是满节点。
*
* @param parentNode - 父节点
* @param childNode - 满子节点
* @param index - 满子节点在父节点中的索引
*/
private void splitNode(BTreeNode parentNode, BTreeNode childNode, int index)
{
assert childNode.size() == maxKeySize;

BTreeNode siblingNode = new BTreeNode();
siblingNode.setLeaf(childNode.isLeaf());
// 将满子节点中索引为[t, 2t - 2]的(t - 1)个关键字插入新的节点中
for(int i = 0; i < minKeySize; ++ i)
siblingNode.addKey(childNode.keyAt(t + i));
// 提取满子节点中的中间关键字，其索引为(t - 1)
Integer key = childNode.keyAt(t - 1);
// 删除满子节点中索引为[t - 1, 2t - 2]的t个关键字
for(int i = maxKeySize - 1; i >= t - 1; -- i)
childNode.removeKey(i);
if(!childNode.isLeaf()) // 如果满子节点不是叶节点，则还需要处理其子节点
{
// 将满子节点中索引为[t, 2t - 1]的t个子节点插入新的节点中
for(int i = 0; i < minKeySize + 1; ++ i)
siblingNode.addChild(childNode.childAt(t + i));
// 删除满子节点中索引为[t, 2t - 1]的t个子节点
for(int i = maxKeySize; i >= t; -- i)
childNode.removeChild(i);
}
// 将key插入父节点
parentNode.insertKey(key, index);
// 将新节点插入父节点
parentNode.insertChild(siblingNode, index + 1);
}

/**
* 在一个非满节点中插入给定的key。
*
* @param node - 非满节点
* @param key - 给定的键值
*/
private void insertNotFull(BTreeNode node, Integer key)
{
assert node.size() < maxKeySize;

if(node.isLeaf()) // 如果是叶子节点，直接插入
node.insertKey(key);
else
{
/* 找到key在给定节点应该插入的位置，那么key应该插入
* 该位置对应的子树中
*/
SearchResult result = node.searchKey(key);
BTreeNode childNode = node.childAt(result.getIndex());
if(childNode.size() == 2*t - 1) // 如果子节点是满节点
{
// 则先分裂
splitNode(node, childNode, result.getIndex());
/* 如果给定的key大于分裂之后新生成的键值，则需要插入该新键值的右边，
* 否则左边。
*/
if(key > node.keyAt(result.getIndex()))
childNode = node.childAt(result.getIndex() + 1);
}
insertNotFull(childNode, key);
}
}

/**
* 在B树中插入给定的

B树的java源码实现(八)