C#实现平衡多路查找树(B树)

写在前面:搞了SQL Server时间也不短了，对B树的概念也算是比较了解。去网上搜也搜不到用C#或java实现的B树，干脆自己写一个。实现B树的过程中也对很多细节有了更深的了解。

创新互联公司-专业网站定制、快速模板网站建设、高性价比陇川网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式陇川网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖陇川地区。费用合理售后完善，十载实体公司更值得信赖。

 

简  介

B树是一种为辅助存储设计的一种数据结构，在1970年由R.Bayer和E.mccreight提出。在文件系统和数据库中为了减少IO操作大量被应用。遗憾的是，他们并没有说明为什么取名为B树，但按照B树的性质来说B通常被解释为Balance。在国内通常有说是B-树，其实并不存在B-树，只是由英文B-Tree直译成了B-树。

一个典型的 B树如图1所示。

   

图1.一个典型的B树

符合如下特征的树才可以称为B树：

  •     根节点如果不是叶节点，则至少需要两颗子树
  •     每个节点中有N个元素，和N+1个指针。每个节点中的元素不得小于最大节点容量的1/2
  •     所有的叶子位于同一层级（这也是为什么叫平衡树）
  •     父节点元素向左的指针必须小于节点元素，向右的指针必须大于节点元素，比如图1中Q的左指针必须小于Q，右指针必须大于Q

为什么要使用B树

在计算机系统中，存储设备一般分为两种，一种为主存（比如说CPU二级缓存，内存等），主存一般由硅制成，速度非常快，但每一个字节的成本往往高于辅助存储设备很多。还有一类是辅助存储(比如硬盘，磁盘等),这种设备通常容量会很大，成本也会低很多，但是存取速度非常的慢，下面我们来看一下最常见的辅存 --硬盘。    硬盘作为主机中除了唯一的一个机械存储设备，速度远远落后于CPU和内存。图2是一个典型的磁盘驱动器。

   

    图2.典型的磁盘驱动器工作原理

一个驱动器包含若干盘片，以一定的速度绕着主轴旋转（比如PC常见的转速是7200RPM,服务器级别的有10000RPM和15000RPM的）,每个盘片表面覆盖一个可磁化的物质.每个盘片利用摇臂末端的磁头进行读写。摇臂是物理连接在一起的，通过移动远离或贴近主轴。

因为有机械移动的部分，所以磁盘的速度相比内存而言是非常的慢。这个机械移动包括两个部分：盘旋转和磁臂移动。仅仅对于盘旋转来说，比如常见的 7200RPM的硬盘，转一圈需要60/7200≈8.33ms,换句话说，让磁盘完整的旋转一圈找到所需要的数据需要8.33ms,这比内存常见的 100ns慢100000倍左右，这还不包括移动摇臂的时间。

因为机械移动如此的花时间，磁盘会每次读取多个数据项。一般来说最小单位为簇。而对于SQL Server来说，则为一页（8K）。

但由于要查找的数据往往很大，不能全部装入主存。需要磁盘来辅助存储。而读取磁盘则是占处理时间最重要的一部分，所以如果我们尽可能的减少对磁盘的IO操作，则会大大加快速度。这也是B树设计的初衷。

B树通过将根节点放入主存，其它所有节点放入辅存来大大减少对于辅存IO的操作。比如图1中，我如果想查找元素Y，仅仅需要从主存中取得根节点，再根据根节点的右指针做一次IO读，再根据这个节点最右的指针做一次IO读，就可以找到元素Y。相比其他数据结构，仅仅做两次辅存IO读大大减少了查找的时间。

B树的高度

根据上面的例子我们可以看出，对于辅存做IO读的次数取决于B树的高度。而B树的高度由什么决定的呢？

根据B树的高度公式:   

其中T为度数（每个节点包含的元素个数），N为总元素个数.

