Relational Database Architecture, B-Trees & Query Optimization
Master relational schema normalization, B-Tree index structures, EXPLAIN ANALYZE query planning, transaction isolation levels, and ACID guarantees.
Key Learning Objectives
- Explain how B-Trees organize database indexes and enable O(log n) seeks and range scans.
- Understand the Left-Prefix Rule for composite indexes and prevent unindexed full table scans.
- Analyze transaction anomalies: Dirty Reads, Non-Repeatable Reads, and Phantom Reads.
- Write optimized SQL queries using CTEs, Window Functions, and covering indexes.
B-Tree Indexes & Disk Block Access
Relational databases like PostgreSQL and MySQL store table data in fixed-size disk blocks or pages (typically 8KB or 16KB). Without an index, finding a specific row requires a sequential table scan: reading every single page from disk into RAM, which is O(n) and disk I/O bound. A B-Tree index creates a balanced, multi-way search tree where each non-leaf node contains hundreds of keys pointing to child pages, and leaf nodes form a doubly linked list of sorted keys pointing directly to the heap tuple IDs. Because of high branching factors (typically 100-500), a table with 10 million rows can be traversed in only 3 to 4 disk page reads (O(log n)).
-- Schema with Composite Index
CREATE TABLE orders (
id BIGSERIAL PRIMARY KEY,
user_id BIGINT NOT NULL,
status VARCHAR(32) NOT NULL,
total_amount NUMERIC(10, 2) NOT NULL,
created_at TIMESTAMP WITH TIME ZONE DEFAULT NOW()
);
-- Composite Index supporting: WHERE user_id = ? AND status = ? ORDER BY created_at DESC
CREATE INDEX idx_orders_user_status_date ON orders(user_id, status, created_at DESC);
-- Query using index seek:
EXPLAIN ANALYZE
SELECT id, total_amount, created_at
FROM orders
WHERE user_id = 42 AND status = 'COMPLETED'
ORDER BY created_at DESC
LIMIT 10;
EXPLAIN ANALYZE shows an "Index Scan" instead of a "Seq Scan", fulfilling both the filter and the sort order without an in-memory sort.
The Left-Prefix Rule & Covering Indexes
When creating a composite index on multiple columns like (A, B, C), the database sorts keys first by column A, then by column B within matching A values, and finally by column C. Therefore, the index can accelerate queries filtering on (A), on (A, B), or on (A, B, C). However, the index CANNOT be used efficiently for queries filtering only on (B) or (C) without column A. A Covering Index includes all columns requested by the SELECT query, allowing the database engine to retrieve the required data entirely from the index tree (an Index-Only Scan) without fetching the physical table heap pages.
-- High-Performance SQL with Window Functions & CTEs
WITH RankedSalaries AS (
SELECT
id,
department_id,
salary,
DENSE_RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) as rank
FROM employees
)
SELECT department_id, id, salary
FROM RankedSalaries
WHERE rank <= 3;
Calculates the top 3 highest-earning employees in every department in a single query pass using window ranking.
Build It: Design an Auditable E-Commerce Checkout Schema with Pessimistic Locking
Write migration scripts and SQL queries ensuring inventory cannot be oversold under concurrent purchase requests.
Project Deliverables
- DDL tables for products, inventory, orders, and order_items with proper foreign keys and constraints.
- Atomic checkout transaction with SELECT ... FOR UPDATE on inventory rows.
- EXPLAIN plan demonstrating index usage and sub-millisecond execution.
Acceptance Criteria
- No inventory counts drop below zero even under simulated concurrent transactions
- Composite indexes created according to high-frequency query access patterns
- Idempotency key stored on orders table to prevent double-charges
Next Steps & Related Learning
This interactive lesson is part of the Backend Developer curriculum. Continue exploring or try another interactive lesson: