B樹的java源碼實現

B樹是為磁盤或其他直接存取輔助存儲設置而設計的一種平衡查找樹。其能夠有效降低磁盤I/O操作次數。許多數據庫系統使用B樹或B樹的變形來儲存信息。參考《算法導論》第二版第十八章的思想使用java語言實現了一顆簡單的B樹，在此跟大家分享下：

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樹的簡單實現。
<p/>
其實現原理參考《算法導論》第二版第十八章。
<p/>
如果大家想讀懂這些源代碼，不妨先看看上述章節。

@author WangPing
*
@param <K> - 鍵類型
@param <V> - 值類型
*/
public class BTree<K, V>
{
 private static Log logger = LogFactory.getLog(BTree.class);
/**

在B樹節點中搜索給定鍵值的返回結果。
<p/> 
該結果有兩部分組成。第一部分表示此次查找是否成功，
如果查找成功，第二部分表示給定鍵值在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，
等到工作完成后，支持泛型。 
<p/>

TODO 需要考慮并發情況下的存取。
/
private static class BTreeNode
{
 /** 節點的關鍵字，以非降序存放 /
 private List<Integer> keys;
 / 內節點的子節點 */
 private List<BTreeNode> children;
 / 是否為葉子節點 */
 private boolean leaf;
public BTreeNode()
 {

 keys = new ArrayList<Integer>();
 children = new ArrayList<BTreeNode>();
 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();
}
/**

在節點中查找給定的<code>key</code>，如果節點中存在給定的
<code>key</code>，則返回一個<code>SearchResult</code>，
標識此次查找成功，給定<code>key</code>在節點中的索引和給定
<code>key</code>對應的值。如果不存在，則返回<code>SearchResult</code>
標識此次查找失敗，給定<code>key</code>應該插入的位置，該<code>key</code>
對應的值為null。
<p/>
如果查找失敗，返回結果中的索引域為[0, {@link #size()}]；
如果查找成功，返回結果中的索引域為[0, {@link #size()} - 1]
<p/>
這是一個二分查找算法，可以保證時間復雜度為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表示元素應該插入的位置

}
 return new SearchResult(result, index);
}
/**

將給定的<code>key</code>追加到節點的末尾，
一定要確保調用該方法之后，節點中的關鍵字還是
以非降序存放。

@param key - 給定的鍵值
*/
public void addKey(Integer key)
{
 keys.add(key);
}
/**

刪除給定索引的鍵值。
<p/>
你需要自己保證給定的索引是合法的。

@param index - 給定的索引
*/
public void removeKey(int index)
{
 keys.remove(index);
}
/**

得到節點中給定索引的鍵值。
<p/>
你需要自己保證給定的索引是合法的。

@param index - 給定的索引
@return 節點中給定索引的鍵值
*/
public Integer keyAt(int index)
{
 return keys.get(index);
}
/**

在該節點中插入給定的<code>key</code>，
該方法保證插入之后，其鍵值還是以非降序存放。
<p/>
不過該方法的時間復雜度為O(t)。
<p/>
TODO 需要考慮鍵值是否可以重復。

@param key - 給定的鍵值
*/
public void insertKey(Integer key)
{
 SearchResult result = searchKey(key);
 insertKey(key, result.getIndex());
}
/**

在該節點中給定索引的位置插入給定的<code>key</code>，
你需要自己保證<code>key</code>插入了正確的位置。

@param key - 給定的鍵值
@param index - 給定的索引
/
public void insertKey(Integer key, int index)
{
 / TODO

通過新建一個ArrayList來實現插入真的很惡心，先這樣吧
要是有類似C中的reallocate就好了。
*/
List<Integer> newKeys = new ArrayList<Integer>();
int i = 0;
// index = 0或者index = keys.size()都沒有問題
for(; i < index; ++ i)
 newKeys.add(keys.get(i));
newKeys.add(key);
for(; i < keys.size(); ++ i)
 newKeys.add(keys.get(i));
keys = newKeys;
}


