Range Queries — B+-Tree Operations | OneNoughtOne

0/131

Database Management SystemsB+-Tree Operations

B+-Tree Operations

LevelIntermediate

Duration90 mins

TopicB+-Tree Operations

2 / 5

Range Queries

The Killer Feature of B+-Trees

If point queries were the only requirement, hash indexes would dominate—their O(1) lookup is unbeatable. But real-world database workloads are filled with range queries : finding all orders from last quarter, retrieving employees with salaries between $50K and $100K, or scanning log entries from the past hour. This is where B+-trees shine. Their linked leaf structure transforms range queries from repeated tree traversals into a single descent followed by a sequential scan. This architectural decision—linking all leaf nodes in key order—is the defining feature that makes B+-trees the default index structure in virtually every relational database.

What You Will Learn

By the end of this page, you will master B+-tree range query execution. You'll understand how to find range boundaries, traverse linked leaves efficiently, handle open-ended ranges, calculate I/O costs, and recognize optimization opportunities for range-heavy workloads.

Types of Range Queries

Range queries come in several forms, each with slightly different execution characteristics: Closed Range (BETWEEN): SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-03-31' Both lower and upper bounds are specified and inclusive. Half-Open Ranges (Inequalities): SELECT * FROM products WHERE price >= 100 AND price < 500 One or both bounds may be exclusive. Open-Ended Ranges (One Bound): SELECT * FROM employees WHERE salary >= 80000 SELECT * FROM logs WHERE timestamp < '2024-01-15' Only one bound is specified; the range extends to the minimum or maximum key. Prefix Ranges (String Matching): SELECT * FROM customers WHERE name LIKE 'John%' String prefixes translate to range queries on collation-ordered indexes.

Range Query Classification and B+-tree Handling
Query Type	SQL Example	Start Bound	End Bound	Scan Direction
Closed range	BETWEEN a AND b	Search for a	Stop after b	Forward
Greater than	a or >= a	Search for a	Rightmost leaf	Forward
Less than	< b or <= b	Leftmost leaf	Stop after b	Forward
Prefix match	LIKE 'abc%'	Search for 'abc'	Stop at first non-match	Forward
Full scan	ORDER BY indexed_col	Leftmost leaf	Rightmost leaf	Forward or backward

LIKE Queries as Range Queries

The query LIKE 'John%' is equivalent to the range query name >= 'John' AND name < 'Joho' (where 'Joho' is the first string lexicographically greater than all strings starting with 'John'). The optimizer transforms prefix LIKE into range bounds automatically.

The Linked Leaf Architecture

The B+-tree's range query efficiency stems from its doubly-linked leaf chain . Let's examine this structure in detail. Leaf Node Linking: Every leaf node contains: Sorted keys with their record pointers A next pointer to the right sibling leaf (keys immediately larger) A previous pointer to the left sibling leaf (keys immediately smaller) — in most implementations This creates a linked list at the leaf level that maintains key ordering across the entire tree.

Converting Mermaid diagram...

Why Linking Matters: Without leaf linking, a range query would require: Search for the first key in range: O(log N) For each subsequent key, re-traverse the tree from root: O(log N) per key Total cost: O(k \times log N) where k is the number of matching keys With leaf linking: Search for the first key in range: O(log N) — one tree traversal Follow sibling pointers for subsequent keys: O(1) per key Total cost: O(log N + k) — dramatically better for large result sets For a query returning 10,000 matching records from a billion-row table: Without linking: ~30,000 tree traversals \times 5 levels = 150,000 I/Os With linking: 5 I/Os to find start + ~100 leaf reads = ~105 I/Os That's a 1,400\times improvement from a simple design decision.

Doubly-Linked vs Singly-Linked

Some B+-tree implementations use only forward (next) pointers to save space. This is sufficient for forward range scans but requires different strategies for backward scans (e.g., ORDER BY DESC). Production databases typically implement doubly-linked leaves to support both scan directions efficiently.

The Range Query Algorithm

