PLAN-101 Career OS
Intermediate 55 Minutes

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:

View Full Backend Developer → Arrays, Contiguous Memory & Hash Tables → JavaScript Asynchronous Execution & V8 Event Loop → Semantic HTML, Accessible Forms & Document Structure → Python Functions, Dictionaries and Reliable Data Processing → SQL Joins, Missing Rows and Query Correctness → React State, Events and Derived UI → Designing a Task API: HTTP Methods, Errors and Validation → Sliding Window: From Quadratic Loops to a Linear Scan → Responsive CSS Layout: Flexbox, Grid and Fluid Constraints → TypeScript Union Types and Runtime Narrowing → Docker Images, Containers and Reproducible Builds → Git Branches, Pull Requests and Conflict Resolution → Graph Traversal: BFS, DFS and Visited Sets → AWS IAM: Least Privilege and Secure Cloud Access → API Pagination, Error Contracts and Safe Retries →