Week 3 • Day 4Week 3

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 2ms during development suddenly take 12,000ms (12 seconds!) when your AI app hits 1,000,000 rows in production? Because someone forgot to add a B-Tree Index on the WHERE / JOIN column!

Today you learn:

  1. The Math of B-Tree Indexes: How a balanced tree with branching factor B≈500B \approx 500 turns a 1,000,000 row Full Table Scan (O(N)O(N)) into just 3 disk page reads (log⁡500(106)≈3\log_{500}(10^6) \approx 3, O(log⁡N)O(\log N))!
  2. Reading Query Plans (EXPLAIN QUERY PLAN): How to prove whether SQLite/PostgreSQL is doing a slow SCAN vs a fast SEARCH ... USING INDEX.
  3. ACID Transactions (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 (O(N)O(N)) vs B-Tree Index (O(log⁡N)O(\log N))

text
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:

sql
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' →\rightarrow Uses Index!
  • WHERE tenant_id = 5 →\rightarrow Uses Index! (Matches the leftmost column tenant_id).
  • WHERE created_at > '2026-01-01' (without tenant_id!) →\rightarrow CANNOT Use Index properly! (Like trying to use a Last Name, First Name phonebook to find everyone whose first name is "Rahul"!).

Part 2: ACID Properties of Relational Transactions

LetterPropertyMeaning in AI Engineering
AAtomicity"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).
CConsistencyEvery transaction brings the database from one valid state to another (all FOREIGN KEY, UNIQUE, and CHECK constraints hold).
IIsolationConcurrent transactions from two users do not corrupt each other's intermediate states.
DDurabilityOnce 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:

powershell
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 log⁡500(1,000,000)≈3\log_{500}(1,000,000) \approx 3 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 Z shelf (500 choices narrowed).
    • Hop 2: Jump straight to Ze- (500 x 500 = 250,000 narrowed).
    • Hop 3: Land right on "Zebra"! Just 3 reads instead of 1,000,000!

Click Run in Browser in Tab 2 (Codes) to execute the real 40,000-row SQLite benchmark live in WebAssembly!