<optgroup id="6y7f6"><small id="6y7f6"></small></optgroup>

<code id="6y7f6"></code>

  • <p id="6y7f6"><tbody id="6y7f6"><ins id="6y7f6"></ins></tbody></p>
    <code id="6y7f6"><form id="6y7f6"></form></code>

      圖解B樹及C#實現(3)數據的刪除

      前言

      本文為系列文章

      1. B樹的定義及數據的插入
      2. 數據的讀取及遍歷
      3. 數據的刪除

      閱讀本文前,建議先復習前兩篇文章,以便更好的理解本文。

      從刪除的數據所在的節點可分為兩種情況:

      1. 從葉子節點刪除數據
      2. 從非葉子節點刪除數據

      無論從葉子節點還是非葉子節點刪除數據時都需要保證B樹的特性:非根節點每個節點的 key 數量都在 [t-1, 2t-1] 之間。

      借此保證B樹的平衡性。

      之前介紹的插入數據關注的是這個范圍的上限 2t-1,插入時,如果節點的 key 數量大于 2t-1,就需要進行數據的分裂。

      而刪除數據則關注是下限 t-1,如果節點的 key 數量小于 t-1,就需要進行數據的移動或者合并。

      刪除數據時,需要考慮的情況比較多,本文會分別討論這些情況,但一些比較邊緣的情況為避免描述過于復雜,不再文中討論,而是在代碼中進行了注釋。

      因為刪除邏輯比較復雜,請結合完整代碼進行閱讀。
      https://github.com/eventhorizon-cli/EventHorizon.BTree/blob/b51881719146a86568669cdc78f8524299bee33d/src/EventHorizon.BTree/BTree.cs#L139

      從葉子節點刪除數據

      如果待刪除的數據在葉子節點,且該節點的 Item 數量大于 t-1,那么直接刪除該數據即可。

      從非葉子節點刪除數據

      如果待刪除的數據在非葉子節點,那么需要先找到該數據的左子節點,然后將左子節點的數據替換到待刪除的數據,最后再刪除左子節點的數據。

      這樣能保證被刪除數據的節點的 Item 數量不變,保證 B樹 有 k 個子節點的非葉子節點擁有 k ? 1 個鍵的特性不受破壞。

      提前擴充只有 t-1 的 Item 的節點:維持 B樹 平衡的核心算法

      在數據插入的時候,為了避免回溯性的節點分裂,我們提前將已滿的子節點進行分裂。

      同樣的在數據刪除,不斷往下遞歸查找時,如果遇到只有 t-1 個 Item 的節點,我們也需要提前將其擴充,以避免回溯性的節點處理。

      擴充的節點不一定是最后數據所在的節點,只是向下查找過程中遇到的節點。

      節點擴充的分為兩類,一個是從兄弟節點借用 Item,一個是合并兄弟節點,被借用的兄弟節點需要滿足 Item 數量大于 t-1。具體可分為以下三種情況:

      從左兄弟節點借用 Item

      待擴充節點的左兄弟節點存在且左兄弟節點的 Item 數量 > t-1 時,從左兄弟節點借用 Item 進行擴充。

      為了保證 B樹 數據的順序特性:任意 Item 的左子樹中的 Key 均小于該 Item 的 Key,右子樹中的 Key 均大于該 Item 的 Key。需要交換左兄弟節點的最右邊的 Item 和父節點中對應位置的 Item(位于左兄弟節點右側)。

      以下圖為例進行說明:

      從右兄弟節點借用 Item

      待擴充節點的左兄弟節點不存在或者左兄弟節點的 Item 數量 只有 t-1 時,無法外借。但右兄弟節點存在且右兄弟節點的 Item 數量 > t-1 時,從右兄弟節點借用 Item 進行擴充。

      以下圖為例進行說明:

      從兄弟節點進行擴充可以概括為:借用,交換,插入。

      與左兄弟節點或者右兄弟節點合并

      如果待擴充節點的左兄弟節點和右兄弟節點都不存在或者都只有 t-1 個 Item 時,無法外借。此時需要與左兄弟節點或者右兄弟節點進行合并。

      以下圖為例進行說明:

      最值的刪除

      之前章節介紹過 B樹 最值的查找:

      1. 最小值:從根節點開始,一直往左子樹走,直到葉子節點。
      2. 最大值:從根節點開始,一直往右子樹走,直到葉子節點。

      最值的刪除就是先找到最值的位置并將其刪除,在向下尋找的過程中,需要和普通的數據刪除一樣,對節點進行擴充或者合并。

      代碼實現

      最值刪除是刪除的特殊情況,我們定義一個枚舉用來區分普通數據的刪除,最小值的刪除以及最大值的刪除,這三種方式只在數據查找的時候有所區分,其他的邏輯都是一樣的。

      internal enum RemoveType
      {
          Item,
          Min,
          Max
      }
      
      public sealed class BTree<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue?>>
      {
          public bool TryRemove([NotNull] TKey key, out TValue? value)
          {
              ArgumentNullException.ThrowIfNull(key);
      
              return TryRemove(key, RemoveType.Item, out value);
          }
      
          public bool TryRemoveMax(out TValue? value) => TryRemove(default, RemoveType.Max, out value);
      
          public bool TryRemoveMin(out TValue? value) => TryRemove(default, RemoveType.Min, out value);
      
              private bool TryRemove(TKey? key, RemoveType removeType, out TValue? value)
          {
              if (_root == null || _root.IsItemsEmpty)
              {
                  value = default;
                  return false;
              }
      
              bool removed = _root.TryRemove(key, removeType, out var item);
              if (_root.IsItemsEmpty && !_root.IsLeaf)
              {
                  // 根節點原來的兩個子節點進行了合并,根節點唯一的元素被移動到了子節點中,需要將合并后的子節點設置為新的根節點
                  _root = _root.GetChild(0);
              }
      
              if (removed)
              {
                  _count--;
                  value = item!.Value;
                  return true;
              }
      
              value = default;
              return removed;
          }
      }
      

      主要的邏輯定義在 Node 中,不斷向下遞歸

      internal class Node<TKey, TValue>
      {
              public bool TryRemove(TKey? key, RemoveType removeType, [MaybeNullWhen(false)] out Item<TKey, TValue?> item)
          {
              int index = 0;
              bool found = false;
              if (removeType == RemoveType.Max)
              {
                  if (IsLeaf)
                  {
                      if (_items.Count == 0)
                      {
                          item = default;
                          return false;
                      }
      
                      // 如果是葉子節點,直接刪除最后一個元素,就是刪除最大的 Item
                      item = _items.RemoveLast();
                      return true;
                  }
      
                  // 當前節點不是葉子節點,需要找到最大的子節點,繼續向下查找并刪除
                  index = ItemsCount;
              }
      
              if (removeType == RemoveType.Min)
              {
                  if (IsLeaf)
                  {
                      if (_items.Count == 0)
                      {
                          item = default;
                          return false;
                      }
      
                      // 當前節點是葉子節點,直接刪除第一個元素,就是刪除最小的 Item
                      item = _items.RemoveAt(0);
                      return true;
                  }
      
                  // 當前節點不是葉子節點,需要找到最小的子節點,繼續向下查找并刪除
                  index = 0;
              }
      
              if (removeType == RemoveType.Item)
              {
                  // 如果沒有找到,index 表示的是 key 可能在的子樹的索引
                  found = _items.TryFindKey(key!, out index);
      
                  if (IsLeaf)
                  {
                      // 如果是葉子節點,能找到就刪除,找不到就返回 false,表示刪除失敗
                      if (found)
                      {
                          item = _items.RemoveAt(index);
                          return true;
                      }
      
                      item = default;
                      return false;
                  }
              }
      
              // 如果當前節點的左子節點的 Item 個數小于最小 Item 個數,就需要進行合并或者借元素
              // 這個處理對應兩種情況:
              // 1. 要刪除的 Item 不在當前節點的子節點中,為避免刪除后導致數據所在節點的 Item 個數小于最小 Item 個數,需要先進行合并或者借元素。
              // 2. 要刪除的 Item 就在當前節點中,為避免刪除后導致當前節點的 Item 個數小于最小 Item 個數,需要先從左子節點中借一個 Item 過來,保證當前節點的 Item 數量不變。
              // 為此先要保證左子節點被借用后的 Item 個數不小于最小 Item 個數。
              if (_children[index].ItemsCount <= _minItems)
              {
                  return GrowChildrenAndTryRemove(index, key!, removeType, out item);
              }
      
              var child = _children[index];
      
              if (found)
              {
                  // 如果在當前節點找到了,就刪除當前節點的 Item,然后將 左子節點 中的最大的 Item 移動到當前節點中
                  // 以維持當前節點的 Item 個數不變,保證 B樹 有 k 個子節點的非葉子節點擁有 k ? 1 個鍵的特性。
                  item = _items[index];
                  child.TryRemove(default!, RemoveType.Max, out var stolenItem);
                  _items[index] = stolenItem;
                  return true;
              }
      
              return child.TryRemove(key!, removeType, out item);
          }
      
          private bool GrowChildrenAndTryRemove(
              int childIndex,
              TKey key,
              RemoveType removeType,
              [MaybeNullWhen(false)] out Item<TKey, TValue?> item)
          {
              if (childIndex > 0 && _children[childIndex - 1].ItemsCount > _minItems)
              {
                  // 如果左邊的子節點存在且左邊的子節點的item數量大于最小值,則從左邊的子節點借一個item
                  var child = _children[childIndex];
                  var leftChild = _children[childIndex - 1];
                  var stolenItem = leftChild._items.RemoveLast();
                  child._items.InsertAt(0, _items[childIndex - 1]);
                  _items[childIndex - 1] = stolenItem;
                  if (!leftChild.IsLeaf)
                  {
                      // 非葉子節點的子節點需要保證數量比item多1,item數量變了,子節點數量也要變
                      // 所以需要從左邊的子節點中移除最后一個子節點,然后插入到當前子節點的第一個位置
                      child._children.InsertAt(0, leftChild._children.RemoveLast());
                  }
              }
              else if (childIndex < ChildrenCount - 1 && _children[childIndex + 1].ItemsCount > _minItems)
              {
                  // 如果右邊的子節點存在且右邊的子節點的item數量大于最小值,則從右邊的子節點借一個item
                  var child = _children[childIndex];
                  var rightChild = _children[childIndex + 1];
                  var stolenItem = rightChild._items.RemoveAt(0);
                  child._items.Add(_items[childIndex]);
                  _items[childIndex] = stolenItem;
                  if (!rightChild.IsLeaf)
                  {
                      // 非葉子節點的子節點需要保證數量比item多1,item數量變了,子節點數量也要變
                      // 所以需要從右邊的子節點中移除第一個子節點,然后插入到當前子節點的最后一個位置
                      child.AddChild(rightChild._children.RemoveAt(0));
                  }
              }
              else
              {
                  // 如果當前節點左右兩邊的子節點的item數量都不大于最小值(例如正好等于最小值 t-1 ),則合并當前節點和右邊的子節點或者左邊的子節點
                  // 優先和右邊的子節點合并,如果右邊的子節點不存在,則和左邊的子節點合并
                  if (childIndex >= ItemsCount)
                  {
                      // ItemCount 代表最的子節點的索引,如果 childIndex 大于等于 ItemCount,說明右邊的子節點不存在,需要和左邊的子節點合并
                      childIndex--;
                  }
      
                  var child = _children[childIndex];
                  var mergeItem = _items.RemoveAt(childIndex);
                  var mergeChild = _children.RemoveAt(childIndex + 1);
                  child._items.Add(mergeItem);
                  child._items.AddRange(mergeChild._items);
                  child._children.AddRange(mergeChild._children);
              }
      
              return TryRemove(key, removeType, out item);
          }
      }
      

      Benchmarks:與 優先隊列 PriorityQueue 的比較

      我們實現的 BTree 支持自定義排序規則,也實現最值的刪除,意味著可以充當優先隊列使用。

      我們使用 PriorityQueue 與 BTree 進行性能對比來看看 B樹 能否充當優先隊列使用。

      入隊性能

      public class BTree_PriorityQueue_EnequeueBenchmarks
      {
          [Params(1000, 1_0000, 10_0000)] public int DataSize;
      
          [Params(2, 4, 8, 16)] public int Degree;
      
          private HashSet<int> _data;
      
          [IterationSetup]
          public void Setup()
          {
              var random = new Random();
              _data = new HashSet<int>();
              while (_data.Count < DataSize)
              {
                  var value = random.Next();
                  _data.Add(value);
              }
          }
      
          [Benchmark]
          public void BTree_Add()
          {
              var btree = new BTree<int, int>(Degree);
      
              foreach (var value in _data)
              {
                  btree.Add(value, value);
              }
          }
      
          [Benchmark]
          public void PriorityQueue_Enqueue()
          {
              var priorityQueue = new PriorityQueue<int, int>(DataSize);
      
              foreach (var value in _data)
              {
                  priorityQueue.Enqueue(value, value);
              }
          }
      }
      

      出隊性能

      public class BTree_PriorityQueue_DequeueBenchmarks
      {
          [Params(1000, 1_0000, 10_0000)] public int DataSize;
      
          [Params(2, 4, 8, 16)] public int Degree;
      
          private BTree<int, int> _btree;
      
          private PriorityQueue<int, int> _priorityQueue;
      
          [IterationSetup]
          public void Setup()
          {
              var random = new Random();
              _btree = new BTree<int, int>(Degree);
              _priorityQueue = new PriorityQueue<int, int>(DataSize);
      
              while (_btree.Count < DataSize)
              {
                  var value = random.Next();
                  _btree.Add(value, value);
                  _priorityQueue.Enqueue(value, value);
              }
          }
      
          [Benchmark]
          public void BTree_Remove()
          {
              while (_btree.Count > 0)
              {
                  _btree.RemoveMin();
              }
          }
      
          [Benchmark]
          public void PriorityQueue_Dequeue()
          {
              while (_priorityQueue.Count > 0)
              {
                  _priorityQueue.Dequeue();
              }
          }
      }
      

      可以看到,B樹 雖然在入隊性能上比 PriorityQueue 差。但在數據量和 degree 較大時,出隊性能比 PriorityQueue 好,是有能力充當優先隊列使用的。

      總結

      B樹 在 degree 較大時,樹的高度較低,刪除的效率較高,可充當優先隊列使用。

      B樹 的插入,刪除,查找都是基于遞歸的,遞歸的深度為樹的高度。

      B樹 對數據的查找基于二分查找,時間復雜度為 O(log n),B樹 的插入和刪除基于 B樹的查找算法,都要找到數據所在的節點,然后在該節點進行插入和刪除。因此,B樹 的插入和刪除的時間復雜度也為 O(log n)。

      B樹 是對二叉樹的一種優化,使得樹的高度更低,但是在插入,刪除的過程中,需要進行大量的節點分裂,合并,借用,交換等操作,使得算法的復雜度更高。

      參考資料

      Google 用 Go 實現的內存版 B樹 https://github.com/google/btree

      B樹 維基百科 https://zh.m.wikipedia.org/zh-hans/B樹

      posted @ 2023-02-04 20:33  黑洞視界  閱讀(373)  評論(0編輯  收藏  舉報
      欧洲黄色网页链接入口,免费A级毛片无码无遮挡久久影院,a免费黄色网址,国产一级黄色的网站
      <optgroup id="6y7f6"><small id="6y7f6"></small></optgroup>

      <code id="6y7f6"></code>

    1. <p id="6y7f6"><tbody id="6y7f6"><ins id="6y7f6"></ins></tbody></p>
      <code id="6y7f6"><form id="6y7f6"></form></code>