B Trees and B+ Trees

When it comes to indexing and efficient data retrieval in databases, two data structures often come up: B Tree and B+ Tree. While both are balanced tree structures optimized for minimizing disk I/O, there’s a crucial distinction (modern databases almost always use B+ Trees, not B Trees).

The B+ Tree is a refinement of the original B Tree that solves key performance and structural limitations, especially when dealing with large datasets and persistent storage.

Despite some systems (like MongoDB) mentioning “B Trees” in their docs, what they actually implement under the hood is a B+ Tree, and for good reason.

This article will walk you through:

• Why full table scans are costly
• What B Trees are and where they fall short
• How B+ Trees overcome those limitations
• Considerations when using B+ Trees in real-world systems
• Differences in B+ Tree storage cost between MySQL and Postgres

Full Table Scans

When you run a query that doesn’t use indexes or has to scan many rows, the database will perform a full table scan (aka sequential scan).

• The database reads the entire table, page by page, from disk
• Tables are stored as data files, made up of 8KB pages (in Postgres)
• It asks the disk controller to fetch each page — this is expensive I/O
• All rows in all pages are scanned to find matching results

Disk I/O is still the slowest part of the stack. Reading from a disk means waiting on the storage subsystem. You’re pulling in every row, even if you only care about one or a few.

If the DB knows that your query will touch most rows anyway, it may choose a full table scan over using an index (Optimizer Behavior). Especially true for things like:

• No WHERE clause
• Low-selectivity filters (e.g., WHERE status = 'active' on a column where 90% are active)
• Functions on columns (WHERE LOWER(name) = 'paul')
• OR conditions that span unindexed columns

Even when it has to do a full scan, modern databases try to be smart:

• Use parallel workers to scan chunks of the table simultaneously
• Prefetching pages from disk into memory
• Keeping recently read pages in shared buffers (cache)

Still, indexing and partitioning are far more efficient if you can reduce the search space

Always check with EXPLAIN ANALYZE to see if your query is doing a sequential scan — and optimize with indexes or partitions if needed.

B-Tree (Balanced Tree)

The B-Tree is the most commonly used data structure behind traditional database indexes. It’s all about reducing search space so we don’t have to scan entire tables. It’s a multi-level search tree, optimized for disk I/O.

It has a degree m (chosen automatically by the database) where each node can have up to m children and m-1 keys. The degree m impacts how wide the tree grows. A higher m = fewer levels = fewer disk reads.

Structure:

• Root Node — top of the tree
• Internal Nodes — routing logic
• Leaf Nodes — store pointers to actual data

Each node is equal to one disk page (typically 8KB in Postgres). That 8KB page must store keys and pointers efficiently. B-Trees are designed to minimize disk seeks — very cache-friendly. It’s optimized fast lookups, inserts, and deletes — all in O(log n).

Each element in a node stores:

• A key (column value)
• A pointer to the actual row (data pointer)

The data pointer in a B-Tree index can point to either the primary key (as in the case of secondary indexes in MySQL InnoDB and Oracle) or directly to the row (tuple) itself (as in Postgres, where all secondary indexes point directly to the tuple).

In PostgreSQL, a tuple is simply a row in a table. Internally, indexes (especially secondary indexes) in Postgres point directly to these tuples stored in the heap, allowing quick access to the actual row data. This differs from MySQL InnoDB, where secondary indexes point to the primary key, which then leads to the row. By skipping this extra hop, Postgres enables more direct and often faster lookups.

B-Trees drastically reduce reads by pruning branches. Instead of reading all pages, it follows a narrow path from root → leaf.

How the Original B-Tree Boosts Performance

B-Trees are powerful because they minimize disk I/O by drastically reducing the number of pages a database needs to touch during a search.

Consider the following table.

Here, TID = tuple ID — internal pointer (page + offset) where the row lives on disk. B-Tree Index Structure (Simplified) would look something like this:

Each node contains key:value pair where the key is the column being indexed (ID) and the value is the tuple ID. The child pointers are based on key ranges.

So, how the search works is that let’s say you’re searching for ID = 3:

1. Start at root [2, 4]. 3 lies between → go to middle child
2. The middle child has [3:703]
3. Use 703 to directly access the tuple from disk

This skips the full table scan entirely.

In a B-Tree of degree m, each node can have m children and m-1 keys. This setup allows proper routing between children using key ranges. More keys per node = fewer levels = fewer disk reads.

In terms of page and disk performance, each B-Tree node corresponds to a disk page (e.g., 8KB in Postgres). The database aims to pack as many keys and child pointers as possible into a single page. More elements per node means fewer levels in the tree and fewer page splits, leading to better overall performance.

