Understanding B+Tree Indexes and Three Practical Strategies for SQL Optimization

There are countless articles that explain index principles, classifications, physical organization, and storage formats, but most of them do not address what developers truly care about. This piece takes a different perspective, focusing on B+Tree indexes and how they can help you.

When developers look at a SQL statement, the primary concern is not how the database executes it internally, but whether it can return results quickly. The essence of SQL optimization is to minimize resource consumption, aiming for the ultimate goal of doing nothing in the database.

Resources are limited and have varying costs: CPU cycles (nanoseconds), memory (microseconds), SSD (hundreds of microseconds), spinning disks (milliseconds), and network latency (even higher). Accessing CPU caches is cheaper than memory, which is cheaper than disk. Consequently, SQL bottlenecks often stem from contention for these resources. In a modern computer, the coarse‑grained resources are CPU, memory, disk, and network. SQL consumes CPU for comparisons, sorting, parsing, and functions; memory for cached and temporary data; disk for cold data reads, large sorts, joins, and writes; and network for request/response traffic.

Before diving into theory, let’s become index masters with three quick tricks. After practicing these, the earlier performance questions become clear.

SELECT CNO, FNAME<br/>FROM CUST<br/>WHERE LNAME = :LNAME AND CITY = :CITY<br/>ORDER BY FNAME

First trick: Create a single‑star (composite) index on the equality or range columns in the WHERE clause, e.g., INDEX(LNAME, CITY). An index trades space for time, but it also filters out unnecessary rows early, dramatically shrinking the data set that needs to be processed. For a table with 1,000,000 rows where CITY filters 10% and LNAME filters 0.1%, the index reduces the rows to read to roughly 100, instead of scanning the whole table.

Second trick: Build a two‑star index INDEX(LNAME, CITY, FNAME). By leveraging the index’s ordering, the database can satisfy the ORDER BY (or GROUP BY) without an extra sort operation, saving CPU and avoiding costly disk‑based sorts when the data does not fit in memory.

Third trick: Build a three‑star (covering) index INDEX(LNAME, CITY, FNAME, CNO). Adding the columns required by the SELECT clause to the index allows the query to be answered entirely from the index leaf nodes, eliminating the need to read the base table and further reducing physical I/O.

In practice, SQL statements vary widely, with dynamic conditions, complex joins, and multiple tables. You cannot apply the three tricks blindly; instead, choose the most selective columns for the index, consider join patterns (e.g., small‑table‑driven nested loops), and balance index benefits against maintenance costs.

Over‑indexing incurs storage overhead and DML penalties. Some NoSQL systems maintain secondary indexes asynchronously, sacrificing strong consistency for performance—something traditional RDBMS cannot do. For InnoDB, using an auto‑increment numeric primary key improves insertion order and reduces index fragmentation. Avoid large columns as primary keys because they bloat secondary indexes. Periodic index rebuilds (e.g., in Oracle) can reclaim space.

B+Tree indexes are disk‑ and SSD‑oriented structures with O(log₂n) read and write complexity. Writes involve an update‑in‑place approach, which can be slower than reads. Alternatives like LSM‑trees trade some read performance for faster writes. Future data structures may achieve better read/write balance.

In summary, when business‑level optimizations are set aside, indexes are the most effective “medicine” for SQL performance, while other techniques become secondary. B‑Tree indexes are widely supported across relational databases, making the knowledge transferable between systems such as Oracle and MySQL.