The range query algorithm consists of three phases: boundary finding, sequential scanning, and termination. Let's examine each in detail.

B+-Tree Range Query Algorithm
Pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
FUNCTION BPlusTreeRangeQuery(root, lowKey, highKey, lowInclusive, highInclusive)
    // ====================================================
    // PHASE 1: FIND STARTING POSITION (Boundary Search)
    // ====================================================
    
    // Use standard search to find the leaf containing lowKey
    startLeaf ← BPlusTreeSearch(root, lowKey).leafNode
    
    // Find the position within the leaf to start scanning
    IF lowInclusive THEN
        startPos ← FindFirstGreaterOrEqual(startLeaf, lowKey)
    ELSE
        startPos ← FindFirstGreaterThan(startLeaf, lowKey)
    END IF
    
    // ====================================================
    // PHASE 2: SEQUENTIAL LEAF SCAN
    // ====================================================
    
    results ← []
    currentLeaf ← startLeaf
    currentPos ← startPos
    
    WHILE currentLeaf ≠ NULL DO
        WHILE currentPos < currentLeaf.keyCount DO
            currentKey ← currentLeaf.keys[currentPos]
            
            // Check if we've passed the upper bound
            IF highInclusive THEN
                IF currentKey > highKey THEN
                    RETURN results    // Done - past upper bound
                END IF
            ELSE
                IF currentKey >= highKey THEN
                    RETURN results    // Done - reached or passed upper bound
                END IF
            END IF
            
            // Key is in range - add to results
            results.append(currentLeaf.recordPointers[currentPos])
            currentPos ← currentPos + 1
        END WHILE
        
        // ====================================================
        // PHASE 3: MOVE TO NEXT LEAF (Sibling Traversal)
        // ====================================================
        currentLeaf ← currentLeaf.nextSibling
        currentPos ← 0
    END WHILE
    
    RETURN results    // Reached end of index
END FUNCTION
 
FUNCTION FindFirstGreaterOrEqual(leaf, key)
    // Binary search for first key >= target
    left ← 0
    right ← leaf.keyCount - 1
    result ← leaf.keyCount    // Default: past end
    
    WHILE left ≤ right DO
        mid ← (left + right) / 2
        IF leaf.keys[mid] >= key THEN
            result ← mid
            right ← mid - 1    // Look for earlier match
        ELSE
            left ← mid + 1
        END IF
    END WHILE
    
    RETURN result
END FUNCTION
 
FUNCTION FindFirstGreaterThan(leaf, key)
    // Binary search for first key > target
    left ← 0
    right ← leaf.keyCount - 1
    result ← leaf.keyCount    // Default: past end
    
    WHILE left ≤ right DO
        mid ← (left + right) / 2
        IF leaf.keys[mid] > key THEN
            result ← mid
            right ← mid - 1    // Look for earlier match
        ELSE
            left ← mid + 1
        END IF
    END WHILE
    
    RETURN result
END FUNCTION

Early Termination is Crucial

The algorithm checks the upper bound on every key. For a small range in a large table, most of the work is finding the start; once we exceed the upper bound, we stop immediately without scanning further leaves. This makes B+-tree range queries efficient regardless of total table size—cost depends primarily on result set size.

Worked Example: Complete Range Scan

Let's trace a complete range query through our example B+-tree: Query: Find all keys in the range [25, 48] (inclusive both bounds) Tree Structure (Leaf Level Only): [3,5,7] \leftrightarrow [10,12,15] \leftrightarrow [20,22,28] \leftrightarrow [30,35,38] \leftrightarrow [40,42,45] \leftrightarrow [50,55,58]

Phase 1: Find Starting Position Search for lowKey = 25: Tree descent finds Leaf 3 (keys [20, 22, 28]) Binary search for first key \geq 25 Position found: index 2 (key = 28) Phase 2: Sequential Scan