For insert performance, inserts are generally fast — unless a page split occurs. A page split happens when a node is full and a new key needs to be inserted. Random inserts (non-sequential keys) are more likely to trigger splits, while sequential inserts (like monotonically increasing IDs) are far more efficient and avoid frequent page splits.

Let’s add more rows:

The updated B-Tree structure will look something like this:

This structure allows a search to touch only 3 pages to find any row — root → internal → leaf.

B-Trees work best when indexed columns have low update frequency and monotonically increasing values (like timestamps, IDs).

Limitations of the Original B-Tree

B-Trees are one of the foundational data structures used by databases to speed up lookups. But like most things in computer science, they come with trade-offs — especially when it comes to memory usage and query efficiency at scale.

Let’s walk through some of the core limitations of B-Trees and why most production databases prefer their smarter sibling: the B+ Tree.

Internal Nodes Waste Space

In a classic B-Tree, every node stores both a key and a value — including internal nodes. While this sounds harmless at first, it becomes a problem as your dataset grows.

Here’s why: when searching for a specific value, the database only uses the value stored in the leaf node. The values stored in internal nodes are essentially placeholders that are never read during a normal lookup — and yet they still take up memory.

Get AkashSDas’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

This becomes expensive when your values are large (e.g., UUIDs or pointers to rows) because fewer keys can fit into a single page. Fewer keys per page lead to more pages overall, more page reads from disk, and ultimately, slower performance.

Poor Range Scan Performance

Another big drawback of B-Trees is how they handle range queries. If you’re asking the database something like: “Find all rows where ID is between 4 and 9.”

The B-Tree offers no optimized path for sequential access. Each key in that range may require a fresh traversal from the root down to a different leaf node. Even though those rows might be stored next to each other on disk, the structure of the B-Tree doesn’t help you get to them efficiently.

In other words, B-Trees are great for point lookups but struggle with range scans.

Data is Scattered and Unordered

Due to how B-Trees manage inserts — especially with random keys — data often ends up scattered across different parts of the tree. Each insert might cause a page split, and newly inserted rows might live in completely different branches of the tree. That randomness increases the number of I/O operations needed to read what might otherwise be a logically sequential set of rows.

And as you likely know, more I/O = slower performance.

A Quick Example

Here’s a visual that illustrates the core problem. Let’s say you want to retrieve all records where ID is between 4 and 9.

To fetch all six rows, you’d need to bounce between multiple branches, sometimes even going back to the root. This is unnecessary overhead that slows down your query, especially compared to a structure where the relevant nodes are already linked.

These shortcomings led to the evolution of the B+ Tree, which solves both the memory efficiency and range query issues by:

• Storing values only in leaf nodes
• Keeping internal nodes slim, with just keys
• Adding linked leaf nodes so range scans can traverse like a linked list

The B+ Tree sacrifices a little on write performance (due to maintaining linked leaves), but dramatically improves read performance, especially for range queries — which is what most databases optimize for.

B+ Tree

The B+ Tree is a refinement over the classic B-Tree structure, designed specifically to address the limitations we saw earlier — namely space inefficiency and poor range scan performance. While both structures serve the same goal — efficient search — the B+ Tree leans into range-based access patterns and I/O optimization.

At first glance, B+ Trees resemble B-Trees, but with a few key modifications:

• Only keys are stored in the root and internal nodes. Values (or pointers to full rows) are pushed exclusively to the leaf nodes.
• As a result, internal nodes are significantly smaller and can hold more keys per page — this makes each I/O more efficient.
• The leaf nodes are linked together like a linked list, which means once you locate a key, you can effortlessly traverse to its neighbors — perfect for range queries.

This seemingly simple change unlocks powerful performance gains. Because internal nodes no longer store data pointers, you can cram in more keys per page. So now, one page read (one I/O) delivers more value, literally.

Here’s a sample B+ Tree with degree 3, storing IDs from 1–11:

Each leaf node stores actual key-value pairs (e.g., 4:704, where 4 is the key and 704 is the tuple ID). Leaf nodes are linked from left to right → enabling fast, in-order traversal.

Range Query Example: ID Between 4–9

Let’s say we want all rows with IDs between 4 and 9.

• Traverse: Root → 5 → left child → 3 → right child → 4
• Land in leaf node holding key 4
• From there, sequential scan across linked leaves: 5, 6, 7, 8, 9
• No need to bounce back to the root or traverse branches again.

In an ideal scenario (where the data pointers are compact — say, integers), this could be a single disk page read for all five records. If the pointers are GUIDs or large strings, fewer entries may fit per page, but performance still beats B-Tree due to the contiguous scan.

