DevPath
Tracks

Indexes, Query Plans, and Transactions

How B-tree indexes turn scans into lookups, how to read EXPLAIN output, and what ACID and isolation levels guarantee, with a runnable SQLite demo.

intermediate50 min#indexes#b-tree#explain#transactions#acid#isolation

Prerequisites: Databases and SQL, Trees and Binary Search Trees

Why it matters

The same query can take 2 milliseconds or 20 seconds depending on one CREATE INDEX statement, and that is the most common database performance fix. On the correctness side, transactions are why a bank does not lose money when a server crashes mid-transfer. Knowing both lets you debug slow pages and data corruption alike, and they are staples of backend interviews.

Intuition

A book's index lets you find "photosynthesis" without reading every page: it keeps terms sorted, each with page numbers. A database index is the same thing: a sorted structure over one or more columns that points back to rows. The cost is that every insert or update must also update the index, and it takes space.

A transaction is a bundle of steps treated as one. Moving 70 from Alice to Bob is two writes: credit Bob, debit Alice. If the machine dies between them, money appears from nowhere. A transaction promises all-or-nothing.

How it works

B-tree indexes. Most databases store indexes as B-trees (or B+ trees): a balanced tree where each node holds many sorted keys, sized to fit a disk page. Fanout is in the hundreds, so a table of a billion rows needs only about four levels. Looking up a key means walking root to leaf: O(log n) page reads, versus O(n) for a full scan.

            [ 40 | 80 ]
           /     |      \
   [10 20 30] [50 60 70] [90 95 99]     leaves: sorted, linked, point to rows

Walking that tree to find key 60 touches only one node per level.

40 | 8010 20 3050 60 7090 95 99
Lookup of 60: at the root, 60 is between 40 and 80, so follow the middle child, then find 60 among its sorted keys. Two page reads instead of scanning every leaf.

Because keys are sorted, a B-tree also serves range queries (BETWEEN), ORDER BY, and prefix searches. It cannot help LIKE '%cache' (leading wildcard) or a function applied to the column, such as WHERE lower(email) = ..., unless you index that expression.

Composite indexes. An index on (a, b) is sorted by a, then b within each a. It helps filters on a, or on a and b, but not on b alone (leftmost prefix rule). Put equality columns first, range columns after.

Reading a query plan. EXPLAIN (in SQLite, EXPLAIN QUERY PLAN) shows the strategy without running the query. Look for SCAN (reads every row) versus SEARCH ... USING INDEX (jumps via the index). A covering index contains every column the query needs, so the table itself is never touched.

ACID

  • Atomicity: all steps happen or none do (rollback on failure).
  • Consistency: a transaction moves the database from one valid state to another; constraints such as CHECK, UNIQUE, and foreign keys are enforced.
  • Isolation: concurrent transactions do not see each other's half-done work.
  • Durability: once committed, data survives a crash, typically via a write-ahead log flushed to disk.

Isolation anomalies. Running transactions fully one after another is safe but slow, so databases offer weaker levels.

  • Dirty read: you read data another transaction has not committed, and it later rolls back.
  • Non-repeatable read: you read a row twice in one transaction and get different values because someone committed in between.
  • Phantom read: you run the same range query twice and new rows appear.
  • Lost update / write skew: two transactions read the same data, then write based on stale reads (the database version of the race condition from the threads lesson).

Here is a non-repeatable read, step by step.

Transaction ATransaction BDatabaseread Bob's balance50set Bob's balance to 120COMMITread Bob's balance again120 (changed inside A)
Transaction A saw two different values for the same row because B committed in between. REPEATABLE READ or SERIALIZABLE would keep returning 50 to A.

Standard levels: READ UNCOMMITTED allows dirty reads; READ COMMITTED forbids them; REPEATABLE READ also forbids non-repeatable reads; SERIALIZABLE behaves as if transactions ran one at a time. Exact behavior varies by engine, so check your database's documentation. SQLite is the simple end: one writer at a time, and transactions are serializable.

OperationTimeNotes
Lookup with B-tree indexO(log n)A handful of page reads
Lookup without indexO(n)Full table scan
Insert with k indexesO(k log n)Every index must be updated
Range scan of m matchesO(log n + m)Find start, then walk leaves

Code: plans and rollback

Python uses SQLite for real: first the query plan before and after an index, then an atomic transfer whose second step violates a constraint. Node has no guaranteed bundled SQL engine, so the JavaScript tab simulates the ideas by hand: a sorted array with binary search stands in for the index, and a snapshot restore stands in for rollback.

import sqlite3
 
con = sqlite3.connect(":memory:")
con.execute("CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT)")
con.executemany(
    "INSERT INTO users VALUES (?, ?)",
    [(i, f"user{i}@example.com") for i in range(1000)],
)
 
 
def plan(sql, args=()):
    for row in con.execute("EXPLAIN QUERY PLAN " + sql, args):
        print(row[3])
 
 
query = "SELECT id FROM users WHERE email = ?"
plan(query, ("user42@example.com",))
con.execute("CREATE INDEX idx_users_email ON users(email)")
plan(query, ("user42@example.com",))
 
