偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

C#實(shí)現(xiàn)平衡多路查找樹(shù)(B樹(shù))

作者：宋沄劍
開(kāi)發(fā) 后端
寫(xiě)在前面:搞了SQL Server時(shí)間也不短了，對(duì)B樹(shù)的概念也算是比較了解。去網(wǎng)上搜也搜不到用C#或java實(shí)現(xiàn)的B樹(shù)，干脆自己寫(xiě)一個(gè)。實(shí)現(xiàn)B樹(shù)的過(guò)程中也對(duì)很多細(xì)節(jié)有了更深的了解。

寫(xiě)在前面:搞了SQL Server時(shí)間也不短了，對(duì)B樹(shù)的概念也算是比較了解。去網(wǎng)上搜也搜不到用C#或java實(shí)現(xiàn)的B樹(shù)，干脆自己寫(xiě)一個(gè)。實(shí)現(xiàn)B樹(shù)的過(guò)程中也對(duì)很多細(xì)節(jié)有了更深的了解。

 

簡(jiǎn)  介

B樹(shù)是一種為輔助存儲(chǔ)設(shè)計(jì)的一種數(shù)據(jù)結(jié)構(gòu)，在1970年由R.Bayer和E.mccreight提出。在文件系統(tǒng)和數(shù)據(jù)庫(kù)中為了減少I(mǎi)O操作大量被應(yīng)用。遺憾的是，他們并沒(méi)有說(shuō)明為什么取名為B樹(shù)，但按照B樹(shù)的性質(zhì)來(lái)說(shuō)B通常被解釋為Balance。在國(guó)內(nèi)通常有說(shuō)是B-樹(shù)，其實(shí)并不存在B-樹(shù)，只是由英文B-Tree直譯成了B-樹(shù)。

一個(gè)典型的 B樹(shù)如圖1所示。

    1

圖1.一個(gè)典型的B樹(shù)

符合如下特征的樹(shù)才可以稱為B樹(shù)：

  •     根節(jié)點(diǎn)如果不是葉節(jié)點(diǎn)，則至少需要兩顆子樹(shù)
  •     每個(gè)節(jié)點(diǎn)中有N個(gè)元素，和N+1個(gè)指針。每個(gè)節(jié)點(diǎn)中的元素不得小于最大節(jié)點(diǎn)容量的1/2
  •     所有的葉子位于同一層級(jí)（這也是為什么叫平衡樹(shù)）
  •     父節(jié)點(diǎn)元素向左的指針必須小于節(jié)點(diǎn)元素，向右的指針必須大于節(jié)點(diǎn)元素，比如圖1中Q的左指針必須小于Q，右指針必須大于Q

為什么要使用B樹(shù)

在計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)設(shè)備一般分為兩種，一種為主存（比如說(shuō)CPU二級(jí)緩存，內(nèi)存等），主存一般由硅制成，速度非?？?，但每一個(gè)字節(jié)的成本往往高于輔助存儲(chǔ)設(shè)備很多。還有一類(lèi)是輔助存儲(chǔ)(比如硬盤(pán)，磁盤(pán)等),這種設(shè)備通常容量會(huì)很大，成本也會(huì)低很多，但是存取速度非常的慢，下面我們來(lái)看一下最常見(jiàn)的輔存 --硬盤(pán)。    硬盤(pán)作為主機(jī)中除了唯一的一個(gè)機(jī)械存儲(chǔ)設(shè)備，速度遠(yuǎn)遠(yuǎn)落后于CPU和內(nèi)存。圖2是一個(gè)典型的磁盤(pán)驅(qū)動(dòng)器。

    ypdxyl01

    圖2.典型的磁盤(pán)驅(qū)動(dòng)器工作原理

 

一個(gè)驅(qū)動(dòng)器包含若干盤(pán)片，以一定的速度繞著主軸旋轉(zhuǎn)（比如PC常見(jiàn)的轉(zhuǎn)速是7200RPM,服務(wù)器級(jí)別的有10000RPM和15000RPM的）,每個(gè)盤(pán)片表面覆蓋一個(gè)可磁化的物質(zhì).每個(gè)盤(pán)片利用搖臂末端的磁頭進(jìn)行讀寫(xiě)。搖臂是物理連接在一起的，通過(guò)移動(dòng)遠(yuǎn)離或貼近主軸。

