B‑Tree Indexing in Databases

By Apiary Staff

Databases are the buzzing heart of every modern information system. Whether you’re tracking the migration of honeybees across continents, powering an autonomous AI‑agent that decides where to plant wildflowers, or serving millions of e‑commerce transactions per second, the ability to locate a single record among billions of rows in a flash is what makes the difference between a thriving service and a stalled one.

At the core of that capability lies a deceptively simple data structure: the B‑tree. First described in the 1970s, the B‑tree has survived three generations of hardware revolutions, from magnetic drums to solid‑state drives, because it aligns itself perfectly with the way computers store and retrieve data on disk. Its design principles—node degree, disk‑page alignment, and range‑query efficiency—are not just academic curiosities; they are the levers you pull when you tune a database for speed, predictability, and resilience.

In this pillar article we will unpack the B‑tree from the ground up, walk through the mathematics that dictate its shape, explore how it interacts with modern storage media, and see concrete examples of how it powers everything from relational DBMSs to the AI agents that help protect pollinator habitats. You’ll finish with a clear mental model that lets you diagnose performance problems, choose the right index type, and explain the trade‑offs to non‑technical stakeholders—be they beekeepers, policy makers, or fellow engineers.

1. What Is a B‑Tree?

A B‑tree (short for balanced tree) is a self‑balancing search tree where each node can hold multiple keys and multiple child pointers. Unlike binary trees, which split data into left/right branches, a B‑tree’s branching factor (or node degree) can be dozens or hundreds, dramatically reducing the number of disk reads required to locate a key.

1.1 Formal definition

A B‑tree of order m satisfies the following constraints for every node N:

The height h of a B‑tree grows logarithmically with the number of stored keys n:

\[ h \le \lceil \log_{⌈m/2⌉} (n+1) \rceil \]

Because each level can branch by at least ⌈m/2⌉, the height stays tiny even for massive tables. For example, with m = 128 (a common value on an 8 KB page) a tree holding 1 billion rows has a height of only 3.

1.2 Why “B”?

The “B” does not stand for binary (that would be a misnomer) nor for balanced (many balanced trees exist). It is simply the first letter of the surname of the two inventors, R. Bayer and E. McCreight, who introduced the structure in 1972. Over the decades the name has stuck, and variations like B+‑tree and **B‑tree* have become standard vocabulary in the DBMS world.

2. Node Degree and the Branching Factor

The node degree—often called the branching factor—determines how many keys a node can hold. It is directly tied to the disk page size (or block size) and the size of each key + pointer.

2.1 Calculating the optimal degree

Assume a typical SSD block (or HDD sector) of 8 KB (8192 bytes). Suppose each index entry stores:

• Key – 8 bytes (e.g., a 64‑bit integer primary key)
• Pointer – 8 bytes (a 64‑bit page address)

A leaf node stores key–pointer pairs, while an internal node stores key values plus child pointers. For a leaf node, the record size is 16 bytes; for an internal node it is 8 bytes (key) + 8 bytes (pointer) = 16 bytes as well.

Maximum entries per page:

\[ \text{max\_entries} = \left\lfloor \frac{8192}{16} \right\rfloor = 512 \]

Thus the order m = 513 (because a node can have up to m‑1 keys). In practice, DBMSs reserve a small header (≈ 24 bytes) and a footer for free‑space tracking, so the usable degree drops to about 500.

2.2 Impact on search depth

With a degree of 500, the tree height for 10 million rows is:

\[ h \le \lceil \log_{250} (10\,000\,000+1) \rceil \approx \lceil 2.84 \rceil = 3 \]

Only three page reads (root → internal → leaf) are needed, each typically costing a few microseconds on an SSD. Contrast that with a binary search tree that would need ~ 24 comparisons (log₂ 10 M) and many more cache misses.

2.3 Real‑world tuning

Some DBMSs let you adjust the fill factor—the percentage of a page that must be occupied after a bulk load. A fill factor of 80 % reduces the effective degree to 400, which increases tree height by at most one level but leaves room for future insertions without immediate page splits. This trade‑off is crucial for write‑heavy workloads where page splits can cause latch contention.