Tradeoff: Duplication in Leaf Nodes

Since only leaf nodes store values, some key duplication happens — internal keys may also appear in leaves. But this duplication is a minor tradeoff for what you gain:

• Slimmer internal nodes
• More keys per page
• Faster traversal
• Optimized range scans

Proven in practice, B+ Trees are the default indexing structure in most relational databases (like MySQL’s InnoDB), search engines, and storage engines.

B+ Trees in the Real World

While the theory behind B+ Trees is elegant, real-world database systems make important design choices to adapt them for performance, memory efficiency, and query behavior. Let’s explore how modern DBMSs implement B+ Trees and what tradeoffs they consider along the way.

Leaf Pointers: To Link or Not to Link?

A defining feature of B+ Trees is that leaf nodes are linked — each one holds a pointer to its right neighbor. This makes range queries lightning-fast since you can walk through records sequentially without jumping back to internal nodes.

• MySQL InnoDB, PostgreSQL, and SQL Server all implement this linked-leaf strategy. It’s cheap in terms of storage, and the performance payoff during range scans is significant.
• On the other hand, MongoDB’s WiredTiger storage engine (which also uses B+ Trees) omits these leaf-to-leaf pointers. Why? It’s a deliberate optimization — since Mongo isn’t built for traditional range queries like SQL databases, it trims anything not strictly necessary. This keeps the structure leaner for its use case.

Nodes = Pages: Page-Optimized Design

Most DBMSs ensure that each B+ Tree node fits exactly into a database page (e.g., 8KB). That’s not just a coincidence (it’s crucial for minimizing I/O):

When a node is fetched, you get the whole page. Since internal nodes only store keys (not values), they pack in a lot more info per page. As a result, you can often fit the entire upper half of the tree (root + internal nodes) into memory, making traversal blazingly fast.

Leaf Nodes Live in the Heap

Unlike internal nodes, leaf nodes contain actual values (i.e., row pointers or row data). Keeping all of them in memory would be prohibitively expensive, especially at scale. So, most DBMSs store leaf nodes on disk (in the heap or data files). You can cache frequently accessed leaves, but it’s a cost-benefit decision tied to workload and memory availability.

This layout allows the best of both worlds:

• Fast, memory-resident traversal for locating where a key might be
• Disk-backed storage for values to handle scale

Nearly every modern DBMS uses B+ Trees as the backbone of their indexing layer — from MySQL to PostgreSQL to Oracle.

B+ Tree Storage Costs: MySQL vs Postgres

While B+ Trees are universally loved for their performance, the way databases implement them — especially around secondary indexes — can lead to very different storage characteristics.

The key design difference lies in what secondary index entries actually store as their “value”:

• PostgreSQL: A secondary index points directly to the physical tuple in the heap (via tuple ID). The benefit of this is that it’s compact, but its drawback is that you often pay a second I/O to get the full row, especially if it’s not in memory.
• MySQL (InnoDB): A secondary index points to the value of the primary key. Since InnoDB is built on a clustered index model, the primary key is the row’s physical location. The benefit of this is that only one index has to deal with physical storage location. If the primary key is large (e.g., UUID, GUID, string), every secondary index stores that large PK. Multiply that by millions of rows, and your index bloat explodes.

This is one of the major reasons large-scale companies like Uber famously migrated from Postgres to MySQL.

Amplification in Action: Why UUIDs Are Painful in MySQL

In InnoDB, every secondary index entry includes the full primary key — because that’s how it locates the actual row. So, imagine your primary key is a UUID stored as a string (36 bytes). Now, imagine 5 secondary indexes. Now multiply that by 100 million rows. Your index storage balloons fast.

In contrast, Postgres indexes point to the tuple directly. Tuple pointers are small and fixed in size (like (page#, row#)), making the secondary indexes more compact and memory-efficient—no matter how bulky your primary key is.

Clustered Indexes in MySQL

Another nuance: In MySQL’s InnoDB engine, the leaf nodes of the primary B+ Tree contain the full row. That’s because it’s an Index-Organized Table (IOT) — also called a clustered index.

This has big implications as it’s faster for primary key lookups (the data is right there in the index), but now inserts with random primary keys (like UUIDs) cause fragmentation, page splits, and overall write inefficiency.

So, while this layout helps for certain reads, it’s a poor fit if:

• Your PKs aren’t sequential.
• You have lots of secondary indexes.
• You care about write throughput and compact storage.

For write-heavy workloads or PKs with large sizes, Postgres has a clear edge in how it manages storage. But if you’re optimizing for fast primary key lookups with few secondary indexes, InnoDB’s model works well.