寫代碼之前，再回顧一下B樹是什麼，滿足什麼樣的規則
B樹規則：
- 排序方式：所有節點關鍵字是按遞增次序排列，并遵循左小右大原則
- 子節點數：非葉節點的子節點數>1，且<=M ，且M>=2，空樹除外（注：M階代表一個樹節點最多有多少個查找路徑，M=M路,當M=2則是2叉樹,M=3則是3叉）
- 關鍵字數：枝節點的關鍵字數量大于等于ceil(m/2)-1個且小于等于M-1個（注：ceil()是個朝正無窮方向取整的函數 如ceil(1.1)結果為2)
- 所有葉子節點均在同一層、葉子節點除了包含了關鍵字和關鍵字記錄的指針外也有指向其子節點的指針隻不過其指針位址都為null對應下圖最後一層節點的空格子
用一張圖來幫助了解B樹（為了友善了解，使用實際字母大小來排列）
B樹查詢流程
如上圖我要從上圖中找到E字母，查找流程如下
- 擷取根節點的關鍵字進行比較，目前根節點關鍵字為M，E<M（26個字母順序），是以往找到指向左邊的子節點（二分法規則，左小右大，左邊放小于目前節點值的子節點、右邊放大于目前節點值的子節點）
- 拿到關鍵字D和G，D<E<G 是以直接找到D和G中間的節點
- 拿到E和F，因為E=E 是以直接傳回關鍵字和指針資訊（如果樹結構裡面沒有包含所要查找的節點則傳回null）
B樹節點插入規則
拿一個5階樹舉例
- 節點拆分規則：目前是要組成一個5路查找樹，那麼此時m=5,關鍵字數必須<=5-1（這裡關鍵字數>4就要進行節點拆分）
- 排序規則：滿足節點本身比左邊節點大，比右邊節點小的排序規則
B樹節點删除規則
- 節點合并規則：目前是要組成一個5路查找樹，那麼此時m=5,關鍵字數必須大于等于ceil（5/2）（這裡關鍵字數<2就要進行節點合并）
- 滿足節點本身比左邊節點大，比右邊節點小的排序規則
- 關鍵字數小于二時先從子節點取，子節點沒有符合條件時就向向父節點取，取中間值往父節點放
B樹特點
B樹相對于平衡二叉樹的不同是，每個節點包含的關鍵字增多了，特别是在B樹應用到資料庫中的時候，資料庫充分利用了磁盤塊的原理（磁盤資料存儲是采用塊的形式存儲的，每個塊的大小為4K，每次IO進行資料讀取時，同一個磁盤塊的資料可以一次性讀取出來）把節點大小限制和充分使用在磁盤快大小範圍；把樹的節點關鍵字增多後樹的層級比原來的二叉樹少了，減少資料查找的次數和複雜度
講了許多，對于程式猿來說，還是上代碼實際
首先定義一個BTree，内部定義一個節點類
public class BTree<K, V> where K : IComparable<K>
{
private class Node
{
public Node Parent { get; set; }
public List<K> Keys { get; set; }
public List<V> Values { get; set; }
public List<Node> Children { get; set; }
/// <summary>
/// 向節點内部按照大小順序插入一個元素，
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
public void Insert(K key, V value)
{
var result = false;
for (var i = 0; i < Keys.Count; i++)
{
var compareValue = key.CompareTo(Keys[i]);
if (compareValue < 0)
{
Keys.Insert(i, key);
Values.Insert(i, value);
result = true;
break;
}
else if (compareValue == 0)
{
throw new Exception();
}
}
if (!result)
{
Keys.Add(key);
Values.Add(value);
}
}
public Node()
{
Keys = new List<K>();
Values = new List<V>();
Children = new List<Node>();
}
}
private int _level;
//單個節點包含key值數量的最小值（除了根節點外）
private int _minKeysCount;
private Node _first;
/// <summary>
/// B樹初始化
/// </summary>
/// <param name="level">表示單個節點包含的最大Key值數量</param>
public BTree(int level)
{
_level = level;
_minKeysCount = (int)(Math.Ceiling(_level / 2.0) - 1);
}
}
BTree中定義的_level表示樹的階數，_minKeysCount表示單個節點關鍵字最小數目
Node表示B樹中的一個節點，包含多個關鍵字和對應的Value值，還包含子節點的引用
插入節點
public void Insert(K key, V value)
{
if (_first == null)
{
_first = new Node();
_first.Insert(key, value);
}
else
{
var current = _first;
Insert(current, key, value);
}
}
private void Insert(Node current, K key, V value)
{
//如果目前節點是葉子節點，則直接插入到葉子節點，再看是否葉子節點需要分裂
if (current.Children.Count == 0)
{
if (current.Keys.Count > _level)
{
return;
}
current.Insert(key, value);
if (current.Keys.Count == _level)
{
Bubble(current);
}
}
else
{
//如果目前節點不是葉子節點，找出大于目前Key值的最小key對應的索引，找到對應的子節點，進行遞歸，直到找到最終的葉子節點
int childIndex = current.Keys.Count;
for (var i = 0; i < current.Keys.Count; i++)
{
var compareValue = key.CompareTo(current.Keys[i]);
if (compareValue < 0)
{
childIndex = i;
break;
}
else if (compareValue == 0)
{
throw new Exception();
}
}
current = current.Children[childIndex];
Insert(current, key, value);
}
}
/// <summary>
/// 冒泡
/// 當目前結點的個數等于階數的時候，就需要把目前結點的最中間的關鍵字放到父結點中去，
/// 目前結點分裂成兩個結點，小于中間結點的是左結點，大于中間結點的右結點，都作為子結點節點加到目前結點的父結點上面去，
/// 因為預設左結點的parent是父結點，是以隻需要加入右結點
/// 然後再判斷目前結點是否有子結點，如果有子結點 子結點個數必定超過了階數（因為子結點的個數總是比目前結點的關鍵字數大1）
/// 若有子結點 則還需要把子結點分成兩部分 一部分成為左結點的子結點 另一部分成為右結點的子結點 分界點就是目前結點最中間關鍵字所在位置
/// 然後遞歸執行，把關鍵字放到父結點中後，判斷父結點是否也需要冒泡分裂
/// </summary>
/// <param name="current"></param>
private void Bubble(Node current)
{
var middleIndex = (current.Keys.Count - 1) / 2;
var middleKey = current.Keys[middleIndex];
var middleValue = current.Values[middleIndex];
var newRightChild = new Node();
newRightChild.Parent = current.Parent;
for (var i = middleIndex + 1; i < current.Keys.Count; i++)
{
newRightChild.Keys.Add(current.Keys[i]);
newRightChild.Values.Add(current.Values[i]);
}
var newLeftChild = current;
var count = newLeftChild.Keys.Count - middleIndex;
newLeftChild.Keys.RemoveRange(middleIndex, count);
newLeftChild.Values.RemoveRange(middleIndex, count);
for (var i = middleIndex + 1; i < current.Children.Count;)
{
var temp = current.Children[i];
newRightChild.Children.Add(temp);
temp.Parent = newRightChild;
newLeftChild.Children.RemoveAt(i);
}
if (current.Parent == null)
{
current.Parent = new Node();
_first = current.Parent;
_first.Children.Add(newLeftChild);
_first.Children.Add(newRightChild);
newLeftChild.Parent = _first;
newRightChild.Parent = _first;
}
else
{
current.Parent.Children.Add(newRightChild);
}
current = current.Parent;
current.Insert(middleKey, middleValue);
if (current.Keys.Count >= _level)
{
Bubble(current);
}
}
查找節點
private Node Find(K key, out int index)
{
index = -1;
if (_first == null)
{
return null;
}
var current = _first;
while (true)
{
var childIndex = current.Keys.Count;
for (var i = 0; i < current.Keys.Count; i++)
{
var compareValue = key.CompareTo(current.Keys[i]);
if (compareValue < 0)
{
childIndex = i;
break;
}
else if (compareValue == 0)
{
index = i;
return current;
}
}
if (current.Children.Count > 0)
{
current = current.Children[childIndex];
}
else
{
return null;
}
};
}
public bool ContainsKey(K key)
{
return Find(key, out int index) != null;
}
删除節點
public void Remove(K key)
{
var current = Find(key, out int index);
if (current == null)
{
return;
}
current.Keys.RemoveAt(index);
current.Values.RemoveAt(index);
BorrowFromChild(current, index);
}
/// <summary>
/// 删除節點後，如果目前節點key的數目少于_minKeysCount，需要向子節點借一個key （類似于算術減法，低位數不夠向高位借）
/// </summary>
/// <param name="current"></param>
/// <param name="index"></param>
private void BorrowFromChild(Node current, int index)
{
if (current.Children.Count == 0)
{
if (current.Keys.Count < _minKeysCount)
{
BorrowFromParent(current);
}
return;
}
var leftChild = current.Children[index];
var rightChild = current.Children[index + 1];
if (rightChild.Keys.Count > _minKeysCount)
{
var childIndex = 0;
current.Keys.Insert(index, rightChild.Keys[childIndex]);
current.Values.Insert(index, rightChild.Values[childIndex]);
rightChild.Keys.RemoveAt(childIndex);
rightChild.Values.RemoveAt(childIndex);
}
else
{
//remove
var childIndex = leftChild.Keys.Count - 1;
current.Keys.Insert(index, leftChild.Keys[childIndex]);
current.Values.Insert(index, leftChild.Values[childIndex]);
leftChild.Keys.RemoveAt(childIndex);
leftChild.Values.RemoveAt(childIndex);
if (leftChild.Keys.Count < _minKeysCount)
{
BorrowFromChild(leftChild, childIndex);
}
}
}
/// <summary>
/// 葉子節點key的數目不夠時，需要向父節點借
/// </summary>
/// <param name="current"></param>
private void BorrowFromParent(Node current)
{
var parent = current.Parent;
if (parent == null)
{
//目前結點為根結點的話 不需要操作
return;
}
var index = parent.Children.IndexOf(current);
if (index > 0)
{
//若有左邊兄弟結點
var leftSibling = parent.Children[index - 1];
var leftKeysIndex = leftSibling.Keys.Count - 1;
if (leftKeysIndex >= _minKeysCount)
{
current.Keys.Insert(0, parent.Keys[index-1]);
current.Values.Insert(0, parent.Values[index-1]);
parent.Keys[index-1] = leftSibling.Keys[leftKeysIndex];
parent.Values[index-1] = leftSibling.Values[leftKeysIndex];
leftSibling.Keys.RemoveAt(leftKeysIndex);
leftSibling.Values.RemoveAt(leftKeysIndex);
return;
}
}
if (index < parent.Children.Count - 1)
{
var rightSibling = parent.Children[index + 1];
if (rightSibling.Keys.Count > _minKeysCount)
{
current.Keys.Add(parent.Keys[index]);
current.Values.Add(parent.Values[index]);
parent.Keys[index] = rightSibling.Keys[0];
parent.Values[index] = rightSibling.Values[0];
rightSibling.Keys.RemoveAt(0);
rightSibling.Values.RemoveAt(0);
return;
}
}
//如果左右兩邊兄弟結點都不滿足條件 判斷是否有左邊兄弟結點，如果有則和左邊兄弟結點合并 沒有 和右邊兄弟結點融合
if (index > 0)
{
MergeToLeft(parent, parent.Children[index - 1], current);
}
else
{
MergeToLeft(parent, current, parent.Children[index + 1]);
}
if (parent.Keys.Count < _minKeysCount)
{
if(parent == _first)
{
//如果是根結點
if(parent.Keys.Count == 0)
{
_first = current;
current.Parent = null;
}
}
else
{
BorrowFromParent(parent);
}
}
}
private void MergeToLeft(Node parent, Node left, Node right)
{
var index = parent.Children.IndexOf(left);
left.Keys.Add(parent.Keys[index]);
left.Values.Add(parent.Values[index]);
parent.Keys.RemoveAt(index);
parent.Values.RemoveAt(index);
left.Keys.AddRange(right.Keys);
left.Values.AddRange(right.Values);
left.Children.AddRange(right.Children);
parent.Children.Remove(right);
}
以上代碼均為原創分享，若大家認為有不妥的地方，煩請留言指出，在下感激不盡
也希望各位能夠多多分享自己寫的東西，共同進步