因?yàn)橛袡C(jī)械移動(dòng)的部分，所以磁盤(pán)的速度相比內(nèi)存而言是非常的慢。這個(gè)機(jī)械移動(dòng)包括兩個(gè)部分：盤(pán)旋轉(zhuǎn)和磁臂移動(dòng)。僅僅對(duì)于盤(pán)旋轉(zhuǎn)來(lái)說(shuō)，比如常見(jiàn)的 7200RPM的硬盤(pán)，轉(zhuǎn)一圈需要60/7200≈8.33ms,換句話說(shuō)，讓磁盤(pán)完整的旋轉(zhuǎn)一圈找到所需要的數(shù)據(jù)需要8.33ms,這比內(nèi)存常見(jiàn)的 100ns慢100000倍左右，這還不包括移動(dòng)搖臂的時(shí)間。

因?yàn)闄C(jī)械移動(dòng)如此的花時(shí)間，磁盤(pán)會(huì)每次讀取多個(gè)數(shù)據(jù)項(xiàng)。一般來(lái)說(shuō)最小單位為簇。而對(duì)于SQL Server來(lái)說(shuō)，則為一頁(yè)（8K）。

但由于要查找的數(shù)據(jù)往往很大，不能全部裝入主存。需要磁盤(pán)來(lái)輔助存儲(chǔ)。而讀取磁盤(pán)則是占處理時(shí)間最重要的一部分，所以如果我們盡可能的減少對(duì)磁盤(pán)的IO操作，則會(huì)大大加快速度。這也是B樹(shù)設(shè)計(jì)的初衷。

B樹(shù)通過(guò)將根節(jié)點(diǎn)放入主存，其它所有節(jié)點(diǎn)放入輔存來(lái)大大減少對(duì)于輔存IO的操作。比如圖1中，我如果想查找元素Y，僅僅需要從主存中取得根節(jié)點(diǎn)，再根據(jù)根節(jié)點(diǎn)的右指針做一次IO讀，再根據(jù)這個(gè)節(jié)點(diǎn)最右的指針做一次IO讀，就可以找到元素Y。相比其他數(shù)據(jù)結(jié)構(gòu)，僅僅做兩次輔存IO讀大大減少了查找的時(shí)間。

B樹(shù)的高度

根據(jù)上面的例子我們可以看出，對(duì)于輔存做IO讀的次數(shù)取決于B樹(shù)的高度。而B(niǎo)樹(shù)的高度由什么決定的呢？

根據(jù)B樹(shù)的高度公式:    clip_image002

其中T為度數(shù)（每個(gè)節(jié)點(diǎn)包含的元素個(gè)數(shù)），N為總元素個(gè)數(shù).

我們可以看出T對(duì)于樹(shù)的高度有決定性的影響。因此如果每個(gè)節(jié)點(diǎn)包含更多的元素個(gè)數(shù)，在元素個(gè)數(shù)相同的情況下，則更有可能減少B樹(shù)的高度。這也是為什么 SQL Server中需要盡量以窄鍵建立聚集索引。因?yàn)镾QL Server中每個(gè)節(jié)點(diǎn)的大小為8092字節(jié)，如果減少鍵的大小，則可以容納更多的元素，從而減少了B樹(shù)的高度，提升了查詢的性能。

上面B樹(shù)高度的公式也可以進(jìn)行推導(dǎo)得出，將每一層級(jí)的的元素個(gè)數(shù)加起來(lái)，比如度為T(mén)的節(jié)點(diǎn)，根為1個(gè)節(jié)點(diǎn)，第二層至少為2個(gè)節(jié)點(diǎn)，第三層至少為2t個(gè)節(jié)點(diǎn)，第四層至少為2t*t個(gè)節(jié)點(diǎn)。將所有最小節(jié)點(diǎn)相加，從而得到節(jié)點(diǎn)個(gè)數(shù)N的公式:

               clip_image002[4]