Step	Current Leaf	Current Key	Compare with 48	Action
1	Leaf 3	28	28 ≤ 48 ✓	Add 28 to results
2	↓ end of Leaf 3, move to sibling
3	Leaf 4	30	30 ≤ 48 ✓	Add 30 to results
4	Leaf 4	35	35 ≤ 48 ✓	Add 35 to results
5	Leaf 4	38	38 ≤ 48 ✓	Add 38 to results
6	↓ end of Leaf 4, move to sibling
7	Leaf 5	40	40 ≤ 48 ✓	Add 40 to results
8	Leaf 5	42	42 ≤ 48 ✓	Add 42 to results
9	Leaf 5	45	45 ≤ 48 ✓	Add 45 to results
10	↓ end of Leaf 5, move to sibling
11	Leaf 6	50	50 > 48 ✗	Stop - upper bound exceeded

Range Query [25, 48] Execution Summary
Metric	Value	Explanation
Tree height traversals	1	Single descent to find starting leaf
Leaf nodes read	4	Leaves 3, 4, 5, 6 (stopped mid-scan on 6)
Total I/Os	~5	Height traversal + leaf reads
Keys examined	10	28, 30, 35, 38, 40, 42, 45, 50 + binary search
Keys returned	7	[28, 30, 35, 38, 40, 42, 45]

I/O Efficiency

Despite the tree containing many more leaves, we only read the 4 leaves that contain keys in our range. The linked list structure ensures we never read irrelevant leaves—we start at the right position and stop exactly when the range ends.

Handling Open-Ended Ranges

Open-ended range queries require special handling because one bound is effectively infinite. Let's examine each case:

Query Pattern: WHERE column >= value Algorithm: Search for the lower bound value Scan forward until reaching the end of the leaf chain No upper bound check needed Example: WHERE salary >= 80000 Find leaf containing 80000 Scan rightward through all remaining leaves Return all keys until NULL sibling pointer I/O Cost: O(log N) + O(k/b) where k is result count and b is keys per leaf Optimization: For queries returning a large fraction of the table, the optimizer may prefer a full table scan to avoid following many sibling pointers.

Selectivity Matters

An open-ended range query like WHERE age > 5 on an employee table will likely match nearly all rows. At this point, using the index becomes counterproductive—the query would read the entire index AND then fetch each row via record pointers (random I/Os). The optimizer may choose a sequential table scan instead.

Complexity Analysis for Range Queries

Let's rigorously analyze the cost of range queries in terms of I/O operations and CPU time.

Notation: N = total number of indexed entries n = B+-tree order (max children per node) k = number of keys in the result set (selectivity \times N) b = number of keys per leaf page h = tree height = O(log_n N) I/O Cost Breakdown: Finding the starting leaf: h I/Os (one per level) Scanning k matching keys: ⌈k/b⌉ leaf pages Total I/O: h + ⌈k/b⌉ For typical parameters: h \approx 3-5 (modest even for billions of rows) b \approx 100-200 (depends on key size and page size) Example: Range query returning 10,000 keys from a billion-row table with 4KB pages and 100 keys/leaf: Finding start: 5 I/Os Scanning leaves: 10,000/100 = 100 leaf I/Os Total: 105 I/Os Time at 10ms/random I/O: 1.05 seconds (improved with sequential read-ahead)

Range Query I/O Cost Examples (100 keys per leaf, height = 4)
Result Set Size (k)	Leaf Pages Read	Total I/Os	Approx. Time @ 10ms/IO
10	1	5	50 ms
100	1	5	50 ms
1,000	10	14	140 ms
10,000	100	104	1 second
100,000	1,000	1,004	10 seconds
1,000,000	10,000	10,004	100 seconds (without read-ahead)

Sequential Read-Ahead Optimization

When the storage system detects sequential leaf access, it can prefetch upcoming pages. With SSDs or large read-ahead buffers, sequential leaf scanning achieves near-streaming throughput—far faster than the random I/O estimates above. A 100,000-row range scan might take 1 second rather than 10 seconds with effective read-ahead.

