Searching in B+ Tree

Searching in a B-tree involves traversing the tree from the root to find the node that might contain the desired key.

Step-by-step algorithm:

Start at the root of the B+ tree.
Check if the current node is a leaf node.
If not a leaf node, compare the search key with the keys in the node to determine the appropriate child node to traverse.
If a leaf node, search for the key within the keys stored in the leaf node.
If the key is found, return the corresponding value.
If the key is not found in any leaf node, return a failure indication (e.g., null or false).
Repeat steps 3-6 until the key is found or until there are no more child nodes to traverse.

Below is the implementation of the above idea:

Python3

import math

# Node creation
class Node:
    def __init__(self, order):
        self.order = order
        self.values = []
        self.keys = []
        self.nextKey = None
        self.parent = None
        self.check_leaf = False

    # Search operation
    def search(self, value):
        current_node = self
        while(not current_node.check_leaf):
            temp2 = current_node.values
            for i in range(len(temp2)):
                if (value == temp2[i]):
                    current_node = current_node.keys[i + 1]
                    break
                elif (value < temp2[i]):
                    current_node = current_node.keys[i]
                    break
                elif (i + 1 == len(current_node.values)):
                    current_node = current_node.keys[i + 1]
                    break
        return current_node

# B plus tree
class BplusTree:
    def __init__(self, order):
        self.root = Node(order)
        self.root.check_leaf = True

    # Search operation
    def search(self, value):
        current_node = self.root
        while(not current_node.check_leaf):
            temp2 = current_node.values
            for i in range(len(temp2)):
                if (value == temp2[i]):
                    current_node = current_node.keys[i + 1]
                    break
                elif (value < temp2[i]):
                    current_node = current_node.keys[i]
                    break
                elif (i + 1 == len(current_node.values)):
                    current_node = current_node.keys[i + 1]
                    break
        return current_node

# Print the tree
def printTree(tree):
    lst = [tree.root]
    level = [0]
    leaf = None
    flag = 0
    lev_leaf = 0

    node1 = Node(str(level[0]) + str(tree.root.values))

    while (len(lst) != 0):
        x = lst.pop(0)
        lev = level.pop(0)
        if (x.check_leaf == False):
            for i, item in enumerate(x.keys):
                print(item.values)
        else:
            for i, item in enumerate(x.keys):
                print(item.values)
            if (flag == 0):
                lev_leaf = lev
                leaf = x
                flag = 1

# Main code
record_len = 3
bplustree = BplusTree(record_len)
bplustree.search('5')

printTree(bplustree)

if(bplustree.search('5')):
    print("Found")
else:
    print("Not found")

Output

Found

Time Complexity: O(log n)
Auxiliary Space: O(1)

B+ Tree in Python

In computer science, data structures are crucial in efficiently managing and organizing data. Among these, the B+ tree is a powerful and important data structure, widely used in databases and file systems. In this article, we will discuss the concept of B+ trees, exploring their structure, operations, and implementation in Python.

B+ Tree in Python

Table of Content

What is a B+ Tree?
Key Characteristics of B+ Trees
Operations on B+ Trees
Searching in B+ Tree
Insertion in B+ Tree
Deletion in B+ Tree

Searching in B+ Tree

B+ Tree in Python

Similar Reads

Contact Us