兩邊取對(duì)數(shù)，則可以得到樹(shù)的高度公式。

這也是為什么開(kāi)篇所說(shuō)每個(gè)節(jié)點(diǎn)必須至少有兩個(gè)子元素，因?yàn)楦鶕?jù)高度公式，如果每個(gè)節(jié)點(diǎn)只有一個(gè)元素，也就是T=1的話，那么高度將會(huì)趨于正無(wú)窮。

B樹(shù)的實(shí)現(xiàn)

講了這么多概念，該到實(shí)現(xiàn)B樹(shù)的時(shí)候了。

首先需要定義B樹(shù)的節(jié)點(diǎn)，如代碼1所示。

  1. public class TreeNode<T>where T:IComparable<T>  
  2. {  
  3.     public int elementNum = 0;//元素個(gè)數(shù)  
  4.     public IList<T> Elements = new List<T>();//元素集合,存在elementNum個(gè)  
  5.     public IList<TreeNode<T>> Pointer = new List<TreeNode<T>>();//元素指針，存在elementNum+1  
  6.     public bool IsLeaf = true;//是否為葉子節(jié)點(diǎn)  
  7.       
  8. } 

代碼1.聲明節(jié)點(diǎn)

 

我給每個(gè)節(jié)點(diǎn)四個(gè)屬性，分別為節(jié)點(diǎn)包含的元素個(gè)數(shù)，節(jié)點(diǎn)的元素?cái)?shù)組，節(jié)點(diǎn)的指針數(shù)組和節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)。我這里對(duì)節(jié)點(diǎn)存儲(chǔ)的元素類(lèi)型使用了泛型T，并且必須實(shí)現(xiàn)ICompable接口使得節(jié)點(diǎn)所存儲(chǔ)的元素可以互相比較。

 

有了節(jié)點(diǎn)的定義后，就可以創(chuàng)建B樹(shù)了，如代碼2所示。

  1. //創(chuàng)建一個(gè)b樹(shù),也是類(lèi)的構(gòu)造函數(shù)  
  2. public BTree()  
  3. {  
  4.  
  5.     RootNode = new TreeNode<T>();  
  6.     RootNode.elementNum = 0;  
  7.     RootNode.IsLeaf = true;  
  8.     //將節(jié)點(diǎn)寫(xiě)入磁盤(pán)，做一次IO寫(xiě)  
  9. } 

代碼2.初始化B樹(shù)

這是BTree類(lèi)的構(gòu)造函數(shù)，初始化一個(gè)根節(jié)點(diǎn)。全部代碼我稍后給出。

 

下面則要考慮B樹(shù)的插入，其實(shí)B樹(shù)的構(gòu)建過(guò)程也是向B樹(shù)插入元素的過(guò)程.B樹(shù)的插入相對(duì)來(lái)說(shuō)比較復(fù)雜，需要考慮很多因素。

首先，每一個(gè)節(jié)點(diǎn)可容納的元素個(gè)數(shù)是一樣并且有限的，這里我聲明了一個(gè)常量最為每個(gè)節(jié)點(diǎn),如代碼3所示。

  1. const int NumPerNode = 4; 

代碼3.設(shè)置每個(gè)節(jié)點(diǎn)最多容納的元素個(gè)數(shù)

 

對(duì)于B樹(shù)來(lái)說(shuō)，節(jié)點(diǎn)增加的唯一方式就是節(jié)點(diǎn)分裂，這個(gè)概念和SQL SERVER中的頁(yè)分裂是一樣的。

頁(yè)分裂的過(guò)程首先需要生成新頁(yè)，然后將大概一半的元素移動(dòng)到新頁(yè)中，然后將中間元素提升到父節(jié)點(diǎn)。比如我想在現(xiàn)有的元素中插入8，造成已滿的頁(yè)進(jìn)行分裂，如圖3所示:

    2

    圖3.向已經(jīng)滿的葉子節(jié)點(diǎn)插入元素會(huì)造成頁(yè)分裂

通過(guò)葉子分裂的概念不難看出，葉子節(jié)點(diǎn)分裂才會(huì)造成非葉子節(jié)點(diǎn)元素的增加。最終傳遞到根元素。而根元素的分裂是樹(shù)長(zhǎng)高的唯一途徑。

