Index Terminology: Essential Concepts and Metrics

In the realm of database indexing, few concepts are as fundamental yet underappreciated as fanout. Also known as the branching factor, fanout is the single most influential parameter determining how quickly a tree-based index can locate any record in a database of millions—or billions—of rows.

Consider this: a B+-tree with a fanout of 100 can search through 100 million records by examining just 4 nodes. The same data in a binary tree (fanout of 2) would require approximately 27 node accesses. This isn't a minor optimization—it's a fundamental architectural difference that separates enterprise-grade database performance from academic toy implementations.

Understanding fanout transforms how you think about index design, capacity planning, and performance troubleshooting. It's the vocabulary principal engineers use when discussing index optimization at scale.

Fanout (also called the branching factor or order) refers to the maximum number of child pointers that a single node in a tree-based index can hold. In database terminology, it represents how many branches emerge from each internal node of the index structure.

Formally, for a B+-tree:

Fanout (F) = Maximum number of child pointers per internal node

This directly corresponds to the number of keys a node can store. An internal node with n keys has n + 1 child pointers (since each key separates two ranges of values). However, in common usage, 'fanout' often refers simply to the number of entries or pointers per node.

Why 'fanout' as a term?

The term visualizes how the tree 'fans out' from root to leaves. Starting from a single root node, each level multiplies the number of nodes by a factor equal to the fanout. A root with fanout 100 leads to up to 100 nodes at level 1, 10,000 at level 2, and 1,000,000 at level 3.

Fanout isn't an arbitrary choice—it's determined by the physical relationship between page size, key size, and pointer size. Understanding this calculation is essential for predicting index performance and making configuration decisions.

The Fundamental Equation:

For a B+-tree internal node:

Fanout (F) = ⌊(Page Size - Header Size) / (Key Size + Pointer Size)⌋

Let's break down each component:

Real-World Fanout Values:

Database vendors optimize heavily for fanout. Here are typical values:

Key insight: Larger page sizes directly increase fanout. MySQL's 16KB default pages give it roughly double the fanout of PostgreSQL's 8KB pages, meaning InnoDB B+-trees are typically one level shallower for equivalent data sets.

Fanout's importance stems from a fundamental property of tree structures: the number of nodes grows exponentially with depth, while search cost grows linearly with depth.

This relationship is captured by the tree height formula:

Height (h) = ⌈log_F(N)⌉

Where:

• F = Fanout (branching factor)
• N = Number of leaf entries (records)
• h = Tree height (levels traversed from root to leaf)

Each increase in fanout logarithmically reduces the tree height, which directly translates to fewer disk I/O operations per query.

The I/O Connection:

In database systems, each level of the index typically requires one disk I/O operation (unless cached in the buffer pool). Therefore:

I/O operations per lookup ≈ Tree Height = log_F(N)

Since disk I/O is 5-6 orders of magnitude slower than memory access, minimizing tree height is the primary optimization goal for disk-based indexes. Fanout is the lever that achieves this.

Concrete Example:

For a table with 100 million rows:

• Fanout 100: Height = ⌈log₁₀₀(100,000,000)⌉ = ⌈4⌉ = 4 levels
• Fanout 500: Height = ⌈log₅₀₀(100,000,000)⌉ = ⌈3.0⌉ = 3 levels

That one-level difference means 25% fewer disk reads per query, which at high query volumes translates to significant performance and cost savings.

One of the most important yet often overlooked relationships in index design is the inverse relationship between key size and fanout. As keys grow larger, fewer fit in each node, reducing fanout and increasing tree height.

This has profound implications for index key selection and composite index design.

Composite Key Fanout:

When creating composite indexes (indexes on multiple columns), the combined key size further reduces fanout:

Composite Key Size = Key₁ Size + Key₂ Size + ... + Keyₙ Size
Fanout = ⌊(Page Size - Header) / (Composite Key Size + Pointer Size)⌋

Example: An index on (last_name VARCHAR(50), first_name VARCHAR(50), birth_date DATE) might have an average composite key size of 30 + 25 + 4 = 59 bytes, yielding fanout of approximately 130 with 8KB pages.

Best Practices for Maximizing Fanout:

Modern database systems implement sophisticated optimizations to maximize effective fanout. Understanding these techniques reveals why production databases achieve better performance than theoretical calculations suggest.

Maximum fanout isn't always optimal fanout. Database systems use fill factor to intentionally leave space in index nodes, trading fanout for other benefits.

Fill Factor specifies what percentage of each index page should be filled during initial creation or rebuild. A 90% fill factor means 10% of each page is left empty.

Effective Fanout Calculation with Fill Factor:

Effective Fanout = Maximum Fanout × Fill Factor

For an index with maximum fanout of 500 and fill factor of 70%:

• Effective Fanout = 500 × 0.70 = 350

This lower effective fanout increases height for large tables but prevents costly page splits during write operations.

When to Adjust Fill Factor:

While the term 'fanout' originates from B-tree family structures, the concept extends to other index types with different interpretations and implications.

B+-Tree vs B-Tree Fanout:

B+-trees achieve higher fanout than classic B-trees because:

1. Internal nodes contain only keys and pointers — No data payloads consuming space
2. All data resides in leaf nodes — Internal nodes are pure navigation structures
3. Smaller internal nodes = more per page — Better cache utilization

This is why B+-trees dominate database indexing despite B-trees being conceptually simpler.

Hash Index 'Fanout':

Hash indexes don't have traditional fanout (there's no tree), but bucket count serves a similar role:

• More buckets → fewer collisions → faster lookups
• Extendible hashing adjusts 'fanout' dynamically via directory doubling
• Linear hashing grows continuously, maintaining target utilization

Fanout is arguably the single most important metric for understanding B+-tree index performance. Let's consolidate the critical insights:

What's Next:

With fanout understood, we'll explore height — the tree depth that fanout determines. You'll learn how to calculate expected heights for production indexes, understand the significance of the 'root-to-leaf path,' and see why most production B+-trees are just 3-4 levels deep regardless of table size.