Course contentsShow
← Computer Science
Lesson 1679 of 2,87238. Database Transactions and IndexingFree lesson

B-Tree Search Operation

How to search for a key in a B-Tree, navigating from root to leaf through key comparisons.

B-Tree Search Operation

What You'll Learn

You'll learn how to search for a key in a B-Tree by navigating from the root to a leaf node using key comparisons at each level.

How B-Tree Search Works

Searching in a B-Tree follows a top-down path from the root to a leaf node. At each internal node, you compare your target key against the node's sorted keys to decide which child pointer to follow next.

The Search Algorithm

Start at the root node. Each internal node contains sorted keys (k₁, k₂, ..., kₙ) and child pointers. For your target key:

  1. Compare the target against the keys in the current node from left to right
  2. If you find an exact match, the search succeeds
  3. If the target is less than k₁, follow the leftmost child pointer
  4. If the target is between kᵢ and kᵢ₊₁, follow the child pointer between them
  5. If the target is greater than all keys, follow the rightmost child pointer
  6. Repeat until you reach a leaf node or find the key

An Analogy

Think of searching a B-Tree like finding a book in a library with a multi-level index card system. Each card directs you to a more specific section: "Fiction A-M or N-Z?" → "N-Q or R-Z?" → "R-S or T-Z?" until you reach the exact shelf.

Why It's Efficient

Because B-Trees have high branching factors (many keys per node), the tree height stays low even for millions of records. Each comparison eliminates entire subtrees, making searches logarithmic in the number of keys.

Key Takeaway: B-Tree search efficiently locates keys by comparing the target against sorted keys in each node, following child pointers until reaching a leaf—typically requiring only a few disk reads even in massive databases.