数据库索引如何支持>=、<=等范围查询？以foo>10场景为例

Hey there! Great question—you’re right that equality checks like foo = 10 use indexes in a super straightforward way, but it’s a common myth that range queries (like foo > 10, foo <= 20, etc.) can’t leverage indexes. Let’s break down exactly how this works, focusing on the B+ Tree index—by far the most common index type in relational databases like PostgreSQL, MySQL, and SQL Server.

A Quick B+ Tree Refresher #

First, let’s recap how these indexes are structured, since that’s the foundation of how they handle both equality and range queries:

• B+ Trees are ordered, balanced trees. Non-leaf nodes act like signposts, guiding the database to the right section of the index.
• Leaf nodes hold all the index keys (your foo values) in sorted order, plus pointers that lead directly to the corresponding rows in your table. Even better, leaf nodes are linked together in a sequential list, making it easy to scan through ranges.

How Equality Queries (foo = 10) Work #

For WHERE foo = 10, the process is pretty direct:

1. Start at the root of the B+ Tree.
2. Traverse down the tree, comparing 10 with the keys in each non-leaf node, until you land on the leaf node that contains 10.
3. Since duplicate keys are grouped together in leaf nodes, you can grab all rows with foo = 10 in one contiguous block, then use the pointers to fetch the actual table data.

How Range Queries (foo > 10, foo >= 10, etc.) Work #

Range queries actually play to the B+ Tree’s biggest strength—its sorted structure. Let’s walk through SELECT * FROM mytable WHERE foo > 10:

1. The database starts at the root and traverses down to find the first leaf node where foo is greater than 10. It uses the non-leaf nodes to skip entire sections of the index that can’t possibly contain values >10 (no need to check keys 5, 8, etc.).
2. Once it finds that starting leaf node, it scans sequentially forward through the linked leaf nodes (since they’re sorted) until it hits the end of the range—either the first foo value that’s not greater than 10, or the end of the index entirely.
3. For each key in this range, it uses the pointer to pull the corresponding table row.

The same logic applies to other range operators:

• foo >= 10: Starts at the first leaf node with foo = 10, then scans forward through all entries from 10 onward.
• foo < 10: Traverses to the last leaf node with foo < 10, then scans backward (or forward from the start up to that point, depending on the database’s implementation).
• foo <= 10: Starts at the first foo = 10 entry, scans through all duplicates of 10, then stops—no need to go beyond that.

When Might a Range Query Skip the Index? #

There are a few cases where the database optimizer might choose a full table scan instead of using the index:

• Low selectivity: If your range covers most of the table (e.g., foo > 0 where 90% of rows have foo > 0), it’s faster to scan the whole table than to jump back and forth between index entries and table rows (this back-and-forth is called "bookmark lookup" overhead).
• Non-covering index: If your query selects columns that aren’t in the index (like SELECT * when the index is only on foo), the database has to do a lookup for every row in the range. For large ranges, this overhead can make the index less efficient than a full scan.
• Outdated statistics: If the database’s table statistics are old, the optimizer might miscalculate how big the range is and pick a suboptimal plan. Updating stats usually fixes this.

A Concrete Example #

Suppose your mytable has foo values: 5, 8, 10, 12, 15, 20, 25. The B+ Tree index on foo keeps these sorted in leaf nodes. For foo > 10:

1. The database finds the first leaf node with 12.
2. It scans through 12, 15, 20, 25, fetching each corresponding row.
3. It never touches the rows with 5, 8, or 10—those are skipped entirely.

That’s way more efficient than scanning every row in the table!

内容的提问来源于stack exchange，提问作者Lance Pollard