在C#中的實(shí)現(xiàn)代碼如代碼4所示。

  1. //B樹(shù)中的節(jié)點(diǎn)分裂  
  2.  public void BTreeSplitNode(TreeNode<T> FatherNode, int position, TreeNode<T> NodeToBeSplit)  
  3.  {  
  4.      TreeNode<T> newNode = new TreeNode<T>();//創(chuàng)建新節(jié)點(diǎn)，容納分裂后被移動(dòng)的元素  
  5.      newNode.IsLeaf = NodeToBeSplit.IsLeaf;//新節(jié)點(diǎn)的層級(jí)和原節(jié)點(diǎn)位于同一層  
  6.      newNode.elementNum = NumPerNode - (NumPerNode / 2 + 1);//新節(jié)點(diǎn)元素的個(gè)數(shù)大約為分裂節(jié)點(diǎn)的一半  
  7.      for (int i = 1; i < NumPerNode - (NumPerNode / 2 + 1); i++)  
  8.      {  
  9.          //將原頁(yè)中后半部分復(fù)制到新頁(yè)中  
  10.          newNode.Elements[i - 1] = NodeToBeSplit.Elements[i + NumPerNode / 2];  
  11.      }  
  12.      if (!NodeToBeSplit.IsLeaf)//如果不是葉子節(jié)點(diǎn)，將指針也復(fù)制過(guò)去  
  13.      {  
  14.          for (int j = 1; j < NumPerNode / 2 + 1; j++)  
  15.          {  
  16.              newNode.Pointer[j - 1] = NodeToBeSplit.Pointer[NumPerNode / 2];  
  17.          }  
  18.      }  
  19.      NodeToBeSplit.elementNum = NumPerNode / 2;//原節(jié)點(diǎn)剩余元素個(gè)數(shù)  
  20.  
  21.      //將父節(jié)點(diǎn)指向子節(jié)點(diǎn)的指針向后推一位  
  22.      for (int k = FatherNode.elementNum + 1; k > position + 1; k--)  
  23.      {  
  24.          FatherNode.Pointer[k] = FatherNode.Pointer[k - 1];  
  25.      }  
  26.      //將父節(jié)點(diǎn)的元素向后推一位  
  27.      for (int k = FatherNode.elementNum; k > position + 1; k--)  
  28.      {  
  29.          FatherNode.Elements[k] = FatherNode.Elements[k - 1];  
  30.      }  
  31.      //將被分裂的頁(yè)的中間節(jié)點(diǎn)插入父節(jié)點(diǎn)  
  32.      FatherNode.Elements[position - 1] = NodeToBeSplit.Elements[NumPerNode / 2];  
  33.      //父節(jié)點(diǎn)元素大小+1  
  34.      FatherNode.elementNum += 1;  
  35.      //將FatherNode,NodeToBeSplit,newNode寫(xiě)回磁盤(pán),三次IO寫(xiě)操作  
  36.  
  37.  } 

代碼4.分裂節(jié)點(diǎn)

 

通過(guò)概念和代碼不難看出，節(jié)點(diǎn)的分裂相對(duì)比較消耗IO，這也是為什么SQL Server中需要一些最佳實(shí)現(xiàn)比如不用GUID做聚集索引，或是設(shè)置填充因子等來(lái)減少頁(yè)分裂。