我们可以看出T对于树的高度有决定性的影响。因此如果每个节点包含更多的元素个数，在元素个数相同的情况下，则更有可能减少B树的高度。这也是为什么 SQL Server中需要尽量以窄键建立聚集索引。因为SQL Server中每个节点的大小为8092字节，如果减少键的大小，则可以容纳更多的元素，从而减少了B树的高度，提升了查询的性能。

上面B树高度的公式也可以进行推导得出，将每一层级的的元素个数加起来，比如度为T的节点，根为1个节点，第二层至少为2个节点，第三层至少为2t个节点，第四层至少为2t*t个节点。将所有最小节点相加，从而得到节点个数N的公式:

              

两边取对数，则可以得到树的高度公式。

这也是为什么开篇所说每个节点必须至少有两个子元素，因为根据高度公式，如果每个节点只有一个元素，也就是T=1的话，那么高度将会趋于正无穷。

B树的实现

讲了这么多概念，该到实现B树的时候了。

首先需要定义B树的节点，如代码1所示。

 
 
 
 
      
  
  
  
  1. public class TreeNodewhere T:IComparable  
    2.   
  
  
  
  2. {  
    3.   
  
  
  
  3.     public int elementNum = 0;//元素个数  
    4.   
  
  
  
  4.     public IList Elements = new List();//元素集合,存在elementNum个  
    5.   
  
  
  
  5.     public IList> Pointer = new List>();//元素指针，存在elementNum+1  
    6.   
  
  
  
  6.     public bool IsLeaf = true;//是否为叶子节点  
    7.   
  
  
  
  7.       
    8.   
  
  
  
  8. } 
    9.

代码1.声明节点

我给每个节点四个属性，分别为节点包含的元素个数，节点的元素数组，节点的指针数组和节点是否为叶子节点。我这里对节点存储的元素类型使用了泛型T，并且必须实现ICompable接口使得节点所存储的元素可以互相比较。

有了节点的定义后，就可以创建B树了，如代码2所示。

 
 
 
 
      
  
  
  
  1. //创建一个b树,也是类的构造函数  
    2.   
  
  
  
  2. public BTree()  
    3.   
  
  
  
  3. {  
    4.   
  
  
  
  4.  
    5.   
  
  
  
  5.     RootNode = new TreeNode();  
    6.   
  
  
  
  6.     RootNode.elementNum = 0;  
    7.   
  
  
  
  7.     RootNode.IsLeaf = true;  
    8.   
  
  
  
  8.     //将节点写入磁盘，做一次IO写  
    9.   
  
  
  
  9. } 
    10.

代码2.初始化B树

这是BTree类的构造函数，初始化一个根节点。全部代码我稍后给出。

下面则要考虑B树的插入，其实B树的构建过程也是向B树插入元素的过程.B树的插入相对来说比较复杂，需要考虑很多因素。

首先，每一个节点可容纳的元素个数是一样并且有限的，这里我声明了一个常量最为每个节点,如代码3所示。

 
 
 
 
      
  
  
  
  1. const int NumPerNode = 4; 
    2.

代码3.设置每个节点最多容纳的元素个数

对于B树来说，节点增加的唯一方式就是节点分裂，这个概念和SQL SERVER中的页分裂是一样的。

页分裂的过程首先需要生成新页，然后将大概一半的元素移动到新页中，然后将中间元素提升到父节点。比如我想在现有的元素中插入8，造成已满的页进行分裂，如图3所示:

   

    图3.向已经满的叶子节点插入元素会造成页分裂

通过叶子分裂的概念不难看出，叶子节点分裂才会造成非叶子节点元素的增加。最终传递到根元素。而根元素的分裂是树长高的唯一途径。