con.execute("CREATE TABLE accounts (name TEXT PRIMARY KEY, balance INTEGER CHECK (balance >= 0))")
con.executemany("INSERT INTO accounts VALUES (?, ?)", [("alice", 100), ("bob", 50)])
 
 
def transfer(src, dst, amount):
    try:
        with con:  # commit on success, rollback on exception
            con.execute("UPDATE accounts SET balance = balance + ? WHERE name = ?", (amount, dst))
            con.execute("UPDATE accounts SET balance = balance - ? WHERE name = ?", (amount, src))
        return "committed"
    except sqlite3.IntegrityError:
        return "rolled back"
 
 
def show():
    rows = con.execute("SELECT name, balance FROM accounts ORDER BY name")
    return " ".join(f"{name}={bal}" for name, bal in rows)
 
 
print(transfer("alice", "bob", 70), show())
print(transfer("alice", "bob", 70), show())

The Python version prints (the exact plan wording can differ slightly between SQLite versions):

SCAN users
SEARCH users USING COVERING INDEX idx_users_email (email=?)
committed alice=30 bob=120
rolled back alice=30 bob=120

The JavaScript version prints scan steps 43, index steps 7, then the same two transfer lines as Python. Forty-three comparisons for a scan against seven for the sorted lookup, and the gap widens as the table grows.

Full scan
43 comparisons
Sorted index lookup
7 comparisons
Comparisons to find one email among 1000 rows, taken from the demo output. The scan grows with the table size while the index grows only logarithmically.

In the failed transfer, Bob was credited first, and only then did Alice's debit break the CHECK. Rollback undoes Bob's credit, so the balances are unchanged. That is atomicity in action.

AppDatabaseBEGIN (alice=100, bob=50)credit bob +70debit alice -70COMMITdurable: alice=30, bob=120
First transfer: both writes succeed, so COMMIT makes them permanent together.
AppDatabaseBEGIN (alice=30, bob=120)credit bob +70 (pending: bob=190)debit alice -70CHECK failed: balance would be -40ROLLBACKundone: alice=30, bob=120
Second transfer: the second write breaks the CHECK, so ROLLBACK also undoes the first write. All or nothing.

Common pitfalls

  • Indexing everything: each index slows writes and uses space. Index columns that appear in WHERE, JOIN, and ORDER BY of frequent queries.
  • Functions on indexed columns: WHERE date(created) = '2025-01-01' bypasses a plain index on created. Rewrite as a range, or index the expression.
  • Low-selectivity indexes: an index on a boolean column rarely helps because half the table matches.
  • Wrong composite order: an index on (b, a) does not help a query filtering only on a.
  • Trusting a plan on tiny data: with 20 rows a scan is as fast as anything, and the planner may choose it. Test with realistic volumes.
  • Long transactions: they hold locks, block others, and bloat logs. Keep them short, and never wait for user input inside one.
  • Assuming the default isolation level is serializable: many engines default to read committed, which allows non-repeatable reads and write skew.

Practice

Add the missing index easy

Hint

Which column does the WHERE clause filter on?

Show solution

Plan says SCAN orders for WHERE customer_id = ?. Run CREATE INDEX idx_orders_customer ON orders(customer_id), re-run EXPLAIN, and expect SEARCH orders USING INDEX idx_orders_customer (customer_id=?).

Order the composite index medium

Hint

Equality first, range second.

Show solution

Query: WHERE status = 'paid' AND created > '2025-01-01' ORDER BY created. Index (status, created) jumps to status = 'paid', then walks the already sorted created values, which also satisfies the ORDER BY without a sort. The reverse order (created, status) would scan the whole date range and filter status row by row.

Name the anomaly medium

Hint

Two reads, one commit in the middle.

Show solution

Transaction A reads Bob's balance (50). Transaction B commits a deposit making it 120. A reads Bob again and sees 120. That is a non-repeatable read. REPEATABLE READ or SERIALIZABLE prevents it. If A had seen B's change before B committed, that would be a dirty read.

Prevent overselling hard

Hint

Two buyers both read stock = 1.

Show solution

Reading stock, checking it, then writing stock - 1 is a lost-update race. Fix it with a single atomic statement: UPDATE items SET stock = stock - 1 WHERE id = ? AND stock > 0 and check that one row changed. Alternatives are SELECT ... FOR UPDATE to lock the row (in engines that support it), a serializable transaction with retry, or optimistic locking using a version column.

Interview questions

  1. How does a B-tree index speed up a query, and what does it cost? Sorted, shallow, wide tree gives O(log n) lookups and fast ranges; it costs space and slows writes.
  2. Why might the database ignore your index? Low selectivity, a function on the column, a type mismatch, a leading wildcard, or the planner estimating a scan is cheaper.
  3. Explain ACID. Atomic, consistent, isolated, durable; be ready with a bank-transfer example for each letter.
  4. What is a phantom read, and which level prevents it? New rows appearing in a repeated range query; serializable prevents it (some engines prevent it at repeatable read).
  5. Pessimistic versus optimistic concurrency? Pessimistic locks rows up front and waits; optimistic proceeds, checks a version at commit, and retries on conflict. Optimistic suits low contention.

Interviewers look for: reading EXPLAIN before guessing, knowing the leftmost-prefix rule, giving a concrete example for each anomaly, and mentioning that stronger isolation costs throughput.

Quick check

A table has a composite index on (country, city). Which query can use it efficiently?

Finished this lesson?

Further resources

Related lessons