3. Disk‑Page Alignment and I/O Efficiency

Modern storage devices read and write data in pages (also called blocks). Aligning a B‑tree node to a page eliminates the need for the DBMS to perform multiple I/O operations to assemble a logical node.

3.1 Page‑oriented design

When a B‑tree node fits exactly into a page, the DBMS can fetch the whole node with a single read‑ahead request. This is why the node degree is often chosen to match the page size.

• Sequential scans: If the DBMS prefetches the next page while processing the current one, the latency of a three‑level tree becomes indistinguishable from a single read for many workloads.
• Write‑behind caching: Updates to leaf pages are buffered in memory and flushed together, reducing write amplification.

3.2 SSD vs. HDD characteristics

On an HDD, each page read incurs a costly seek. The B‑tree’s high branching factor minimizes the number of seeks. On an SSD, the latency is already low, but the B‑tree still helps because SSDs have write‑amplification; fewer page splits mean fewer program/erase cycles, extending device lifespan—a subtle but real environmental benefit that aligns with Apiary’s sustainability ethos.

3.3 Example: query latency on a 1 TB table

Consider a table of 500 million rows, each row 200 bytes, stored on a 1 TB SSD. Using a B‑tree index with degree 500:

• Height = 3 levels (root, internal, leaf)
• I/O per lookup = 3 page reads ≈ 0.6 ms (SSD latency)
• Total latency (including CPU work) ≈ 1 ms

If the same data were accessed via a hash index that required a full‑page scan due to collisions, the latency could rise to 5–10 ms. The B‑tree wins both on speed and on predictable latency, which is essential for real‑time AI agents that need deterministic response times.

4. Insertion, Deletion, and Tree Balancing

A B‑tree remains balanced automatically, but the mechanics of splits, merges, and redistributions affect performance and concurrency.

4.1 Insertion algorithm

1. Search for the leaf where the new key belongs (O(logₘ n) page reads).
2. Insert the key into the leaf’s sorted array.
3. If the leaf overflows (exceeds m‑1 keys), split it:

• Create a new leaf node.
• Move the upper half of keys to the new node.
• Promote the middle key to the parent.

1. If the parent overflows, the split propagates upward, possibly creating a new root (increasing tree height by 1).

Because each split touches only one or two pages, the cost is bounded. The worst‑case scenario—splitting all the way to the root—occurs only when the tree is completely full, a situation avoided by setting a fill factor < 100 %.

4.2 Deletion algorithm

Deletion mirrors insertion:

• Locate the key in a leaf.
• Remove it.
• If the leaf falls below the minimum occupancy (⌈m/2⌉ − 1 keys), attempt to borrow a key from a sibling. If borrowing isn’t possible, merge the leaf with a sibling and delete the separator key from the parent.

Again, merges propagate upward only when necessary, and the tree height never shrinks below the logarithmic bound.

4.3 Concurrency control

Most DBMSs use latch coupling (also called crabbing) to protect pages while traversing the tree. For high‑throughput workloads, optimistic concurrency control (OCC) can be layered on top, allowing readers to proceed without blocking writers as long as the version numbers of traversed pages stay unchanged.

A practical tip: avoid long‑running transactions that hold exclusive latches on root pages, because that can become a bottleneck for all concurrent inserts. Instead, batch inserts in small transactions and let the DBMS perform background index maintenance.

5. Range Queries – The B‑Tree’s Natural Strength

One of the B‑tree’s most celebrated properties is its ability to return ordered ranges with minimal effort. This is why B‑trees dominate primary key and ordered secondary key indexing.

5.1 Traversal for a range

To fetch rows where key BETWEEN a AND b:

1. Search for the leaf containing a.
2. Scan forward leaf pages, following the right sibling pointers (a linked list of leaves).
3. Stop when a key exceeds b.

Because leaf nodes are stored contiguously on disk (often in the same file region), the scan can be satisfied with sequential reads, which are dramatically faster than random reads.

5.2 Example: time‑series data for pollinator counts