而如果需要插入元素的節(jié)點(diǎn)不滿，則不需要頁(yè)分裂，則需要從根開(kāi)始查找，找到需要被插入的節(jié)點(diǎn)，如代碼5所示。

  1. //在節(jié)點(diǎn)非滿時(shí)尋找插入節(jié)點(diǎn)  
  2. public void BTreeInsertNotFull(TreeNode<T> Node, T KeyWord)  
  3. {  
  4.     int i=Node.elementNum;  
  5.     //如果是葉子節(jié)點(diǎn)，則尋找合適的位置直接插入  
  6.     if (Node.IsLeaf)  
  7.     {  
  8.           
  9.         while (i >= 1 && KeyWord.CompareTo(Node.Elements[i - 1]) < 0)  
  10.         {  
  11.             Node.Elements[i] = Node.Elements[i - 1];//所有的元素后推一位  
  12.             i -= 1;  
  13.         }  
  14.         Node.Elements[i - 1] = KeyWord;//將關(guān)鍵字插入節(jié)點(diǎn)  
  15.         Node.elementNum += 1;  
  16.         //將節(jié)點(diǎn)寫(xiě)入磁盤(pán)，IO寫(xiě)+1  
  17.     }  
  18.     //如果是非葉子節(jié)點(diǎn)  
  19.     else 
  20.     {  
  21.         while (i >= 1 && KeyWord.CompareTo(Node.Elements[i - 1]) < 0)  
  22.         {  
  23.             i -= 1;  
  24.         }  
  25.         //這步將指針?biāo)赶虻墓?jié)點(diǎn)讀入內(nèi)存,IO讀+1  
  26.         if (Node.Pointer[i].elementNum == NumPerNode)  
  27.         {  
  28.             //如果子節(jié)點(diǎn)已滿，進(jìn)行節(jié)點(diǎn)分裂  
  29.             BTreeSplitNode(Node, i, Node.Pointer[i]);  
  30.  
  31.         }  
  32.         if (KeyWord.CompareTo(Node.Elements[i - 1]) > 0)  
  33.         {  
  34.             //根據(jù)關(guān)鍵字的值決定插入分裂后的左孩子還是右孩子  
  35.             i += 1;  
  36.         }  
  37.         //迭代找葉子，找到葉子節(jié)點(diǎn)后插入  
  38.         BTreeInsertNotFull(Node.Pointer[i], KeyWord);  
  39.            
  40.  
  41.     }  
  42. } 

代碼5.插入

 

通過(guò)代碼5可以看出，我們沒(méi)有進(jìn)行任何迭代。而是從根節(jié)點(diǎn)開(kāi)始遇到滿的節(jié)點(diǎn)直接進(jìn)行分裂。從而減少了性能損失。

再將根節(jié)點(diǎn)分裂的特殊情況考慮進(jìn)去，我們從而將插入操作合為一個(gè)函數(shù)，如代碼6所示。

  1. public void BtreeInsert(T KeyWord)  
  2. {  
  3.     if (RootNode.elementNum == NumPerNode)  
  4.     {  
  5.  
  6.         //如果根節(jié)點(diǎn)滿了，則對(duì)跟節(jié)點(diǎn)進(jìn)行分裂  
  7.         TreeNode<T> newRoot = new TreeNode<T>();  
  8.         newRoot.elementNum = 0;  
  9.         newRoot.IsLeaf = false;  
  10.         //將newRoot節(jié)點(diǎn)變?yōu)楦?jié)點(diǎn)  
  11.         BTreeSplitNode(newRoot, 1, RootNode);  
  12.         //分裂后插入新根的樹(shù)  
  13.         BTreeInsertNotFull(newRoot, KeyWord);  
  14.         //將樹(shù)的根進(jìn)行變換  
  15.         RootNode = newRoot;  
  16.     }  
  17.     else 
  18.     {  
  19.         //如果根節(jié)點(diǎn)沒(méi)有滿，直接插入  
  20.         BTreeInsertNotFull(RootNode, KeyWord);  
  21.     }  
  22. } 

代碼6.插入操作

 

現(xiàn)在，我們就可以通過(guò)插入操作，來(lái)實(shí)現(xiàn)一個(gè)B樹(shù)了。

B樹(shù)的查找