CPU Cost: Binary search at each internal node: O(log n) per level = O(h \times log n) total for descent Binary search within starting leaf: O(log b) Comparison for each scanned key: O(k) Total CPU: O(h \times log n + k) CPU cost is typically negligible compared to I/O cost. For in-memory databases (all data cached), CPU becomes the bottleneck, but it still scales linearly with result size—unavoidable for any approach.

Range Queries: B+-tree vs Alternatives

How do B+-tree range queries compare to other approaches?

Range Query Performance Comparison
Structure	Range Query Cost	Key Advantage	Key Limitation
B+-tree	O(log N + k)	Linked leaves enable sequential scan	One tree descent required
Hash Index	O(N) — full scan required	N/A for ranges	Cannot support range queries at all
Sorted Array	O(log N + k)	Cache-friendly scan	O(N) insert cost prohibitive
Skip List	O(log N + k)	Simpler implementation	Less cache-efficient than B+-tree
Full Table Scan	O(N)	No index maintenance cost	Must examine every row

B+-tree Range Advantages

•Logarithmic start cost — find first match in O(log N)
•Linear scan cost — O(k) for k matching keys
•No additional sorting — results come in sort order
•Early termination — stop as soon as upper bound exceeded
•Incremental results — can return rows as scanned

When B+-tree Range Query Loses

•Very low selectivity — returning 80%+ of table
•Unclustered access — index scan then N random fetches
•Multi-column ranges — only first column uses tree
•Highly concurrent OLTP — range locks may bottleneck
•Wide rows — may be better to scan table directly

The Unclustered Access Problem

When the index is not clustered (data rows not stored in index order), each index entry points to a potentially random location in the heap. A range scan returning 1,000 rows might require 1,000 random I/Os to fetch the actual data. This is often slower than a full table scan, leading optimizers to skip the index for large range queries on non-clustered indexes.

Database Management SystemsB+-Tree Operations

B+-Tree Operations

LevelIntermediate

Duration90 mins

TopicB+-Tree Operations

2 / 5

Range Queries

The Killer Feature of B+-Trees

If point queries were the only requirement, hash indexes would dominate—their O(1) lookup is unbeatable. But real-world database workloads are filled with range queries : finding all orders from last quarter, retrieving employees with salaries between $50K and $100K, or scanning log entries from the past hour. This is where B+-trees shine. Their linked leaf structure transforms range queries from repeated tree traversals into a single descent followed by a sequential scan. This architectural decision—linking all leaf nodes in key order—is the defining feature that makes B+-trees the default index structure in virtually every relational database.

What You Will Learn

By the end of this page, you will master B+-tree range query execution. You'll understand how to find range boundaries, traverse linked leaves efficiently, handle open-ended ranges, calculate I/O costs, and recognize optimization opportunities for range-heavy workloads.

Types of Range Queries

Range queries come in several forms, each with slightly different execution characteristics: Closed Range (BETWEEN): SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-03-31' Both lower and upper bounds are specified and inclusive. Half-Open Ranges (Inequalities): SELECT * FROM products WHERE price >= 100 AND price < 500 One or both bounds may be exclusive. Open-Ended Ranges (One Bound): SELECT * FROM employees WHERE salary >= 80000 SELECT * FROM logs WHERE timestamp < '2024-01-15' Only one bound is specified; the range extends to the minimum or maximum key. Prefix Ranges (String Matching): SELECT * FROM customers WHERE name LIKE 'John%' String prefixes translate to range queries on collation-ordered indexes.

Range Query Classification and B+-tree Handling
Query Type	SQL Example	Start Bound	End Bound	Scan Direction
Closed range	BETWEEN a AND b	Search for a	Stop after b	Forward
Greater than	a or >= a	Search for a	Rightmost leaf	Forward
Less than	< b or <= b	Leftmost leaf	Stop after b	Forward
Prefix match	LIKE 'abc%'	Search for 'abc'	Stop at first non-match	Forward
Full scan	ORDER BY indexed_col	Leftmost leaf	Rightmost leaf	Forward or backward

LIKE Queries as Range Queries

