Lesson 42 · Web and backend

Indexes and transactions

Two ideas make databases both fast and safe. An index lets the database jump to the rows you want instead of reading every one, at the cost of extra space and slower writes. A transaction groups several changes so they all happen or none do. Watch a query scan a table, then walk a B-tree straight to its row, and watch a bank transfer crash halfway, get rolled back, and finally commit.

12 min12 steps5 questionsBeginner

Fig 42 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01A table has 1,000,000 rows and no index on email. What does SELECT * FROM users WHERE email = 'sam@example.com' have to do?

Without an index the database has no way to know where the matching rows are, so it checks every row. The work grows with the number of rows, O(n).

02Why does an index on name make WHERE name = 'Kai' fast?

Each step down the tree skips most of the remaining names, so the work grows like log n. The leaf entry gives the row id, so only that one row is read.

03What is the main cost of adding an index?

An index is a second structure that the database keeps up to date, so writes do more work and the file grows. Index the columns you search often.

04Inside a transaction, 50 is taken from Ana, and then the program crashes before Ben is paid. What does the database do?

Atomicity: a transaction that did not reach COMMIT is undone as if it never started. SQLite does this from its rollback journal when the database is opened again.

05Which ACID property means a committed change survives a crash or power cut a moment later?

Durability: once COMMIT returns, the change is safely stored. Isolation is about other users not seeing half-done work; atomicity is all-or-nothing.

Key terms

Glossary

Full table scan: Reading every row of a table to find the matching ones. The work grows with the number of rows, O(n).
Index: A second, sorted structure over one or more columns, with a pointer from each entry to its row, so lookups do not need a full scan.
B-tree: A shallow tree of sorted nodes used by most databases for indexes. Each level narrows the search, so a lookup takes about log n steps.
Transaction: A group of changes that the database treats as one unit: all of them happen, or none of them do.
COMMIT: The command that ends a transaction and makes its changes permanent and visible to everyone.
ROLLBACK: The command that ends a transaction by undoing all of its changes. The database also rolls back a transaction cut off by a crash.
ACID: Atomicity (all or nothing), Consistency (valid state to valid state), Isolation (no one sees half-done work) and Durability (committed changes survive crashes).
Undo journal: A note of the old values the database keeps while a transaction runs, so it can put them back. SQLite calls it the rollback journal.

Fine print

Notes and sources

name is not unique, so a scan cannot stop at the first Kai it meets: another Kai could be further down.
Real index nodes are disk pages holding hundreds of entries, so the tree stays very shallow: if every node points to 100 children, three levels already reach 100 × 100 × 100 = 1,000,000 rows.
The drawing shows a tiny classic B-tree. SQLite keeps each table and each index in its own b-tree, and PostgreSQL makes a B-tree when CREATE INDEX names no other type.
SQLite (in its default mode) copies the original content into a rollback journal before it changes the database. PostgreSQL instead keeps a write-ahead log; both let the database recover a consistent state after a crash.
How strictly transactions are kept apart is set by the isolation level. In PostgreSQL even the weakest level never shows another transaction's uncommitted changes.
In Python, sqlite3.connect(..., isolation_level=None) lets you write BEGIN and COMMIT yourself. With the default settings, `with db:` commits the block's changes if it finishes and rolls them back if an error escapes it.

Quiz Unlocks after the last step.