在C#中的实现代码如代码4所示。

 
 
 
 
      
  
  
  
  1. //B树中的节点分裂  
    2.   
  
  
  
  2.  public void BTreeSplitNode(TreeNode FatherNode, int position, TreeNode NodeToBeSplit)  
    3.   
  
  
  
  3.  {  
    4.   
  
  
  
  4.      TreeNode newNode = new TreeNode();//创建新节点，容纳分裂后被移动的元素  
    5.   
  
  
  
  5.      newNode.IsLeaf = NodeToBeSplit.IsLeaf;//新节点的层级和原节点位于同一层  
    6.   
  
  
  
  6.      newNode.elementNum = NumPerNode - (NumPerNode / 2 + 1);//新节点元素的个数大约为分裂节点的一半  
    7.   
  
  
  
  7.      for (int i = 1; i < NumPerNode - (NumPerNode / 2 + 1); i++)  
    8.   
  
  
  
  8.      {  
    9.   
  
  
  
  9.          //将原页中后半部分复制到新页中  
    10.   
  
  
  
  10.          newNode.Elements[i - 1] = NodeToBeSplit.Elements[i + NumPerNode / 2];  
    11.   
  
  
  
  11.      }  
    12.   
  
  
  
  12.      if (!NodeToBeSplit.IsLeaf)//如果不是叶子节点，将指针也复制过去  
    13.   
  
  
  
  13.      {  
    14.   
  
  
  
  14.          for (int j = 1; j < NumPerNode / 2 + 1; j++)  
    15.   
  
  
  
  15.          {  
    16.   
  
  
  
  16.              newNode.Pointer[j - 1] = NodeToBeSplit.Pointer[NumPerNode / 2];  
    17.   
  
  
  
  17.          }  
    18.   
  
  
  
  18.      }  
    19.   
  
  
  
  19.      NodeToBeSplit.elementNum = NumPerNode / 2;//原节点剩余元素个数  
    20.   
  
  
  
  20.  
    21.   
  
  
  
  21.      //将父节点指向子节点的指针向后推一位  
    22.   
  
  
  
  22.      for (int k = FatherNode.elementNum + 1; k > position + 1; k--)  
    23.   
  
  
  
  23.      {  
    24.   
  
  
  
  24.          FatherNode.Pointer[k] = FatherNode.Pointer[k - 1];  
    25.   
  
  
  
  25.      }  
    26.   
  
  
  
  26.      //将父节点的元素向后推一位  
    27.   
  
  
  
  27.      for (int k = FatherNode.elementNum; k > position + 1; k--)  
    28.   
  
  
  
  28.      {  
    29.   
  
  
  
  29.          FatherNode.Elements[k] = FatherNode.Elements[k - 1];  
    30.   
  
  
  
  30.      }  
    31.   
  
  
  
  31.      //将被分裂的页的中间节点插入父节点  
    32.   
  
  
  
  32.      FatherNode.Elements[position - 1] = NodeToBeSplit.Elements[NumPerNode / 2];  
    33.   
  
  
  
  33.      //父节点元素大小+1  
    34.   
  
  
  
  34.      FatherNode.elementNum += 1;  
    35.   
  
  
  
  35.      //将FatherNode,NodeToBeSplit,newNode写回磁盘,三次IO写操作  
    36.   
  
  
  
  36.  
    37.   
  
  
  
  37.  } 
    38.

代码4.分裂节点

通过概念和代码不难看出，节点的分裂相对比较消耗IO，这也是为什么SQL Server中需要一些最佳实现比如不用GUID做聚集索引，或是设置填充因子等来减少页分裂。

