Height Analysis

Understanding B-tree height is not merely academic—it's directly predictive of performance. Since each level of the tree typically requires one disk I/O, knowing the height tells you exactly how many disk accesses a search requires. This enables capacity planning, query optimization, and system design decisions.

In this final page of the B-tree Concept module, we derive precise height formulas, analyze how parameters affect height, and connect theory to practice for database sizing and performance estimation.

The minimum possible height of a B-tree occurs when all nodes are maximally full. This gives us the lower bound—the best case for a given number of keys.

Theorem: For a B-tree of order m with n keys, the minimum height is:

$$h_{min} = \lceil \log_m (n+1) \rceil - 1$$

Derivation:

With all nodes at maximum capacity:

• Each internal node has m children
• Each internal node has m-1 keys
• Each leaf has m-1 keys

The maximum number of keys a B-tree of height h can hold:

The maximum possible height occurs when all nodes are minimally occupied (at the threshold of underflow). This is the worst case we must plan for.

Theorem: For a B-tree of order m with n keys, the maximum height is:

$$h_{max} = \lfloor \log_{\lceil m/2 \rceil} \left( \frac{n+1}{2} \right) \rfloor$$

Derivation:

With all nodes at minimum capacity:

• Root has at least 2 children (1 key)
• Other internal nodes have at least ⌈m/2⌉ children (⌈m/2⌉ - 1 keys)
• Leaves have at least ⌈m/2⌉ - 1 keys

Let t = ⌈m/2⌉ (the minimum degree).

In practice, B-trees are neither maximally nor minimally full. The average case depends on the fill factor—the fraction of node capacity actually used.

Fill Factor Definition

Fill factor α = (actual keys in node) / (maximum keys per node)

• α = 1.0: maximally full (100% utilization)
• α = 0.5: minimally full (50% utilization)
• α ≈ 0.69: average for random insertions (ln(2))

Why ln(2) ≈ 0.69?

For random insertions into a B-tree:

• After a split, each half starts at 50% capacity
• Random insertions fill nodes until they split at 100%
• Average occupancy is the midpoint: (50% + 100%) / 2 = 75%?

Actually, the correct analysis shows that the expected fill factor converges to ln(2) ≈ 0.693 due to the distribution of split points.

Height With Average Fill Factor

With fill factor α, effective fanout is approximately α × m:

$$h_{avg} \approx \log_{\alpha \cdot m}(n)$$

Impact of Fill Factor

Fill factor affects:

1. Height: Lower fill = taller tree = more I/Os
2. Space: Lower fill = more nodes = more disk space
3. Write performance: Higher fill = more frequent splits

There's a trade-off: very high fill factors mean almost every insertion causes a split, while very low fill factors waste space and increase height.

Fanout (the number of children per node) is the key parameter determining B-tree height. Let's analyze this relationship precisely.

The Logarithmic Relationship

Height h ≈ log_f(n) where f is the average fanout.

Doubling fanout: h → h × (log_f(n) / log_2f(n)) = h × (log_f(n) / (1 + log_f(n) / log_f(2)))

Simplified: doubling fanout reduces height by approximately 1 / log_f(2).

For f = 100: doubling to 200 reduces height by ~15% For f = 10: doubling to 20 reduces height by ~30%

Diminishing Returns

The benefit of increasing fanout is logarithmic, meaning:

• Going from fanout 2 to 10: huge improvement (30 → 10 levels)
• Going from fanout 100 to 200: modest improvement (5 → 4 levels)
• Going from fanout 500 to 1000: minimal improvement (4 → 3 levels)

Optimal Fanout Considerations

Why not maximize fanout by using huge pages?

1. Page size limits: Operating systems have natural page sizes (4KB, 8KB)
2. Cache efficiency: Larger nodes hurt CPU cache performance
3. Write amplification: Modifying a 64KB page costs more than 4KB
4. Lock granularity: Larger nodes mean coarser locking

For most systems, fanout of 100-500 (8KB-16KB pages) hits the sweet spot.

The primary motivation for understanding height is predicting I/O cost. Let's make this connection explicit.

Search I/O Cost

For a point query (find one key):

• Traverse from root to leaf: h node accesses
• Each node access is 1 disk I/O (assuming cold cache)
• Total: h disk I/Os

With Caching

In practice, upper levels are cached:

• Root: always in memory (1 page, accessed constantly)
• Level 1: usually in memory (≤ m pages, frequently accessed)
• Level 2+: may or may not be cached

Effective I/O = h - (cached levels) ≈ h - 2 for active indexes

Range Query I/O Cost

For a range query returning k keys:

• Initial descent: h disk I/Os
• Leaf scan: k/(m-1) leaf pages
• Total: h + ⌈k/(m-1)⌉ disk I/Os

Latency Estimation

With disk characteristics, we can estimate query latency:

HDD: 10ms average seek + read time
SSD: 0.1ms average access time

Point Query on HDD (h=4, warm cache):
  2 disk accesses × 10ms = 20ms

Point Query on SSD (h=4, warm cache):
  2 disk accesses × 0.1ms = 0.2ms

Range Query for 1000 keys on HDD:
  13 sequential reads × 5ms (sequential faster) = 65ms

Range Query for 1000 keys on SSD:
  13 reads × 0.05ms = 0.65ms

This is why SSDs transformed database performance—reducing each I/O from milliseconds to microseconds makes B-tree height less critical (but still important for maximum throughput).

Height analysis enables precise capacity planning. Given expected data volume and performance requirements, we can calculate required fanout and resources.

Problem: Size an index for a table expected to grow to 500 million rows, with point query latency under 2ms on SSD.

Analysis:

Space Estimation

Height analysis also helps estimate index size:

Total nodes ≈ n / (fill_factor × (m-1)) × (1 + 1/m + 1/m² + ...)
           ≈ n / (0.69 × (m-1)) × m/(m-1)
           ≈ n / (0.69 × (m-1))

For n = 500M, m = 578:
  Nodes ≈ 500M / (0.69 × 577) ≈ 1.25M nodes
  Size ≈ 1.25M × 8KB ≈ 10GB index size

Actual size includes overhead, typically 8-12GB for this case.

This calculation helps plan storage allocation and buffer pool sizing.

B+-trees (covered in detail in subsequent modules) have slightly different height characteristics because data is stored only in leaves.

Key Difference

B+-tree Height Calculation

For B+-trees, we consider two fanouts:

• f_internal = fanout of internal nodes (keys + pointers)
• f_leaf = entries per leaf (keys + data pointers)

Height determination:

Number of leaves = ⌈n / f_leaf⌉
Internal tree height to cover that many leaves:
  h_internal = ⌈log_{f_internal}(number of leaves)⌉

Total height = h_internal + 1 (for leaf level)

Example Comparison