B树的java源码实现 - JAVA

B树是为磁盘或其他直接存取辅助存储设置而设计的一种平衡查找树。其能够有效降低磁盘I/O操作次数。许多数据库系统使用B树或B树的变形来储存信息。清明节这几天闲来无事，参考《算法导论》第二版第十八章的思想使用java语言实现了一颗简单的B树，在此跟大家分享下，就当是抛砖引玉，欢迎大家跟我讨论。

[java] package com.discover;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
* 一颗B树的简单实现。
*

* 其实现原理参考《算法导论》第二版第十八章。
*

* 如果大家想读懂这些源代码，不妨先看看上述章节。
*
* @author WangPing
*
* @param - 键类型
* @param - 值类型
*/
public class BTree
{
private static Log logger = LogFactory.getLog(BTree.class);

/**
* 在B树节点中搜索给定键值的返回结果。
*

* 该结果有两部分组成。第一部分表示此次查找是否成功，
* 如果查找成功，第二部分表示给定键值在B树节点中的位置，
* 如果查找失败，第二部分表示给定键值应该插入的位置。
*/
private static class SearchResult
{
private boolean result;
private int index;

public SearchResult(boolean result, int index)
{
this.result = result;
this.index = index;
}

public boolean getResult()
{
return result;
}

public int getIndex()
{
return index;
}
}

/**
* 为了简单起见，暂时只支持整型的key，
* 等到工作完成后，支持泛型。
*

*
* TODO 需要考虑并发情况下的存取。
*/
private static class BTreeNode
{
/** 节点的关键字，以非降序存放 */
private List keys;
/** 内节点的子节点 */
private List children;
/** 是否为叶子节点 */
private boolean leaf;

public BTreeNode()
{
keys = new ArrayList();
children = new ArrayList();
leaf = false;
}

public boolean isLeaf()
{
return leaf;
}

public void setLeaf(boolean leaf)
{
this.leaf = leaf;
}

/**
* 返回关键字的个数。如果是非叶子节点，该节点的
* 子节点个数为({@link #size()} + 1)。
*
* @return 关键字的个数
*/
public int size()
{
return keys.size();
}

/**
* 在节点中查找给定的key，如果节点中存在给定的
* key，则返回一个SearchResult，
* 标识此次查找成功，给定key在节点中的索引和给定
* key对应的值。如果不存在，则返回SearchResult
* 标识此次查找失败，给定key应该插入的位置，该key
* 对应的值为null。
*

* 如果查找失败，返回结果中的索引域为[0, {@link #size()}]；
* 如果查找成功，返回结果中的索引域为[0, {@link #size()} - 1]
*

* 这是一个二分查找算法，可以保证时间复杂度为O(log(t))。
*
* @param key - 给定的键值
* @return - 查找结果
*/
public SearchResult searchKey(Integer key)
{
int l = 0;
int h = keys.size() - 1;
int mid = 0;
while(l <= h)
{
mid = (l + h) / 2; // 先这么写吧，BTree实现中，l+h不可能溢出
if(keys.get(mid) == key)
break;
else if(keys.get(mid) > key)
h = mid - 1;
else // if(keys.get(mid) < key)
l = mid + 1;
}
boolean result = false;
int index = 0;
if(l <= h) // 说明查找成功
{
result = true;
index = mid; // index表示元素所在的位置
}
else
{
result = false;
index = l; // index

B树的java源码实现(一)