# Balanced Trees and B-Trees

Search trees that maintain a height invariant so operations stay logarithmic, with B-trees widening nodes specifically to suit block storage.

**Rests on:** Big-O Notation, Binary Search, Binary Tree Traversal

*Machine Learning · Data Structures*


## Why learn this

This is worth your time because it explains how computers find information in massive datasets with incredible speed. Without these structures, searching for a record in a database like PostgreSQL or MySQL would be painfully slow, requiring the system to check every single entry one by one. Understanding this gives you the mental model for why database indexes work and why inserting new data can sometimes take longer than expected. It also helps you compare different methods of finding data quickly, such as hash functions, each of which makes a different trade-off between speed, memory usage, and order.


## The intuition

Imagine you have a list of 1,000 names written on a single long sheet of paper. To find a specific name, you might have to read all 1,000 entries. This is slow because the time grows directly with the size of the list. Now imagine you organize these names into a hierarchy. You split the list into 10 groups, and for each group, you keep only the first and last name on a summary page. To find a name, you look at those 10 summary pages to pick the right group (10 checks). Then, within that group of roughly 100 names, you look again to narrow it down. If you repeat this process—splitting the remaining list into smaller and smaller groups—you reduce the search space dramatically. With a balanced structure, finding a name might take only about 30 steps instead of 1,000. The key is balance: if you add names in sorted order to a poorly designed system, it might become a long, single line again (like your original sheet), forcing you back to slow, linear checks. A balanced tree prevents this by ensuring every path from the top to the bottom is roughly the same length. A B-tree takes this further by making each "page" in your hierarchy wider. Instead of holding just two names, a page might hold hundreds. This is designed for disk storage: reading one large block of data from a hard drive is fast and efficient, while jumping between many small pieces is slow.


## An analogy

Think of looking up a word in a massive printed encyclopedia. You do not start at page one and read every page. Instead, you look at the table of contents (the top levels of the tree) to see which section contains the letter 'B'. Then you flip to that section and look at its sub-headings to find the specific range for 'Ba' through 'Be'. Finally, you scan those few pages to find the exact word. A balanced tree ensures that no matter which word you need, the number of steps—looking at the big categories, then the sub-categories, then scanning—is roughly the same. This structure is efficient because it avoids checking every single item. The analogy works well for the logic: you use broad categories to eliminate large swaths of irrelevant data quickly. It falls short only when considering physical storage: in a real encyclopedia, each page is small, whereas in a B-tree, each "page" (or node) is often the entire size of a computer's disk block, holding hundreds or thousands of entries at once to minimize the time spent physically moving data.


## Definition

A balanced tree is a hierarchical data structure where every path from the top to the bottom is roughly the same length, ensuring that search operations remain fast regardless of how the data is ordered. A B-tree is a variation of this structure designed for storage systems, where each node holds many keys and child pointers to align with disk block sizes, minimizing slow physical disk reads.


## How it connects

This sits beside Hash Functions and Bloom Filters, which are other methods for finding data quickly but do not maintain order or support range queries. It also connects directly to Binary Tree Traversal, a technique for visiting every node in the structure systematically; specifically, traversing a balanced search tree in order will always produce the data sorted from smallest to largest.


## The mathematics

This concept rests on counting how many items fit into a structure that branches out. We do not need algebra or calculus. We only need to know how numbers grow when we multiply them by themselves.

The key idea is 'logarithmic'. This word sounds scary, but it just describes a specific pattern of growth. It means that as the number of items grows very large, the number of steps (or levels) in the tree grows very slowly. 

Think of it this way: if you have a pile of papers and you can throw away half of them at each step by looking at just one piece of paper, how many steps does it take to get down to one paper? This is what a balanced binary tree does.

In a binary tree, every node (a box in the tree) splits into exactly two children. 
- At level 0 (the root), you have 1 node.
- At level 1, those 1 node splits into 2 nodes.
- At level 2, those 2 nodes split into 4 nodes.
- At level 3, those 4 nodes split into 8 nodes.

