Day 4:Database Internals — B-Tree Indexes (O(log N)), EXPLAIN QUERY PLAN & ACID Transactions
Battle-tested daily lesson note • 100% runnable code, interview Q&A, test suite & interactive quiz
Week 3 — Day 4: Database Internals — B-Tree Indexes (O(log N)), EXPLAIN QUERY PLAN & ACID Transactions
Mentor's Note (10+ YOE Staff AI Engineer POV): Why does a database query that ran in
2msduring development suddenly take12,000ms(12 seconds!) when your AI app hits 1,000,000 rows in production? Because someone forgot to add a B-Tree Index on theWHERE/JOINcolumn!Today you learn:
- The Math of B-Tree Indexes: How a balanced tree with branching factor turns a
1,000,000row Full Table Scan () into just 3 disk page reads (, )!- Reading Query Plans (
EXPLAIN QUERY PLAN): How to prove whether SQLite/PostgreSQL is doing a slowSCANvs a fastSEARCH ... USING INDEX.ACIDTransactions (BEGIN,COMMIT,ROLLBACK): Ensuring that if deducting user credits succeeds, but saving the LLM response fails, the entire transaction rolls back atomically!
Part 1: Full Table Scan () vs B-Tree Index ()
WITHOUT INDEX (Full Table Scan = O(N)):
Query: SELECT * FROM logs WHERE trace_id = 'trace_49999';
Database must inspect Row 1 -> Row 2 -> Row 3 -> ... -> Row 50,000!
WITH B-TREE INDEX (`CREATE INDEX idx_logs_trace_id ON logs(trace_id)` = O(log N)):
[Root Node: 'trace_25000']
/ \
[<'trace_25000'] [>='trace_25000']
\
[Leaf Page -> Jumps straight to Row #49,999 in 3 steps!]
The Composite Index "Leftmost-Prefix Rule" (Senior Interview Favorite!)
Suppose you create a two-column composite index:
CREATE INDEX idx_tenant_created ON llm_requests(tenant_id, created_at);
Because the B-Tree sorts first by tenant_id, and then by created_at within each tenant_id (just like a phonebook sorted by Last Name, First Name):
WHERE tenant_id = 5 AND created_at > '2026-01-01'Uses Index!WHERE tenant_id = 5Uses Index! (Matches the leftmost columntenant_id).WHERE created_at > '2026-01-01'(withouttenant_id!) CANNOT Use Index properly! (Like trying to use aLast Name, First Namephonebook to find everyone whose first name is "Rahul"!).
Part 2: ACID Properties of Relational Transactions
| Letter | Property | Meaning in AI Engineering |
|---|---|---|
| A | Atomicity | "All or Nothing." If inserting the assistant message AND deducting user token quota are in one transaction, either both succeed (COMMIT) or both undo (ROLLBACK). |
| C | Consistency | Every transaction brings the database from one valid state to another (all FOREIGN KEY, UNIQUE, and CHECK constraints hold). |
| I | Isolation | Concurrent transactions from two users do not corrupt each other's intermediate states. |
| D | Durability | Once committed (COMMIT), data is written to disk (WAL — Write-Ahead Log) and survives power loss. |
Part 3: Hands-On Lab — B-Tree Index Benchmark & Atomic Transaction Rollback (btree_index_benchmark.py)
Check out src/btree_index_benchmark.py (in Tab 2: Codes — click Run in Browser to execute) and run the live 40,000-row benchmark and tests:
python week03_sql_databases_from_zero_to_pro/day04_btree_indexes_query_plans_and_acid/src/btree_index_benchmark.py
python -m unittest discover -s week03_sql_databases_from_zero_to_pro/day04_btree_indexes_query_plans_and_acid/tests -v
In Simple English: Why Is Magical
Imagine looking for the word "Zebra" in a 1,000,000-page book:
- Without an Index (
O(N)): You turn Page 1, Page 2, Page 3... up to 1,000,000 pages! - With a B-Tree Index (
O(log N)): Each index page holds ~500 sorted signposts ("A–C go to folder 1, D–F go to folder 2...").- Hop 1: Jump straight to the
Zshelf (500choices narrowed). - Hop 2: Jump straight to
Ze-(500 x 500 = 250,000narrowed). - Hop 3: Land right on "Zebra"! Just 3 reads instead of 1,000,000!
- Hop 1: Jump straight to the
Click Run in Browser in Tab 2 (Codes) to execute the real 40,000-row SQLite benchmark live in WebAssembly!