Assume a table BeeCounts(date DATE, hive_id INT, count INT) with a composite B‑tree index on (date, hive_id). A query to retrieve all counts for January 2025 translates to a range on the date column. The DBMS will locate the first leaf for 2025‑01‑01, then read successive leaf pages until 2025‑01‑31.

On a 4 TB SSD, such a scan over 10 million rows (≈ 160 MB of index pages) typically completes in ≈ 30 ms, far faster than a full table scan (≈ 150 ms).

5.3 Comparison to other index types

• Hash indexes excel at point lookups but cannot serve ordered ranges without a full scan.
• GiST / GIN indexes support spatial and full‑text queries but have higher per‑lookup overhead.
• Columnar stores can also serve range queries efficiently, but they require a different data layout and often sacrifice write performance.

Thus, for workloads that involve time‑ordered analytics, geospatial bounding boxes, or lexicographic sorting, the B‑tree remains the default choice.

6. B+‑Tree and B*‑Tree Variants

While the classic B‑tree already offers impressive performance, most production DBMSs implement a B+‑tree or a **B‑tree*. Understanding the differences helps you decide which flavour a particular engine uses and why.

6.1 B+‑tree

In a B+‑tree, all data records reside in leaf nodes, while internal nodes contain only keys that act as separators.

• Pros:
• Uniform leaf size → easier to predict I/O.
• Simple forward/backward leaf links → efficient range scans.
• Cons:
• Slightly deeper tree (since internal nodes hold fewer keys).

All major relational engines—PostgreSQL, MySQL InnoDB, SQL Server, Oracle—use B+‑trees for primary and secondary indexes.

6.2 B*‑tree

A B‑tree improves space utilization by enforcing a minimum fill factor of 2/3 (instead of 1/2). When a node overflows, instead of splitting immediately, the B‑tree tries to redistribute keys among its siblings before creating a new node.

• Pros:
• Fewer splits → less write amplification.
• Higher average fanout → slightly lower height.
• Cons:
• More complex insertion logic.

IBM DB2 and some older versions of Oracle employ B*‑trees in specific contexts (e.g., index-organized tables).

6.3 Choosing a variant

If your workload is read‑heavy with frequent range scans, a B+‑tree is ideal. If you have a write‑intensive workload on SSDs and are concerned about wear, the B*‑tree’s reduced split frequency can extend device life—an indirect benefit for sustainability.

7. Performance Tuning – From Theory to Practice

A well‑designed B‑tree index can make or break an application. Below are concrete knobs you can turn, with measurable impact.

7.1 Fill factor

• Default: 90 % (SQL Server), 100 % (PostgreSQL).
• Recommendation: For bulk‑load tables that will not change much, set to 100 %. For tables with continuous inserts, set to 70–80 % to reduce page splits.

Result: In a benchmark on a 500 M‑row table, reducing fill factor from 100 % to 80 % cut insert‑time from 12 ms/row to 7 ms/row (≈ 40 % improvement).

7.2 Index column order

The order of columns in a composite index matters for range queries. For (date, hive_id), placing date first enables date range scans without touching the hive_id column. Reversing the order would force the engine to scan the entire index for each date.

7.3 Covering indexes

If a query can be satisfied entirely from the index (i.e., the index contains all needed columns), the DBMS can avoid touching the base table. This is known as a covering index.

Example:

SELECT count FROM BeeCounts WHERE date = '2025-01-15' AND hive_id = 42;

A B+‑tree on (date, hive_id, count) lets the engine read only the leaf pages, shaving off up to 30 % of I/O for large tables.

7.4 Partitioning and local indexes

Splitting a massive table into partitions (e.g., by year) creates smaller B‑tree indexes per partition. Queries that target a single partition only need to traverse a local index, reducing both read traffic and lock contention.

8. Real‑World Implementations

8.1 MySQL InnoDB

• Node size: 16 KB (default).
• Branching factor: ~ 800 for 8‑byte keys.
• Leaf format: B+‑tree with clustered primary key (data stored in leaf).

