1. Concept Introduction
The Separation of Engine Layers
In modern Database Management Systems (DBMS), the Query Processing Engine is strictly decoupled from the Storage Engine.
+-------------------------------------------------------------------------+
| QUERY PROCESSING ENGINE |
| +---------------------+ +---------------------+ +-----------------+ |
| | SQL Parser & Lexer | | Query Optimizer | | Execution Engine| |
| | (Abstract Syntax) | | (Cost-Based Engine) | | (Volcano Model) | |
| +---------------------+ +---------------------+ +-----------------+ |
+-------------------------------------------------------------------------+
│
▼ Storage Engine API / SPI
+-------------------------------------------------------------------------+
| STORAGE ENGINE |
| +---------------------+ +---------------------+ +-----------------+ |
| | Buffer Pool Manager | | Concurrency Control | | Logging & WAL | |
| | (Frame Allocation) | | (MVCC / Locking) | | (ARIES Recovery)| |
| +---------------------+ +---------------------+ +-----------------+ |
+-------------------------------------------------------------------------+2. Theory & Low-Level Internals
A. Slotted Page Physical Architecture
+-------------------------------------------------------------------------+
| SLOTTED PAGE ARCHITECTURE |
+-------------------------------------------------------------------------+
| PAGE HEADER |
| [ LSN (8B) | Flags (2B) | Lower Offset (2B) | Upper Offset (2B) | ... ] |
+-------------------------------------------------------------------------+
| ITEM POINTER ARRAY (Slots growing FORWARD ──>) |
| [ Slot 0: Offset 8100, Len 90 ] | [ Slot 1: Offset 7980, Len 120 ] ... |
+-------------------------------------------------------------------------+
| <── FREE SPACE REGION ──> |
+-------------------------------------------------------------------------+
| TUPLE STORAGE AREA (Tuples written BACKWARD from page boundary <──) |
| ... [ Tuple 1 Payload ] [ Tuple 0 Payload (Offset 8100, 90 Bytes) ] |
+-------------------------------------------------------------------------+B. B+ Tree Fan-Out Proof
For page size $P = 16\text{ KB}$, key size $K = 8\text{ B}$, child pointer $V = 6\text{ B}$, and tuple size $T = 200\text{ B}$:
Internal Fan-out ($B$) = 1,170 keys/page • Leaf Capacity ($C$) = 57 tuples/page
Total Records at Height 3: $N = (1,170)^2 \times 57 \approx \mathbf{78,027,300\text{ records}}$.
C. MVCC Physical Versioning: PostgreSQL vs. MySQL InnoDB
| Engine | Physical UPDATE Strategy | Dead Version Cleanup | Secondary Index Impact |
|---|---|---|---|
| PostgreSQL | Appends new tuple copy into Heap page (`xmin`/`xmax`). | Requires Autovacuum worker threads. | Updates ALL secondary indexes (unless HOT). |
| MySQL InnoDB | Overwrites row in-place in Clustered Index; writes diff to Undo Log. | Purge threads clean Undo Log segments. | No secondary index updates if indexed column un-changed. |
3. Real Production Architecture Example
High-Throughput E-Commerce Order Ledger handling 100,000 write TPS with PostgreSQL Range Partitioning, PgBouncer pooler, and Partial Covering Indexes.
4. Code Examples
A. Production Pattern: SARGable Range Queries & Partial Covering Indexes
-- SARGable Range Constraint for B+ Tree Root-to-Leaf Lookup
SELECT order_id, customer_id, order_total
FROM orders
WHERE created_at >= '2026-08-01 00:00:00'
AND created_at < '2026-08-02 00:00:00';
-- Partial Index for Skewed Unpaid Status (95% Disk Reduction)
CREATE INDEX idx_unpaid_orders ON orders (customer_id, created_at)
WHERE status = 'UNPAID';
-- Index-Only Scan via Covering Index
CREATE INDEX idx_orders_covering ON orders (customer_id, created_at)
INCLUDE (order_total);B. C Engine Slotted Page Simulation
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#define PAGE_SIZE 4096
typedef struct { uint16_t offset; uint16_t length; } Slot;
typedef struct { uint64_t lsn; uint16_t slot_count; uint16_t lower; uint16_t upper; } PageHeader;
typedef struct { uint8_t data[PAGE_SIZE]; } SlottedPage;
void init_page(SlottedPage *page) {
PageHeader *header = (PageHeader *)page->data;
header->lsn = 1001; header->slot_count = 0;
header->lower = sizeof(PageHeader); header->upper = PAGE_SIZE;
}5. Tiered Interview Questions
Q1: Why do DBMS engines use B+ Trees instead of Binary Search Trees (BST)?
Ideal Answer: 1. Disk Block Alignment: B+ Tree nodes align to 8KB/16KB disk pages, achieving fan-outs of 1,000+ and tree heights $\le 3$. BSTs have fan-out 2, requiring 27+ random disk reads for 100M rows. 2. Sequential Range Scans: B+ Tree leaf nodes are doubly linked.
Q2: Compare PostgreSQL In-Heap MVCC vs InnoDB Undo Log. How to eliminate bloat at 50k updates/sec?
Ideal Answer: Postgres appends new tuple versions into heap pages, causing dead tuple bloat if long transactions hold open Read Views. Solved via **HOT Optimization** (Heap-Only Tuples with `fillfactor=70` without updating secondary indexed columns).
6. Production Debugging Scenario
Symptom: Query Latency Spike 14,201ms to 0.112ms
Root Cause: Single column index forced 104,920 buffer page reads to filter status='PENDING' and sort by transaction_time.
Resolution: Created Composite Partial Covering Index `(merchant_id, status, transaction_time DESC)`. Execution dropped to 0.112ms ($126,000\times$ speedup)!
📜 Official Developer Certification & Cloud Hosting
Validate your software engineering skills with official developer certifications and high-performance cloud hosting.