二叉树的问题分析:二叉树的操作效率较高,但是也存在问题。
为了解决以上问题,就产生了多叉树的概念。
B树通过重新组织节点,降低树的高度,并且减少I/O读写次数来提升效率。
上图中,每个红圈都是一个节点,每个节点里有多个数据项。这里又需要引出两个概念:
除了2-3树,还有2-3-4树等。概念和2-3树类似,也是一种B树。如图:
B-Tree树即B树,B即Balanced,平衡的意思。有人把B-Tree翻译成B-树,容易让人产生误解。会以为B-树是一种树,而B树又是另一种树。实际上,B-Tree就是指的B树。
前面以及介绍了2-3树和2-3-4树,他们就是B树(B-Tree也写成B-树),这里我们在做一个说明,我们在学习Mysql时,经常听说某种数据类型的索引是基于B树或者B+树的,如图:
说明:
public class Consts
{
public const int M = 3; // B树的最小度数
public const int KeyMax = 2 * M - 1; // 节点包含关键字的最大个数
public const int KeyMin = M - 1; // 非根节点包含关键字的最小个数
public const int ChildMax = KeyMax + 1; // 孩子节点的最大个数
public const int ChildMin = KeyMin + 1; // 孩子节点的最小个数
}
public class BTreeNode
{
private bool leaf;
public int[] keys;
public int keyNumber;
public BTreeNode[] children;
public int blockIndex;
public int dataIndex;
public BTreeNode(bool leaf)
{
this.leaf = leaf;
keys = new int[Consts.KeyMax];
children = new BTreeNode[Consts.ChildMax];
}
/// <summary>在未满的节点中插入键值</summary>
/// <param name="key">键值</param>
public void InsertNonFull(int key)
{
var index = keyNumber - 1;
if (leaf == true)
{
// 找到合适位置,并且移动节点键值腾出位置
while (index >= 0 && keys[index] > key)
{
keys[index + 1] = keys[index];
index--;
}
// 在index后边新增键值
keys[index + 1] = key;
keyNumber = keyNumber + 1;
}
else
{
// 找到合适的子孩子索引
while (index >= 0 && keys[index] > key) index--;
// 如果孩子节点已满
if (children[index + 1].keyNumber == Consts.KeyMax)
{
// 分裂该孩子节点
SplitChild(index + 1, children[index + 1]);
// 分裂后中间节点上跳父节点
// 孩子节点已经分裂成2个节点,找到合适的一个
if (keys[index + 1] < key) index++;
}
// 插入键值
children[index + 1].InsertNonFull(key);
}
}
/// <summary>分裂节点</summary>
/// <param name="childIndex">孩子节点索引</param>
/// <param name="waitSplitNode">待分裂节点</param>
public void SplitChild(int childIndex, BTreeNode waitSplitNode)
{
var newNode = new BTreeNode(waitSplitNode.leaf);
newNode.keyNumber = Consts.KeyMin;
// 把待分裂的节点中的一般节点搬到新节点
for (var j = 0; j < Consts.KeyMin; j++)
{
newNode.keys[j] = waitSplitNode.keys[j + Consts.ChildMin];
// 清0
waitSplitNode.keys[j + Consts.ChildMin] = 0;
}
// 如果待分裂节点不是也只节点
if (waitSplitNode.leaf == false)
{
for (var j = 0; j < Consts.ChildMin; j++)
{
// 把孩子节点也搬过去
newNode.children[j] = waitSplitNode.children[j + Consts.ChildMin];
// 清0
waitSplitNode.children[j + Consts.ChildMin] = null;
}
}
waitSplitNode.keyNumber = Consts.KeyMin;
// 拷贝一般键值到新节点
for (var j = keyNumber; j >= childIndex + 1; j--)
children[j + 1] = children[j];
children[childIndex + 1] = newNode;
for (var j = keyNumber - 1; j >= childIndex; j--)
keys[j + 1] = keys[j];
// 把中间键值上跳至父节点
keys[childIndex] = waitSplitNode.keys[Consts.KeyMin];
// 清0
waitSplitNode.keys[Consts.KeyMin] = 0;
// 根节点键值数自加
keyNumber = keyNumber + 1;
}
/// <summary>根据节点索引顺序打印节点键值</summary>
public void PrintByIndex()
{
int index;
for (index = 0; index < keyNumber; index++)
{
// 如果不是叶子节点, 先打印叶子子节点.
if (leaf == false) children[index].PrintByIndex();
Console.Write("{0} ", keys[index]);
}
// 打印孩子节点
if (leaf == false) children[index].PrintByIndex();
}
/// <summary>查找某键值是否已经存在树中</summary>
/// <param name="key">键值</param>
/// <returns></returns>
public BTreeNode Find(int key)
{
int index = 0;
while (index < keyNumber && key > keys[index]) index++;
// 该key已经存在, 返回该索引位置节点
if (keys[index] == key) return this;
// key 不存在,并且节点是叶子节点
if (leaf == true) return null;
// 递归在孩子节点中查找
return children[index].Find(key);
}
}
public class BTree
{
public BTreeNode Root { get; private set; }
public BTree() { }
/// <summary>根据节点索引顺序打印节点键值</summary>
public void PrintByIndex()
{
if (Root == null)
{
Console.WriteLine("空树");
return;
}
Root.PrintByIndex();
}
/// <summary>查找某键值是否已经存在树中</summary>
/// <param name="key">键值</param>
/// <returns></returns>
public BTreeNode Find(int key)
{
if (Root == null) return null;
return Root.Find(key);
}
/// <summary>新增B树节点键值</summary>
/// <param name="key">键值</param>
public void Insert(int key)
{
if (Root == null)
{
Root = new BTreeNode(true);
Root.keys[0] = key;
Root.keyNumber = 1;
return;
}
if (Root.keyNumber == Consts.KeyMax)
{
var newNode = new BTreeNode(false);
newNode.children[0] = Root;
newNode.SplitChild(0, Root);
var index = 0;
if (newNode.keys[0] < key) index++;
newNode.children[index].InsertNonFull(key);
Root = newNode;
}
else
{
Root.InsertNonFull(key);
}
}
}
调用
static void Main(string[] args)
{
BTree tree = new BTree();
Random random = new Random();
for (int i = 0; i < 10; i++)
{
tree.Insert(random.Next(100));
}
tree.PrintByIndex();
Console.Read();
}
B+树是B树的变体,也是一种多路搜索树。
B+树的说明:
如果不用B+树的结构管理数据,下图中有9组数据每组3个那么总共有27个数据。放在单链表中的排列就会是{5,8,9,10,15,18.....28.....99}。
如果需要去检索除28,那么就会逐个遍历去找效率会非常低。如果不想这么去操作,这时候就需要进行分组。将它们每3个分成一组,那么{5,8,9,10,15,18.....28.....99}这个列表就会被分成9段。每一段有3个数据。
这个时候再去找28就会非常快,就相当于砍掉了2/3个节点数。
代码参考:https://github.com/justcoding121/Advanced-Algorithms/blob/develop/src/Advanced.Algorithms/DataStructures/Tree/B+Tree.cs
B*树是B+树的变体,在B+树的非根和非叶子节点再增加指向兄弟的指针。