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.
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.
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.
| Operation | Time | Notes |
|---|---|---|
| Lookup with B-tree index | O(log n) | A handful of page reads |
| Lookup without index | O(n) | Full table scan |
| Insert with k indexes | O(k log n) | Every index must be updated |
| Range scan of m matches | O(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())// "Index": keep the keys sorted so we can binary-search them.
const emails = Array.from({ length: 1000 }, (_, i) => `user${i}@example.com`);
const sorted = [...emails].sort();
const target = "user42@example.com";
function scan(rows, key) {
let steps = 0;
for (const value of rows) {
steps++;
if (value === key) break;
}
return steps;
}
function binarySearch(rows, key) {
let lo = 0;
let hi = rows.length - 1;
let steps = 0;
while (lo <= hi) {
steps++;
const mid = (lo + hi) >> 1;
if (rows[mid] === key) return steps;
if (rows[mid] < key) lo = mid + 1;
else hi = mid - 1;
}
return steps;
}
console.log("scan steps", scan(emails, target));
console.log("index steps", binarySearch(sorted, target));
// "Transaction": snapshot the state, restore it if any step fails.
const accounts = { alice: 100, bob: 50 };
function transfer(src, dst, amount) {
const snapshot = { ...accounts };
try {
accounts[dst] += amount;
accounts[src] -= amount;
if (accounts[src] < 0) throw new Error("CHECK constraint failed");
return "committed";
} catch {
Object.assign(accounts, snapshot); // rollback
return "rolled back";
}
}
const show = () => `alice=${accounts.alice} bob=${accounts.bob}`;
console.log(transfer("alice", "bob", 70), show());
console.log(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.
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.
Common pitfalls
- Indexing everything: each index slows writes and uses space. Index columns that appear in
WHERE,JOIN, andORDER BYof frequent queries. - Functions on indexed columns:
WHERE date(created) = '2025-01-01'bypasses a plain index oncreated. 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 ona. - 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
- 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.
- 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.
- Explain ACID. Atomic, consistent, isolated, durable; be ready with a bank-transfer example for each letter.
- 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).
- 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
- SQLite query planner overview (docs)
- SQLite: EXPLAIN QUERY PLAN (docs)
- SQLite isolation (docs)
- ACID (Wikipedia) (article)