The query LIKE 'John%' is equivalent to the range query name >= 'John' AND name < 'Joho' (where 'Joho' is the first string lexicographically greater than all strings starting with 'John'). The optimizer transforms prefix LIKE into range bounds automatically.

The Linked Leaf Architecture

The B+-tree's range query efficiency stems from its doubly-linked leaf chain . Let's examine this structure in detail. Leaf Node Linking: Every leaf node contains: Sorted keys with their record pointers A next pointer to the right sibling leaf (keys immediately larger) A previous pointer to the left sibling leaf (keys immediately smaller) — in most implementations This creates a linked list at the leaf level that maintains key ordering across the entire tree.

Converting Mermaid diagram...

Why Linking Matters: Without leaf linking, a range query would require: Search for the first key in range: O(log N) For each subsequent key, re-traverse the tree from root: O(log N) per key Total cost: O(k \times log N) where k is the number of matching keys With leaf linking: Search for the first key in range: O(log N) — one tree traversal Follow sibling pointers for subsequent keys: O(1) per key Total cost: O(log N + k) — dramatically better for large result sets For a query returning 10,000 matching records from a billion-row table: Without linking: ~30,000 tree traversals \times 5 levels = 150,000 I/Os With linking: 5 I/Os to find start + ~100 leaf reads = ~105 I/Os That's a 1,400\times improvement from a simple design decision.

Doubly-Linked vs Singly-Linked

Some B+-tree implementations use only forward (next) pointers to save space. This is sufficient for forward range scans but requires different strategies for backward scans (e.g., ORDER BY DESC). Production databases typically implement doubly-linked leaves to support both scan directions efficiently.

The Range Query Algorithm

The range query algorithm consists of three phases: boundary finding, sequential scanning, and termination. Let's examine each in detail.

B+-Tree Range Query Algorithm
Pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
FUNCTION BPlusTreeRangeQuery(root, lowKey, highKey, lowInclusive, highInclusive)
    // ====================================================
    // PHASE 1: FIND STARTING POSITION (Boundary Search)
    // ====================================================
    
    // Use standard search to find the leaf containing lowKey
    startLeaf ← BPlusTreeSearch(root, lowKey).leafNode
    
    // Find the position within the leaf to start scanning
    IF lowInclusive THEN
        startPos ← FindFirstGreaterOrEqual(startLeaf, lowKey)
    ELSE
        startPos ← FindFirstGreaterThan(startLeaf, lowKey)
    END IF
    
    // ====================================================
    // PHASE 2: SEQUENTIAL LEAF SCAN
    // ====================================================
    
    results ← []
    currentLeaf ← startLeaf
    currentPos ← startPos
    
    WHILE currentLeaf ≠ NULL DO
        WHILE currentPos < currentLeaf.keyCount DO
            currentKey ← currentLeaf.keys[currentPos]
            
            // Check if we've passed the upper bound
            IF highInclusive THEN
                IF currentKey > highKey THEN
                    RETURN results    // Done - past upper bound
                END IF
            ELSE
                IF currentKey >= highKey THEN
                    RETURN results    // Done - reached or passed upper bound
                END IF
            END IF
            
            // Key is in range - add to results
            results.append(currentLeaf.recordPointers[currentPos])
            currentPos ← currentPos + 1
        END WHILE
        
        // ====================================================
        // PHASE 3: MOVE TO NEXT LEAF (Sibling Traversal)
        // ====================================================
        currentLeaf ← currentLeaf.nextSibling
        currentPos ← 0
    END WHILE
    
    RETURN results    // Reached end of index
END FUNCTION
 
FUNCTION FindFirstGreaterOrEqual(leaf, key)
    // Binary search for first key >= target
    left ← 0
    right ← leaf.keyCount - 1
    result ← leaf.keyCount    // Default: past end
    
    WHILE left ≤ right DO
        mid ← (left + right) / 2
        IF leaf.keys[mid] >= key THEN
            result ← mid
            right ← mid - 1    // Look for earlier match
        ELSE
            left ← mid + 1
        END IF
    END WHILE
    
    RETURN result
