多路查找树
二叉树与B树
二叉树的问题分析：二叉树的操作效率较高，但是也存在问题。
- （1）二叉树需要加载到内存里，如果二叉树的节点少，没有什么问题，但是如果二叉树节点很多（比如1亿），就存在如下问题。
- （2）问题1：在构建二叉树时，需要多次进行I/O操作（海量数据存在数据库或文件中），节点海量，构建二叉树时，速度会有影响。
- （3）问题2：节点海量，也会造成二叉树的高度很大，会降低操作速度。
多叉树
为了解决以上问题，就产生了多叉树的概念。
- （1）在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（Mutiway Tree）。
- （2）后面我们讲解的2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。
- （3）举例说明（下面2-3树就是一颗多叉树）
B树
B树通过重新组织节点，降低树的高度，并且减少I/O读写次数来提升效率。
- （1）如果B树通过重新组织节点，降低了树的高度。
- （2）文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页（页的大小通常为4K），这样每个节点只需要一次I/O就可以完全载入。
- （3）将树的度M设置为1024，在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素，B树（B ）广泛应用于文件存储系统以及数据库系统中。
上图中，每个红圈都是一个节点，每个节点里有多个数据项。这里又需要引出两个概念：
- （1）节点度：每个节点，下面的子树个数有几个。如果有两颗子树度为2。
- （2）树度：所有节点里面，节点度最大的为树度。
2-3树
除了2-3树，还有2-3-4树等。概念和2-3树类似，也是一种B树。如图：
B树、B 树、B*树
B-Tree树即B树，B即Balanced,平衡的意思。有人把B-Tree翻译成B-树，容易让人产生误解。会以为B-树是一种树，而B树又是另一种树。实际上，B-Tree就是指的B树。
- 我们所说的B树、B 树、B*树，首先得是一颗平衡树，平衡树的前提必须是一颗搜索树或者排序树。
1.B树介绍
前面以及介绍了2-3树和2-3-4树，他们就是B树（B-Tree也写成B-树），这里我们在做一个说明，我们在学习Mysql时，经常听说某种数据类型的索引是基于B树或者B 树的，如图：
说明：
- （1）B树的阶：节点最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4.
- （2）B-树的搜索，从根节点开始，对节点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的子节点；重复，直到所对应的子指针为空，或已经是叶子节点。
- （3）关键字集合分部在整颗树中，即叶子节点和非叶子节点都存放数据。
- （4）搜索有可能在非叶子节点结束。
- （5）其搜索性能等价于在关键字全集内做一次二分查找。
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);
}
}
}调用
代码语言：javascript复制 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();
}2.B 树介绍
B 树是B树的变体，也是一种多路搜索树。
B 树的说明：
- （1）B 树的搜索与B树也基本相同，区别是B 树只有达到叶子节点才命中（B树可以在非叶子节点命中），其性能也等价于在关键字全集做一次二分查找。
- （2）所有关键子都出现在叶子节点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字（数据）恰好是有序的。
- （3）不可能在非叶子节点命中。第一个箭头指向的5是索引并不是数据，而真正的数据5节点是通过下面路径找到的。
- （4）非叶子节点相当于是叶子节点的索引（稀疏索引），叶子系欸DNA相当于是存储（关键字）数据的数据层。
- （5）更适合文件搜索系统。
- （6）B树和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
3.B*树介绍
B*树是B 树的变体，在B 树的非根和非叶子节点再增加指向兄弟的指针。
- （1）B*树定义了非叶子节点关键字个数至少为（2/3） * M，即块的最低使用率为2/3，而B 树的块的最低使用率为B 树的1/2。
- （2）从第一个特点我们可以看出，B*树分配新节点的概率比B 树要低，空间使用效率更高。