The number of nodes at any level is 2 raised to the power of that level number. 
Level 0: 2^0 = 1 node.
Level 1: 2^1 = 2 nodes.
Level 2: 2^2 = 4 nodes.
Level 3: 2^3 = 8 nodes.

The total capacity of a tree is the sum of all nodes at all levels. If a tree has height h (meaning there are h+1 levels, from level 0 to level h), the maximum number of items it can hold is 2^(h+1) minus 1. 

Why do we care? Because we can reverse this question. If I have n items, how many levels do I need? We look for the smallest integer h such that 2^h is greater than or equal to n. This h is roughly the base-2 logarithm of n.

For a B-tree, the branching factor is larger. Instead of splitting into 2, each node splits into t children, where t is a number like 100 or 1,000. 
Level 0: 1 node.
Level 1: t nodes.
Level 2: t * t nodes (or t squared).
Level h: t^h nodes.

The height of a B-tree with minimum degree t (where each internal node has at least t children) is bounded by the logarithm base t of n. Specifically, the height h is less than or equal to the ceiling of log_t((n+1)/2). The 'ceiling' function means we round up to the next whole number because you cannot have a fraction of a level.

The operation we use to move down the tree is simple comparison. We compare the search key (the number we are looking for) to the keys stored in the current node. Based on whether the search key is smaller, equal to, or larger than the stored keys, we choose which child branch to follow. This is arithmetic and logic, nothing more.

For an unbalanced tree, this logic fails. If the tree degenerates into a straight line (like a linked list), the height becomes equal to n. You must check every single item. A balanced tree ensures the height stays small.


## A worked example

Let us work through two concrete cases: a balanced binary tree and a B-tree.

Case 1: Balanced Binary Tree with 1,000,000 items.

We need to find the smallest integer h such that 2^h is at least 1,000,000. 
Let us test powers of 2:
2^10 = 1,024. This is too small.
2^20 = (2^10) * (2^10) = 1,024 * 1,024.
1,024 * 1,024 = 1,048,576.

Since 1,048,576 is greater than 1,000,000, a height of 20 levels is sufficient. 
Note: The formula h <= ceiling(log_2(n+1)) gives approximately log_2(1,000,001) which is about 19.93. Rounding up gives 20.

So, in a balanced binary tree with 1 million items, you will visit at most 20 nodes to find an item.

Case 2: B-tree with branching factor 100.

Here, each node can have up to 100 children. This means the capacity grows by a factor of 100 at each level.
Level 0: 1 node.
Level 1: 100 nodes.
Level 2: 100 * 100 = 10,000 nodes.
Level 3: 100 * 100 * 100 = 1,000,000 nodes.

We need to hold 1,000,000 items. 
At level 2, we can hold 10,000 items. This is not enough.
At level 3, we can hold 1,000,000 items. This is enough.

So the height is 3 levels. 
Comparison: 20 steps vs 3 steps. The B-tree is much faster because each step eliminates more possibilities.

Case 3: Step-by-step search in a small B-tree.

Suppose we have a B-tree where each node holds up to 2 keys and has 3 children (degree t=3). 
We want to search for the number 42.

Step 1: Start at the root node.
The root contains keys [30, 70].
We compare our target 42 to these keys.
Is 42 < 30? No.
Is 42 > 70? No.
Therefore, 42 must be between 30 and 70. We follow the middle child pointer.

Step 2: Arrive at the second node.
This node contains keys [40, 50].
We compare our target 42 to these keys.
Is 42 < 40? No.
Is 42 > 50? No.
Therefore, 42 must be between 40 and 50. We follow the middle child pointer of this node.

Step 3: Arrive at a leaf node.
This node contains keys [41, 42, 43].
We scan these keys linearly (since there are only three).
Is 42 == 41? No.
Is 42 == 42? Yes.

Result: We found the item 42 in exactly 3 node visits. 

In contrast, if this data were stored in an unbalanced binary tree that had degenerated into a straight line (a linked list), we might have to visit all 1,000,000 nodes in the worst case. The structure of the B-tree guarantees we only need 3 visits.