InnoDB also maintains a secondary B+‑tree for each non‑unique index, where leaf entries contain the primary key as a pointer, enabling covering scans.

8.2 PostgreSQL

• Page size: 8 KB (configurable).
• Index type: B‑tree (B+‑tree variant).
• Fill factor: 100 % by default; can be set per index (ALTER INDEX … SET (fillfactor = 70)).

PostgreSQL’s B‑tree implementation supports predicate indexes (WHERE …) and partial indexes, which are powerful for reducing index size when only a subset of rows matters (e.g., only active hives).

8.3 Microsoft SQL Server

• Page size: 8 KB.
• Index structure: B+‑tree with non‑clustered and clustered variations.
• Fill factor: 0–100 % (default 0 % = 100 %).

SQL Server adds row‑compression and page‑compression options that shrink leaf pages, effectively increasing the effective degree without changing the physical page size.

9. From Bees to AI Agents – Why B‑Trees Matter

9.1 The hive analogy

A bee colony is a distributed, self‑organizing system where each worker follows simple rules yet the whole hive achieves complex tasks (foraging, thermoregulation, defense). The B‑tree’s branching factor mirrors how a queen bee can lay thousands of eggs, creating many “branches” of the colony. Just as a hive maintains balanced workload among its workers, a B‑tree keeps its branches evenly filled, guaranteeing that no single leaf becomes a hot spot.

9.2 AI agents that plan with indexes

Consider an autonomous agent that decides where to plant wildflowers to support pollinator routes. The agent stores a spatial index of land parcels, each keyed by latitude and longitude. When a new observation arrives (e.g., a sudden decline of a bee species in a region), the agent performs a range query to locate all parcels within a 20‑km radius. The B+‑tree’s leaf links let the agent retrieve the relevant parcels in a single sequential scan, enabling near‑real‑time decision making.

If the underlying index were a hash map, the agent would have to scan the entire dataset or maintain additional structures, incurring latency that could cause missed planting windows.

9.3 Sustainable storage

Every extra page split on an SSD triggers an erase‑program cycle, consuming energy and shortening device life. By selecting a high fill factor and using a **B‑tree where appropriate, you reduce the number of writes, aligning database engineering with Apiary’s mission to minimize environmental impact*.

10. Future Directions – Beyond Classic B‑Trees

While B‑trees remain dominant for OLTP workloads, new storage architectures and workloads are prompting hybrid approaches.

Even as these alternatives mature, the core concepts—node degree, page alignment, and range traversal—remain relevant. Many systems (e.g., Apache Cassandra) combine an LSM core with a B‑tree‑like bloom filter to speed up point lookups. Understanding the classic B‑tree therefore gives you a solid foundation for evaluating any new index technology.

Why It Matters

A B‑tree is more than a textbook data structure; it is the engine room that powers reliable, fast, and predictable data access across virtually every relational database. For Apiary’s community, that translates into:

• Timely insights for beekeepers and conservationists who need to query massive observation datasets without waiting minutes for results.
• Efficient AI agents that can react to environmental changes in seconds, not hours, because their underlying indexes return the right data range instantly.
• Sustainable operations—fewer page splits and lower write amplification mean longer SSD lifespans and reduced energy consumption, aligning tech with ecological stewardship.

By mastering the mechanics of node degree, disk‑page alignment, and range‑query efficiency, you gain the tools to design databases that are fast, durable, and kind to the planet—just like a well‑organized bee colony.

References

• Bayer, R., & McCreight, E. (1972). Organization and maintenance of large ordered indexes. ACM Transactions on Database Systems.
• “InnoDB Architecture.” MySQL Documentation. https://dev.mysql.com/doc/refman/8.0/en/innodb-architecture.html
• “PostgreSQL B‑Tree Indexes.” PostgreSQL Documentation. https://www.postgresql.org/docs/current/indexes-btree.html
• “SQL Server Index Design Guide.” Microsoft Docs. https://learn.microsoft.com/en-us/sql/relational-databases/sql-server-index-design-guide

For further reading, see our related pages: bplus-tree, disk-io, range-queries, ai-agent-architecture, database-indexing.