END FUNCTION
 
FUNCTION FindFirstGreaterThan(leaf, key)
    // Binary search for first key > target
    left ← 0
    right ← leaf.keyCount - 1
    result ← leaf.keyCount    // Default: past end
    
    WHILE left ≤ right DO
        mid ← (left + right) / 2
        IF leaf.keys[mid] > key THEN
            result ← mid
            right ← mid - 1    // Look for earlier match
        ELSE
            left ← mid + 1
        END IF
    END WHILE
    
    RETURN result
END FUNCTION

Early Termination is Crucial

The algorithm checks the upper bound on every key. For a small range in a large table, most of the work is finding the start; once we exceed the upper bound, we stop immediately without scanning further leaves. This makes B+-tree range queries efficient regardless of total table size—cost depends primarily on result set size.

Worked Example: Complete Range Scan

Let's trace a complete range query through our example B+-tree: Query: Find all keys in the range [25, 48] (inclusive both bounds) Tree Structure (Leaf Level Only): [3,5,7] \leftrightarrow [10,12,15] \leftrightarrow [20,22,28] \leftrightarrow [30,35,38] \leftrightarrow [40,42,45] \leftrightarrow [50,55,58]

Phase 1: Find Starting Position Search for lowKey = 25: Tree descent finds Leaf 3 (keys [20, 22, 28]) Binary search for first key \geq 25 Position found: index 2 (key = 28) Phase 2: Sequential Scan

Step	Current Leaf	Current Key	Compare with 48	Action
1	Leaf 3	28	28 ≤ 48 ✓	Add 28 to results
2	↓ end of Leaf 3, move to sibling
3	Leaf 4	30	30 ≤ 48 ✓	Add 30 to results
4	Leaf 4	35	35 ≤ 48 ✓	Add 35 to results
5	Leaf 4	38	38 ≤ 48 ✓	Add 38 to results
6	↓ end of Leaf 4, move to sibling
7	Leaf 5	40	40 ≤ 48 ✓	Add 40 to results
8	Leaf 5	42	42 ≤ 48 ✓	Add 42 to results
9	Leaf 5	45	45 ≤ 48 ✓	Add 45 to results
10	↓ end of Leaf 5, move to sibling
11	Leaf 6	50	50 > 48 ✗	Stop - upper bound exceeded

Range Query [25, 48] Execution Summary
Metric	Value	Explanation
Tree height traversals	1	Single descent to find starting leaf
Leaf nodes read	4	Leaves 3, 4, 5, 6 (stopped mid-scan on 6)
Total I/Os	~5	Height traversal + leaf reads
Keys examined	10	28, 30, 35, 38, 40, 42, 45, 50 + binary search
Keys returned	7	[28, 30, 35, 38, 40, 42, 45]

I/O Efficiency

Despite the tree containing many more leaves, we only read the 4 leaves that contain keys in our range. The linked list structure ensures we never read irrelevant leaves—we start at the right position and stop exactly when the range ends.

Handling Open-Ended Ranges

Open-ended range queries require special handling because one bound is effectively infinite. Let's examine each case:

Query Pattern: WHERE column >= value Algorithm: Search for the lower bound value Scan forward until reaching the end of the leaf chain No upper bound check needed Example: WHERE salary >= 80000 Find leaf containing 80000 Scan rightward through all remaining leaves Return all keys until NULL sibling pointer I/O Cost: O(log N) + O(k/b) where k is result count and b is keys per leaf Optimization: For queries returning a large fraction of the table, the optimizer may prefer a full table scan to avoid following many sibling pointers.

Selectivity Matters

An open-ended range query like WHERE age > 5 on an employee table will likely match nearly all rows. At this point, using the index becomes counterproductive—the query would read the entire index AND then fetch each row via record pointers (random I/Os). The optimizer may choose a sequential table scan instead.

Complexity Analysis for Range Queries

Let's rigorously analyze the cost of range queries in terms of I/O operations and CPU time.

