数据结构中的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次浏览

启动你的 职业生涯

完成课程以获得认证

开始