而如果需要插入元素的节点不满，则不需要页分裂，则需要从根开始查找，找到需要被插入的节点，如代码5所示。

 
 
 
 
      
  
  
  
  1. //在节点非满时寻找插入节点  
    2.   
  
  
  
  2. public void BTreeInsertNotFull(TreeNode Node, T KeyWord)  
    3.   
  
  
  
  3. {  
    4.   
  
  
  
  4.     int i=Node.elementNum;  
    5.   
  
  
  
  5.     //如果是叶子节点，则寻找合适的位置直接插入  
    6.   
  
  
  
  6.     if (Node.IsLeaf)  
    7.   
  
  
  
  7.     {  
    8.   
  
  
  
  8.           
    9.   
  
  
  
  9.         while (i >= 1 && KeyWord.CompareTo(Node.Elements[i - 1]) < 0)  
    10.   
  
  
  
  10.         {  
    11.   
  
  
  
  11.             Node.Elements[i] = Node.Elements[i - 1];//所有的元素后推一位  
    12.   
  
  
  
  12.             i -= 1;  
    13.   
  
  
  
  13.         }  
    14.   
  
  
  
  14.         Node.Elements[i - 1] = KeyWord;//将关键字插入节点  
    15.   
  
  
  
  15.         Node.elementNum += 1;  
    16.   
  
  
  
  16.         //将节点写入磁盘，IO写+1  
    17.   
  
  
  
  17.     }  
    18.   
  
  
  
  18.     //如果是非叶子节点  
    19.   
  
  
  
  19.     else 
    20.   
  
  
  
  20.     {  
    21.   
  
  
  
  21.         while (i >= 1 && KeyWord.CompareTo(Node.Elements[i - 1]) < 0)  
    22.   
  
  
  
  22.         {  
    23.   
  
  
  
  23.             i -= 1;  
    24.   
  
  
  
  24.         }  
    25.   
  
  
  
  25.         //这步将指针所指向的节点读入内存,IO读+1  
    26.   
  
  
  
  26.         if (Node.Pointer[i].elementNum == NumPerNode)  
    27.   
  
  
  
  27.         {  
    28.   
  
  
  
  28.             //如果子节点已满，进行节点分裂  
    29.   
  
  
  
  29.             BTreeSplitNode(Node, i, Node.Pointer[i]);  
    30.   
  
  
  
  30.  
    31.   
  
  
  
  31.         }  
    32.   
  
  
  
  32.         if (KeyWord.CompareTo(Node.Elements[i - 1]) > 0)  
    33.   
  
  
  
  33.         {  
    34.   
  
  
  
  34.             //根据关键字的值决定插入分裂后的左孩子还是右孩子  
    35.   
  
  
  
  35.             i += 1;  
    36.   
  
  
  
  36.         }  
    37.   
  
  
  
  37.         //迭代找叶子，找到叶子节点后插入  
    38.   
  
  
  
  38.         BTreeInsertNotFull(Node.Pointer[i], KeyWord);  
    39.   
  
  
  
  39.            
    40.   
  
  
  
  40.  
    41.   
  
  
  
  41.     }  
    42.   
  
  
  
  42. } 
    43.

代码5.插入

通过代码5可以看出，我们没有进行任何迭代。而是从根节点开始遇到满的节点直接进行分裂。从而减少了性能损失。

再将根节点分裂的特殊情况考虑进去，我们从而将插入操作合为一个函数，如代码6所示。

 
 
 
 
      
  
  
  
  1. public void BtreeInsert(T KeyWord)  
    2.   
  
  
  
  2. {  
    3.   
  
  
  
  3.     if (RootNode.elementNum == NumPerNode)  
    4.   
  
  
  
  4.     {  
    5.   
  
  
  
  5.  
    6.   
  
  
  
  6.         //如果根节点满了，则对跟节点进行分裂  
    7.   
  
  
  
  7.         TreeNode newRoot = new TreeNode();  
    8.   
  
  
  
  8.         newRoot.elementNum = 0;  
    9.   
  
  
  
  9.         newRoot.IsLeaf = false;  
    10.   
  
  
  
  10.         //将newRoot节点变为根节点  
    11.   
  
  
  
  11.         BTreeSplitNode(newRoot, 1, RootNode);  
    12.   
  
  
  
  12.         //分裂后插入新根的树  
    13.   
  
  
  
  13.         BTreeInsertNotFull(newRoot, KeyWord);  
    14.   
  
  
  
  14.         //将树的根进行变换  
    15.   
  
  
  
  15.         RootNode = newRoot;  
    16.   
  
  
  
  16.     }  
    17.   
  
  
  
  17.     else 
    18.   
  
  
  
  18.     {  
    19.   
  
  
  
  19.         //如果根节点没有满，直接插入  
    20.   
  
  
  
  20.         BTreeInsertNotFull(RootNode, KeyWord);  
    21.   
  
  
  
  21.     }  
    22.   
  
  
  
  22. } 
    23.

