資料結構中的B樹查詢

下面我們將瞭解如何在B樹中執行搜尋。B樹搜尋也稱為B樹查詢。假設我們有一棵如下所示的B樹−

B樹示例 −

搜尋技術與二叉搜尋樹非常相似。假設我們要從以上樹中搜索66。因此，我們將從根節點開始，現在66大於根元素46。因此，我們將移至根節點的右子節點。然後，右子節點具有多個元素。這些元素是按順序排列的，它們是[56, 81]。我們的目標鍵大於56但小於81，因此我們將進入56和81之間的子樹。然後，我們就移動到了葉層。在這一點上，我們找到了元素66。

讓我們看看在B樹內搜尋元素的演算法。

演算法

BTreeSearch(root, key) −

輸入 − 樹的根節點和要查詢的鍵 

輸出 − 如果不存在具有此鍵的節點，則返回鍵節點的值，否則返回空值

x := Read root
if x is an index node, then
   if there is an object o in x, such that o->key = ‘key’, then return o->val
   Find the child of x, as x->child[i], whose key range is containing ‘key’
   return BTreeSearch(x->child[i], key)
else
   if there is an object o in x, such that o->key = ‘key’, then return o->val,
   else return null
   end if
end if

阿納布·查克拉伯蒂

更新於： 2020年8月11日

592次瀏覽

啟動你的 職業生涯

完成課程以獲得認證

開始