B-Tree Index

Hook: Interviewers love this one because a B-tree index is the everyday tool that turns a slow table scan into a fast, sorted shortcut.

Question: What is a B-tree index in SQL, and why does it improve performance?

Answer: A B-tree index is a sorted data structure that lets the database find rows without reading the whole table. It keeps keys balanced, so search, range filters, and ordered reads are fast. In many SQL engines, the concrete structure is really B+tree-like, meaning the leaf pages are linked so nearby values can be read in order.

Interview-Ready Answer: I think of a B-tree index as a library catalog for a table. Instead of scanning every row, the database compares the key at a few levels, lands on the right leaf page, and then walks nearby entries in order. That is why B-tree indexes are the default general-purpose index in systems like PostgreSQL: they work well for equality lookups, ranges, and ORDER BY.

What it is

A B-tree is a balanced tree, which means every search path has about the same length. A page is a fixed-size block of storage, often 8 KB in PostgreSQL, and a fan-out is how many child pointers fit in one internal page. Big fan-out is the secret sauce: even with millions of rows, the tree is usually only a few levels deep.

How it works under the hood

1. The database starts at the root page and compares the search key with separator keys stored there.
2. It follows the correct child pointer to a lower internal page, then repeats the comparison.
3. It eventually reaches a leaf page, which stores sorted index entries and pointers to the table rows.
4. For an equality lookup, it finds the exact key or learns there is no match very quickly.
5. For a range query like BETWEEN or >=, it scans forward through linked leaf pages instead of jumping back to the root each time.
6. For an insert, if the target leaf page is full, the engine splits the page into two pages and updates the parent; deletes may redistribute or merge pages later.

When to use it

Use a B-tree when you need equality filters, range filters, prefix searches that match the left side of the key, sorting, or fast joins on indexed columns. In practice, this is the everyday index for customer IDs, timestamps, email addresses, and foreign keys.

Comparison with other choices

Performance notes and gotchas

• Lookup cost is about O(log n) in the number of rows, but the real win is fewer page reads. With short keys and an 8 KB page, a million-row index often has only 3 to 4 levels.
• Wide text keys reduce fan-out, so the tree gets taller and slower. That is why index size and column choice matter.
• Every insert, update to an indexed column, and delete must maintain the index, so B-trees speed reads at the cost of extra write work.
• Composite indexes obey the leftmost prefix rule: the first column matters most. A predicate on the second column alone usually cannot use the same index efficiently.
• Wrapping a column in a function, such as DATE(created_at), often blocks normal index use unless you create an expression index.
• Most engines can index NULL values, but ordering details and planner behavior vary by database version and vendor.

The mental model to keep: a B-tree is not magic; it is a very organized shortcut that keeps the search space small and sorted.

Real-world story

Imagine a checkout service for an e-commerce site. The app needs to find recent orders by customer_id and sort them by created_at, so the team adds a B-tree index on (customer_id, created_at). That makes customer support screens and fraud checks fast because the database can jump straight to one customer’s slice of the data.

Then a developer changes a query to WHERE DATE(created_at) = CURRENT_DATE because it looks cleaner. Suddenly the index is much less useful, the database starts scanning far more rows, CPU climbs, and the p95 latency jumps from milliseconds to seconds. The logs show slow query entries, the dashboard shows more sequential scans, and users feel it as a laggy checkout or a timeout on order history pages.

What went wrong: the team forgot that B-tree indexes work best when the predicate matches the stored order of the key. A small-looking function wrapper changed the access pattern enough to defeat the shortcut.

Follow-up & Tricky Questions:

• How does a B-tree help ORDER BY? If the query sorts by the same key order as the index, the database can read the index in order and avoid an expensive sort step.
• Why might the planner ignore a B-tree index? If the table is tiny, the predicate matches too many rows, or statistics say a sequential scan is cheaper, the optimizer may skip the index.
• What is the leftmost prefix rule? In a composite index, the first column drives access. You can usually use the index best when predicates start with the leftmost column, then optionally continue to later columns.
• What is the write cost of a B-tree? Inserts and updates can split pages and update parent pages, so heavy write workloads pay extra maintenance cost even though reads get faster.
• What is a covering index? It is an index that contains all columns needed by the query, so the engine may answer from the index alone without visiting the table rows.
• Can a B-tree help with joins? Yes, especially on join keys like foreign keys, because the database can probe the index repeatedly instead of scanning the whole table on each join.
• Can one B-tree replace every other index type? No. It is general-purpose, but specialized indexes are better for text search, geospatial data, or very specific equality-only cases.
• Can B-tree support DESC order? Usually yes, because the engine can scan the index backward or use a descending index definition depending on the database.
• Can B-tree use LIKE '%abc'? Usually no, because the leading wildcard removes the ordered prefix the tree needs to jump into the right place.
• Does a B-tree always beat a hash index? No. Hash can be fine for pure equality, but B-tree is more flexible and is the safer first choice in most SQL systems.

• Tricky: Can WHERE first_name = 'Liam' use an index on (last_name, first_name)? Usually not efficiently, because the first column is missing. The database may scan the index, but that is not the same as a clean indexed lookup.
• Tricky: Are B-tree indexes only for exact matches? No. They are especially useful for ranges and ordered output, which is why they are so common in SQL.
• Tricky: Does adding more indexes always make reads faster? Not necessarily. Too many indexes slow writes, take space, and can confuse the optimizer if they overlap badly.

Common Mistakes:

• Thinking every index helps every query. Correction: an index only helps when the predicate and sort order match the index structure well.
• Putting composite columns in the wrong order. Correction: put the most selective and most commonly filtered leading column first, especially for equality and range patterns you really run.
• Indexing very low-selectivity columns alone. Correction: a boolean or status column by itself may still touch too many rows to beat a table scan.
• Wrapping indexed columns in functions without planning for it. Correction: use expression indexes or rewrite the predicate so the index order stays visible to the optimizer.

Memory Hook: A B-tree is a library catalog: each card points to the right drawer, the drawers stay sorted, and you never read the whole library just to find one book.

Cheat Sheet:

• Default general-purpose SQL index.
• Best for equality, ranges, and ORDER BY.
• Balanced tree, usually a few levels deep.
• Composite indexes follow leftmost prefix rules.
• Reads get faster; writes get more expensive.
• Leading wildcards and wrapped columns often block use.

Practice Tasks:

• Create a table with 100,000 rows and compare a table scan to an indexed lookup using EXPLAIN.
• Build a composite index and test which queries use it when you change the column order.
• Try a query with LIKE 'abc%' and then LIKE '%abc' to see why prefix searches are index-friendly but suffix searches are not.