Notation: N = total number of indexed entries n = B+-tree order (max children per node) k = number of keys in the result set (selectivity \times N) b = number of keys per leaf page h = tree height = O(log_n N) I/O Cost Breakdown: Finding the starting leaf: h I/Os (one per level) Scanning k matching keys: ⌈k/b⌉ leaf pages Total I/O: h + ⌈k/b⌉ For typical parameters: h \approx 3-5 (modest even for billions of rows) b \approx 100-200 (depends on key size and page size) Example: Range query returning 10,000 keys from a billion-row table with 4KB pages and 100 keys/leaf: Finding start: 5 I/Os Scanning leaves: 10,000/100 = 100 leaf I/Os Total: 105 I/Os Time at 10ms/random I/O: 1.05 seconds (improved with sequential read-ahead)

Range Query I/O Cost Examples (100 keys per leaf, height = 4)
Result Set Size (k)	Leaf Pages Read	Total I/Os	Approx. Time @ 10ms/IO
10	1	5	50 ms
100	1	5	50 ms
1,000	10	14	140 ms
10,000	100	104	1 second
100,000	1,000	1,004	10 seconds
1,000,000	10,000	10,004	100 seconds (without read-ahead)

Sequential Read-Ahead Optimization

When the storage system detects sequential leaf access, it can prefetch upcoming pages. With SSDs or large read-ahead buffers, sequential leaf scanning achieves near-streaming throughput—far faster than the random I/O estimates above. A 100,000-row range scan might take 1 second rather than 10 seconds with effective read-ahead.

CPU Cost: Binary search at each internal node: O(log n) per level = O(h \times log n) total for descent Binary search within starting leaf: O(log b) Comparison for each scanned key: O(k) Total CPU: O(h \times log n + k) CPU cost is typically negligible compared to I/O cost. For in-memory databases (all data cached), CPU becomes the bottleneck, but it still scales linearly with result size—unavoidable for any approach.

Range Queries: B+-tree vs Alternatives

How do B+-tree range queries compare to other approaches?

Range Query Performance Comparison
Structure	Range Query Cost	Key Advantage	Key Limitation
B+-tree	O(log N + k)	Linked leaves enable sequential scan	One tree descent required
Hash Index	O(N) — full scan required	N/A for ranges	Cannot support range queries at all
Sorted Array	O(log N + k)	Cache-friendly scan	O(N) insert cost prohibitive
Skip List	O(log N + k)	Simpler implementation	Less cache-efficient than B+-tree
Full Table Scan	O(N)	No index maintenance cost	Must examine every row

B+-tree Range Advantages

•Logarithmic start cost — find first match in O(log N)
•Linear scan cost — O(k) for k matching keys
•No additional sorting — results come in sort order
•Early termination — stop as soon as upper bound exceeded
•Incremental results — can return rows as scanned

When B+-tree Range Query Loses

•Very low selectivity — returning 80%+ of table
•Unclustered access — index scan then N random fetches
•Multi-column ranges — only first column uses tree
•Highly concurrent OLTP — range locks may bottleneck
•Wide rows — may be better to scan table directly

The Unclustered Access Problem

When the index is not clustered (data rows not stored in index order), each index entry points to a potentially random location in the heap. A range scan returning 1,000 rows might require 1,000 random I/Os to fetch the actual data. This is often slower than a full table scan, leading optimizers to skip the index for large range queries on non-clustered indexes.

Range Queries

The Killer Feature of B+-Trees

Types of Range Queries

The Linked Leaf Architecture

The Range Query Algorithm

Worked Example: Complete Range Scan

Handling Open-Ended Ranges

Complexity Analysis for Range Queries

Range Queries: B+-tree vs Alternatives

There’s more to understand.

Range Queries

The Killer Feature of B+-Trees

Types of Range Queries

The Linked Leaf Architecture

The Range Query Algorithm

Worked Example: Complete Range Scan

Handling Open-Ended Ranges

Complexity Analysis for Range Queries

Range Queries: B+-tree vs Alternatives

There’s more to understand.