Indexing an orders table with 500 million records. Creating a Composite Index ON orders(user_id, status, created_at) allows fetching a user's pending orders sorted by date via an Index Range Scan in 0.4ms while leveraging the Leftmost Prefix rule.
-- Creating Clustered and Composite Secondary Indexes -- In PostgreSQL, Primary Key automatically creates a Unique B-Tree index CREATE TABLE orders ( order_id BIGSERIAL PRIMARY KEY, user_id INT NOT NULL, status VARCHAR(20) NOT NULL, total_amount NUMERIC(12, 2) NOT NULL, created_at TIMESTAMPTZ NOT NULL DEFAULT CURRENT_TIMESTAMP ); -- Composite Index supporting queries on (user_id), (user_id, status), and (user_id, status, created_at) CREATE INDEX idx_orders_user_status_date ON orders(user_id, status, created_at); -- Covering Index: Includes total_amount in index payload to enable Index-Only Scan (no heap table access!) CREATE INDEX idx_orders_covering ON orders(user_id, status) INCLUDE (total_amount); -- Inspecting Query Execution Plan with EXPLAIN ANALYZE EXPLAIN ANALYZE SELECT user_id, status, total_amount FROM orders WHERE user_id = 42890 AND status = 'COMPLETED';
Visual representation of control loops, memory layout, and execution flow for Database Indexing, B+ Trees & Hashing.
Databases organize disk storage in fixed-size Blocks / Pages (e.g., 4KB, 8KB in Postgres, 16KB in InnoDB). A Slotted Page contains a Page Header, a Slot Array of offsets growing downward, and variable-length Tuple records growing upward from the bottom of the page. Tuples are addressed by Record ID (RID / TID = PageID + SlotNumber).
1. Higher Fan-Out: In a standard B-Tree, internal nodes store data records alongside keys. In a B+ Tree, internal nodes store ONLY search keys and child disk pointers. A 16KB page can fit 1,000+ key pointers (fan-out M = 1000). A 3-level B+ Tree can index 1,000^3 = 1 Billion rows with only 3 disk seeks! 2. Sequential Range Scans: B+ Tree leaf nodes form a continuous doubly-linked list. Executing `WHERE date BETWEEN x AND y` traverses the tree once to find the start key, then scans leaf nodes sequentially without re-traversing parent nodes.
Clustered Index: Determines the physical sorted order of rows on disk. Leaf nodes contain the ACTUAL table row data tuples. There can be ONLY ONE Clustered Index per table (usually Primary Key). Secondary (Non-Clustered) Index: Stored in a separate structure. Leaf nodes contain the indexed key value + a Pointer to the data. In PostgreSQL, the pointer is a TID (PageID, SlotID); in MySQL InnoDB, the pointer is the Clustered Primary Key value (triggering a secondary index lookup + clustered index traversal / "bookmark lookup").
A composite index on (A, B, C) is sorted primarily by A, then by B, then by C. - Query with WHERE A = 1 -> Uses Index. - Query with WHERE A = 1 AND B = 2 -> Uses Index. - Query with WHERE A = 1 AND B = 2 AND C = 3 -> Uses Index. - Query with WHERE B = 2 (missing A) -> CANNOT use index effectively (violates Leftmost Prefix Rule)! Covering Index: If an index contains all columns requested by the SELECT query, the engine performs an Index-Only Scan without accessing the heap table pages.
| Feature / Dimension | B+ Tree Index | Hash Index |
|---|---|---|
| Point Lookups (WHERE id = 5) | O(log_M N) tree traversal (typically 2–4 disk seeks) | O(1) average time direct bucket lookup |
| Range Queries (WHERE age > 21) | EXCELLENT: Efficient sequential traversal via doubly-linked leaf nodes | IMPOSSIBLE: Hash functions scatter contiguous values across random buckets |
| Sorting & Ordering (ORDER BY) | Data is maintained in sorted key order; eliminates in-memory sort | Does not preserve sorting; requires full in-memory sorting |
Detailed answers, interviewer pro tips, key takeaway summaries, and code examples formulated for technical rounds.
✅ Correction: Indexes degrade INSERT, UPDATE, and DELETE performance and consume buffer pool RAM. Only index columns that appear frequently in WHERE filters, JOIN predicates, and ORDER BY clauses.
✅ Correction: Applying a function prevents the engine from utilizing the B+ Tree index, causing a full table scan. Rewrite as a range query: `WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01'` or create a functional/expression index.
Self-balancing on-disk data structures for rapid sub-millisecond query execution.