代码6.插入操作

现在，我们就可以通过插入操作，来实现一个B树了。

B树的查找

既然B树生成好了，我们就可以对B树进行查找了。B树的查找实现相对简单，仅仅是从跟节点进行迭代，如果找到元素则返回节点和位置，如果找不到则返回NULL.

 
 
 
 
      
  
  
  
  1. //从B树中搜索节点，存在则返回节点和元素在节点的值，否则返回NULL  
    2.   
  
  
  
  2. public returnValue BTreeSearch(TreeNode rootNode, T keyword)  
    3.   
  
  
  
  3. {  
    4.   
  
  
  
  4.     int i = 1;  
    5.   
  
  
  
  5.       
    6.   
  
  
  
  6.     while (i <= rootNode.elementNum && keyword.CompareTo(rootNode.Elements[i - 1])>0)  
    7.   
  
  
  
  7.     {  
    8.   
  
  
  
  8.         i = i + 1;  
    9.   
  
  
  
  9.     }  
    10.   
  
  
  
  10.     if (i <= rootNode.elementNum && keyword.CompareTo(rootNode.Elements[i - 1]) == 0)  
    11.   
  
  
  
  11.     {  
    12.   
  
  
  
  12.         returnValue r = new returnValue();  
    13.   
  
  
  
  13.         r.node = rootNode.Pointer[i];  
    14.   
  
  
  
  14.         r.position = i;  
    15.   
  
  
  
  15.         return r;  
    16.   
  
  
  
  16.     }  
    17.   
  
  
  
  17.     if (rootNode.IsLeaf)  
    18.   
  
  
  
  18.     {  
    19.   
  
  
  
  19.         return null;  
    20.   
  
  
  
  20.     }  
    21.   
  
  
  
  21.     else 
    22.   
  
  
  
  22.     {  
    23.   
  
  
  
  23.         //从磁盘将内容读出来,做一次IO读  
    24.   
  
  
  
  24.         return BTreeSearch(rootNode.Pointer[i], keyword);  
    25.   
  
  
  
  25.     }  
    26.   
  
  
  
  26. } 
    27.

代码7.对B树进行查找

顺带说一下，returnValue类仅仅是对返回值的一个封装，代码如代码8所示。

 
 
 
 
      
  
  
  
  1. public class returnValue where T : IComparable  
    2.   
  
  
  
  2. {  
    3.   
  
  
  
  3.     public TreeNode node;  
    4.   
  
  
  
  4.     public int position;  
    5.   
  
  
  
  5. } 
    6.

代码8.returnValue的代码

总  结

本文从B树的概念原理，以及为什么需要B树到B树的实现来阐述B树的概念。B树是一种非常优雅的数据结构。是关系数据库和文件系统的核心算法。对于B树的了解会使得你对于数据库的学习更加系统和容易。

源码下载地址：http://down.51cto.com/data/369940

文章标题：C#实现平衡多路查找树(B树)
网页URL：http://www.shufengxianlan.com/qtweb/news18/215218.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

云服务器知识

分类信息网

虚拟主机　　 　成都做网站　　 　成都网站设计　　 　网站seo优化　　 　成都广告制作　　 　成都二枢电信服务器托管　　 　奢侈品网站建设方案　　 　域名注册　　 　LED亮化工程　　 　成都定制网站建设　　 　手机网站制作　　 　微信公众号开发　　 　成都做网站　　 　德阳服务器托管　　 　鳄鱼养殖　　 　双流做网站　　 　成都网页设计　　 　雷运建站　　 　腾讯云香港空间　　 　成都花箱厂家