既然B樹(shù)生成好了，我們就可以對(duì)B樹(shù)進(jìn)行查找了。B樹(shù)的查找實(shí)現(xiàn)相對(duì)簡(jiǎn)單，僅僅是從跟節(jié)點(diǎn)進(jìn)行迭代，如果找到元素則返回節(jié)點(diǎn)和位置，如果找不到則返回NULL.

  1. //從B樹(shù)中搜索節(jié)點(diǎn)，存在則返回節(jié)點(diǎn)和元素在節(jié)點(diǎn)的值，否則返回NULL  
  2. public returnValue<T> BTreeSearch(TreeNode<T> rootNode, T keyword)  
  3. {  
  4.     int i = 1;  
  5.       
  6.     while (i <= rootNode.elementNum && keyword.CompareTo(rootNode.Elements[i - 1])>0)  
  7.     {  
  8.         i = i + 1;  
  9.     }  
  10.     if (i <= rootNode.elementNum && keyword.CompareTo(rootNode.Elements[i - 1]) == 0)  
  11.     {  
  12.         returnValue<T> r = new returnValue<T>();  
  13.         r.node = rootNode.Pointer[i];  
  14.         r.position = i;  
  15.         return r;  
  16.     }  
  17.     if (rootNode.IsLeaf)  
  18.     {  
  19.         return null;  
  20.     }  
  21.     else 
  22.     {  
  23.         //從磁盤(pán)將內(nèi)容讀出來(lái),做一次IO讀  
  24.         return BTreeSearch(rootNode.Pointer[i], keyword);  
  25.     }  
  26. } 

代碼7.對(duì)B樹(shù)進(jìn)行查找

 

順帶說(shuō)一下，returnValue類(lèi)僅僅是對(duì)返回值的一個(gè)封裝，代碼如代碼8所示。

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

代碼8.returnValue的代碼

總  結(jié)

本文從B樹(shù)的概念原理，以及為什么需要B樹(shù)到B樹(shù)的實(shí)現(xiàn)來(lái)闡述B樹(shù)的概念。B樹(shù)是一種非常優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)。是關(guān)系數(shù)據(jù)庫(kù)和文件系統(tǒng)的核心算法。對(duì)于B樹(shù)的了解會(huì)使得你對(duì)于數(shù)據(jù)庫(kù)的學(xué)習(xí)更加系統(tǒng)和容易。

源碼下載地址：http://down.51cto.com/data/369940

原文鏈接：http://www.cnblogs.com/CareySon/archive/2012/04/06/2435349.html

【編輯推薦】

  1. C#開(kāi)發(fā)高性能Log Help類(lèi)設(shè)計(jì)開(kāi)發(fā)
  2. 溫故而知新之C#中的Stream篇
  3. C#幾個(gè)經(jīng)常犯錯(cuò)誤匯總
  4. 淺談面向?qū)ο蟪绦蛟O(shè)計(jì)C#中的類(lèi)
  5. 淺析你所不了解的C#協(xié)變和逆變
責(zé)任編輯：林師授 來(lái)源： 宋沄劍的博客
C#
相關(guān)推薦

2020-05-06 16:41:36

紅黑樹(shù)二叉查找樹(shù)

2009-09-03 10:52:41

C#遞歸樹(shù)

2021-04-07 09:26:37

Java數(shù)據(jù)結(jié)構(gòu)算法

2020-04-01 18:08:57

MySQL B-樹(shù)B+樹(shù)

2019-08-29 10:46:22

MySQL索引數(shù)據(jù)庫(kù)

2023-08-29 08:31:13

B+樹(shù)數(shù)據(jù)索引

2009-08-11 13:29:57

C#二叉樹(shù)遍歷

2009-08-27 09:57:50

C# Lambda表達(dá)

2019-09-24 09:33:53

MySQLB+樹(shù)InnoDB

2009-05-27 09:38:32

C#二叉樹(shù)樹(shù)

2009-09-02 13:01:11

C#多路廣播

2022-12-06 07:53:33

MySQL索引B+樹(shù)

2025-03-06 08:16:08

lambda表達(dá)式變量

2021-06-02 10:23:06

索引B+樹(shù)數(shù)據(jù)

2024-05-22 09:01:53

InnoDBB+索引

2021-09-29 10:19:00

算法平衡二叉樹(shù)

2022-10-12 23:25:17

二叉樹(shù)父節(jié)點(diǎn)根節(jié)點(diǎn)

2019-12-31 09:33:03

MongoDBB 樹(shù)NoSQL

2021-04-19 10:03:33

MongoDbB 樹(shù) B+ 樹(shù)

2021-10-09 18:26:59

二叉樹(shù)多叉樹(shù)搜索
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)