## From scratch, in Python

```python
class BTreeNode:
    def __init__(self, leaf=False):
        self.keys = []          # a list of keys, sorted
        self.children = []      # a list of child nodes (empty if leaf)
        self.leaf = leaf        # True if this node has no children

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(leaf=True)
        self.t = t              # minimum degree

    def search(self, key, node=None):
        if node is None:
            node = self.root
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and key == node.keys[i]:
            return (node, i)
        elif node.leaf:
            return None
        else:
            return self.search(key, node.children[i])

# Example usage:
btree = BTree(t=2)
# (We'd need an insert method for a full example, but this shows the structure.)
print(btree.search(42))  # None, since tree is empty
```


## The same thing, with a framework

In practice, you rarely implement B-trees yourself; you use a database engine. In Python, you might use SQLite (which uses B-trees internally) or an external library like `btree` (for Python's Berkeley DB). For example:

```python
import sqlite3
conn = sqlite3.connect('example.db')
c = conn.cursor()
c.execute('CREATE TABLE users (id INTEGER PRIMARY KEY, name TEXT)')
c.execute('INSERT INTO users (name) VALUES ("Alice")')
# SQLite automatically creates a B-tree index on the primary key
```

The `sqlite3` module is part of Python's standard library. The `CREATE TABLE` statement creates an index (a B-tree) on the id column automatically. When you later do `SELECT * FROM users WHERE id = 123`, SQLite uses that B-tree to find the row in O(log n) time instead of scanning the whole table. Underneath, SQLite is doing exactly what our `search` method does — it reads a node, compares keys, and follows a child pointer — but it's optimized and written in C for speed.


## What the code does

First, we define a BTreeNode. It has three attributes: `keys` is a list that stores the keys in ascending order — this is what we search within. `children` is a list of child nodes, and `leaf` is a boolean (True/False) telling us whether this node has any children — a leaf is a bottom node with no children. In Python, a list is an ordered collection that can be changed (you can add or remove items). A boolean is a value that is either True or False. The BTree class is the whole tree — it has a root node and a minimum degree `t`. The minimum degree `t` controls how many keys a node can hold: at least t-1 keys and at most 2t-1 keys. The `search` method takes a `key` and a `node`. It starts at the root if no node is given. It uses a `while` loop to move through the keys in the current node, comparing `key` with each key. If it finds an exact match, it returns the node and the index. If not, and if the node is a leaf, the key isn't in the tree, so it returns None. Otherwise, it recurses into the appropriate child (the child at index `i`). In the example, we create a B-tree with t=2 (so nodes can have 1 to 3 keys) and call `search(42)`, which returns None because the tree is empty. This code is intentionally minimal — a full implementation would need `insert` with node splitting, but this shows the lookup logic.


## Common misconceptions

**Balanced means perfectly symmetrical** — A balanced tree has to look like a perfect pyramid — every branch the same length.

That's actually a perfectly balanced tree. But perfect balance is expensive to maintain — every insertion would require moving many nodes. Instead, balanced trees like AVL or red-black allow some imbalance, as long as the height stays logarithmic. For example, a red-black tree allows the longest path to be at most twice as long as the shortest. In fact: Balanced means the height is O(log n), not that the tree is perfectly symmetric. There's always a bound on how much the paths can differ.

**B-tree is the same as a binary tree** — B-tree is just a binary tree with a B in front.

A binary tree has at most two children per node. A B-tree can have any number of children (as determined by its degree). That's the whole point — wider nodes reduce the height and suit disk blocks. In fact: A B-tree is a different family of trees: nodes can hold many keys and many children, and the height stays short even with millions of items.

**Balancing is only for insertion** — You only need to balance when you insert; deletion doesn't affect balance.

Deleting a key can also unbalance the tree (e.g., removing a node that caused a subtree to become too small). AVL and red-black trees rebalance on both insertion and deletion. In fact: Both insertion and deletion can break the height invariant, and both need rebalancing to restore it.

**B-tree is only used in databases, not in memory** — B-trees are only for disk; you wouldn't use them in memory.

B-trees are also used in memory, e.g., in many file systems (like NTFS's MFT) and in some key-value stores. They're not limited to databases. But they're especially valuable on disk because of their block alignment. In fact: B-trees are a general search tree structure, widely used on disk but also in-memory in certain contexts.


## In short

Balanced trees (like AVL, red-black) maintain a height invariant so search, insert, delete all run in O(log n). B-trees are a form of balanced tree with wide nodes (many keys per node), specifically designed for disk storage. They minimize disk seeks by aligning node size with block size. They back nearly every database index you'll use. Unbalanced trees degrade to linked lists on sorted input, so balancing is essential for predictable performance.


## Where this is used

Balanced trees and B-trees are everywhere in AI systems, often behind the scenes.

**Large language models (LLMs):** LLMs like ChatGPT store their training data and model weights in files, but when you're serving them, you need fast access to token indices, embedding lookup tables, and metadata. These are stored in databases that use B-trees. For example, the tokenizer vocabulary used by an LLM — mapping text to token IDs — is often stored in a hash map, but for range queries (e.g., finding all tokens that start with 'art'), a B-tree index would be used. More importantly, the vector databases used for retrieval-augmented generation (RAG) often use tree-based indexes (like ANNOY or HNSW) that are conceptually similar to balanced trees in that they partition space to speed up nearest-neighbour search. The mechanism: each node covers a region of the vector space, and the search prunes branches that can't contain the nearest neighbour.

**Small models on devices (e.g., on a phone):** These models are stored as files. When you load a model, you read it from disk. The model file might have an index to let you quickly find a weight tensor — that index could be a B-tree. Also, on-device databases (like SQLite used in Android and iOS) use B-trees for all queries. When an app searches a local contact list or a cached image database, the B-tree index is what makes it fast.

**Retrieval-augmented generation (RAG):** RAG involves retrieving relevant documents from a corpus and passing them to an LLM. The retrieval step uses an index of embeddings. While that's often an approximate nearest-neighbour (ANN) index like HNSW, the underlying metadata — the mapping from embedding IDs to document text — is stored in a database with a B-tree index. The mechanism: the ANN index returns a set of candidate IDs; then the system looks up those IDs in a B-tree index to fetch the actual text. Without the B-tree, you'd have to scan all documents to find the ones matching the IDs.

**Agentic systems:** An agent that plans and calls tools often maintains a database of its state, files, or conversation history. Queries like 'find all tasks scheduled for today' are range queries, which B-trees handle efficiently. The agent might use SQLite or a similar embedded database, and every query goes through a B-tree index.

**Everyday applied ML (recommendation, vision, fraud detection):** In recommendation systems, user-item interaction data is stored in databases (e.g., MySQL, PostgreSQL) with B-tree indexes on user IDs and item IDs to support fast lookups and range queries (e.g., 'all items a user bought in the last month'). In vision, feature databases used for image retrieval again use indices. In fraud detection, transactional data is queried with time-range filters — again a B-tree on the timestamp column enables fast queries.

**What a developer actually writes:** In most cases, they write SQL or use a database API. Underneath, they rely on the database's built-in indexes (B-trees). For example:

```sql
CREATE INDEX idx_orders_time ON orders(order_time);
SELECT * FROM orders WHERE order_time BETWEEN '2025-01-01' AND '2025-01-31';
```

The `CREATE INDEX` statement builds a B-tree on the `order_time` column. Without it, the database would have to scan every row. With it, the database can traverse the B-tree, following blocks from root to leaf, reading only the relevant pages from disk.

**What breaks when done badly:** If you fail to index the right columns, queries become slow. If you create too many indexes, inserts and updates become slow because every index must be maintained. If you use a database without B-trees (like a simple hash-based store), you lose the ability to do range queries efficiently. This is the practical reason B-trees are a core skill.


---

Read this on the web: https://basavapurushottam.com/learn-ai/balanced-trees-and-b-trees
