B-trees for databases in Data Structures Theory - Time & Space Complexity

Time Complexity: B-trees for databases

O(log n)

Understanding Time Complexity

When using B-trees in databases, it is important to understand how the time to find, insert, or delete data grows as the database gets bigger.

We want to know how the number of steps changes when the amount of data increases.

Scenario Under Consideration

Analyze the time complexity of searching for a key in a B-tree.

function searchBTree(node, key) {
  if (node == null) return null;
  let i = 0;
  while (i < node.keys.length && key > node.keys[i]) {
    i++;
  }
  if (i < node.keys.length && key === node.keys[i]) {
    return node.values[i];
  } else if (node.isLeaf) {
    return null;
  } else {
    return searchBTree(node.children[i], key);
  }
}

This code searches for a key by checking keys in nodes and moving down the tree until it finds the key or reaches a leaf.

Identify Repeating Operations

• Primary operation: Comparing the key with keys in a node (loop inside each node).
• How many times: This happens once per tree level, moving down from root to leaf.

How Execution Grows With Input

As the database grows, the B-tree grows taller slowly because each node holds many keys.

Input Size (n)	Approx. Operations
10	About 2-3 node checks
100	About 3-4 node checks
1000	About 4-5 node checks

Pattern observation: The number of steps grows slowly, roughly with the height of the tree, which increases very slowly as data grows.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find or insert data grows slowly, roughly proportional to the logarithm of the data size.

Common Mistake

[X] Wrong: "Searching a B-tree takes time proportional to the number of keys because it checks all keys."

[OK] Correct: Each node holds many keys, but the search only checks a few keys per node and moves down the tree levels, so it does not check all keys in the whole tree.

Interview Connect

Understanding B-tree time complexity shows you can reason about how databases keep searches fast even with lots of data, a useful skill in many real-world systems.

Self-Check

"What if each B-tree node could hold twice as many keys? How would the time complexity change?"