/**

返回節點中給定索引的子節點。
<p/>
你需要自己保證給定的索引是合法的。

@param index - 給定的索引
@return 給定索引對應的子節點
*/
public BTreeNode childAt(int index)
{
 if(isLeaf())

 throw new UnsupportedOperationException("Leaf node doesn't have children.");

return children.get(index);
}
/**

將給定的子節點追加到該節點的末尾。

@param child - 給定的子節點
*/
public void addChild(BTreeNode child)
{
 children.add(child);
}
/**

刪除該節點中給定索引位置的子節點。
</p>
你需要自己保證給定的索引是合法的。

@param index - 給定的索引
*/
public void removeChild(int index)
{
 children.remove(index);
}
/**

將給定的子節點插入到該節點中給定索引
的位置。

@param child - 給定的子節點
@param index - 子節點帶插入的位置
*/
public void insertChild(BTreeNode child, int index)
{
 List<BTreeNode> newChildren = new ArrayList<BTreeNode>();
 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;
}
/**

搜索給定的<code>key</code>。
<p/>
TODO 需要重新定義返回結果，應該返回
<code>key</code>對應的值。

@param key - 給定的鍵值
@return TODO 得返回值類型
*/
public int search(Integer key)
{
 return search(root, key);
}
/**

在以給定節點為根的子樹中，遞歸搜索
給定的<code>key</code>

@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;
}
/**

分裂一個滿子節點<code>childNode</code>。
<p/>
你需要自己保證給定的子節點是滿節點。

@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);
}
/**

在一個非滿節點中插入給定的<code>key</code>。

@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樹中插入給定的<code>key</code>。

@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樹中刪除一個給定的<code>key</code>。

@param key - 給定的鍵值
*/
public void delete(Integer key)
{
 // root的情況還需要做一些特殊處理
 delete(root, key);
}
/**

從以給定<code>node</code>為根的子樹中刪除指定的<code>key</code>。
<p/>
刪除的實現思想請參考《算法導論》第二版的第18章。
<p/>
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個關鍵字
     BTreeNode rightChildNode = node.childAt(result.getIndex() + 1);
     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)
 {
 if(siblingIndex < result.getIndex()) // 左兄弟節點滿足條件
 {
     childNode.insertKey(node.keyAt(siblingIndex), 0);
     node.removeKey(siblingIndex);
     node.insertKey(siblingNode.keyAt(siblingNode.size() - 1), siblingIndex);
     siblingNode.removeKey(siblingNode.size() - 1);
     // 將左兄弟節點的最后一個孩子移到childNode
     if(!siblingNode.isLeaf())
     {
         childNode.insertChild(siblingNode.childAt(siblingNode.size()), 0);
         siblingNode.removeChild(siblingNode.size());
     }
 }
 else // 右兄弟節點滿足條件
 {
     childNode.insertKey(node.keyAt(result.getIndex()), childNode.size() - 1);
     node.removeKey(result.getIndex());
     node.insertKey(siblingNode.keyAt(0), result.getIndex());
     siblingNode.removeKey(0);
     // 將右兄弟節點的第一個孩子移到childNode
     // childNode.insertChild(siblingNode.childAt(0), childNode.size() + 1);
     if(!siblingNode.isLeaf())
     {
         childNode.addChild(siblingNode.childAt(0));
         siblingNode.removeChild(0);
     }
 }
 delete(childNode, key);

 }
 else // 3.b 如果其相鄰左右節點都包含t-1個關鍵字
 {
 if(result.getIndex() < node.size()) // 存在右兄弟
 {
     BTreeNode rightSiblingNode = node.childAt(result.getIndex() + 1);
     childNode.addKey(node.keyAt(result.getIndex()));
     node.removeKey(result.getIndex());
     node.removeChild(result.getIndex() + 1);
     for(int i = 0; i < rightSiblingNode.size(); ++ i)
         childNode.addKey(rightSiblingNode.keyAt(i));
     if(!rightSiblingNode.isLeaf())
     {
         for(int i = 0; i <= rightSiblingNode.size(); ++ i)
             childNode.addChild(rightSiblingNode.childAt(i));
     }
 }
 else // 存在左節點
 {
     BTreeNode leftSiblingNode = node.childAt(result.getIndex() - 1);
     childNode.addKey(node.keyAt(result.getIndex() - 1));
     node.removeKey(result.getIndex() - 1);
     node.removeChild(result.getIndex() - 1);
     for(int i = leftSiblingNode.size() - 1; i >= 0; -- i)
         childNode.insertKey(leftSiblingNode.keyAt(i), 0);
     if(!leftSiblingNode.isLeaf())
     {
         for(int i = leftSiblingNode.size(); i >= 0; -- i)
             childNode.insertChild(leftSiblingNode.childAt(i), 0);
     }
 }
 // 如果node是root并且node不包含任何關鍵字了
 if(node == root && node.size() == 0)
     root = childNode;
 delete(childNode, key);

 }
}
}
}



/**

一個簡單的層次遍歷B樹實現，用于輸出B樹。
<p/>
TODO 待改進，使顯示更加形象化。
*/
public void output()
{
 Queue<BTreeNode> queue = new LinkedList<BTreeNode>();
 queue.offer(root);
 while(!queue.isEmpty())
 {

 BTreeNode node = queue.poll();
 for(int i = 0; i < node.size(); ++ i)
     System.out.print(node.keyAt(i) + " ");
 System.out.println();
 if(!node.isLeaf())
 {
     for(int i = 0; i <= node.size(); ++ i)
         queue.offer(node.childAt(i));
 }

}
}
public static void main(String[] args)
{
 Random random = new Random();
 BTree<Integer, Byte[]> btree = new BTree<Integer, Byte[]>();
 for(int i = 0; i < 10; ++ i)
 {

 int r = random.nextInt(100);
 System.out.println(r);
 btree.insert(r);

}
 System.out.println("----------------------");
 btree.output();
}
}</pre>轉自：http://blog.csdn.net/wangpingfang/article/details/7426943