🗄️ Database Internals: Storage Engines, B+Trees & LSM-Trees
1️⃣ Database Anatomy: Query Engine vs Storage Engine
Definition: Relational aur NoSQL databases do primary subsystems me split hote hain: Query Engine (jo SQL query ko parse, optimize aur execute plan me convert karta hai) aur Storage Engine (jo raw bytes ko persistent disk blocks aur memory buffers me manipulate karta hai).
| Subsystem | Core Components | Primary Responsibility |
|---|---|---|
| Transport & Query Layer | Parser, Lexer, Query Planner, Cost-Based Optimizer (CBO) | SQL syntax validate karna, execution cost calculate karna aur optimized relational algebra tree produce karna. |
| Storage Engine | Buffer Pool Manager, Lock Manager, WAL Logger, Page Storage Layer | Disk blocks read/write karna, transactional atomicity enforce karna aur crash recovery guarantee karna. |
2️⃣ Disk Page Layouts & Slotted-Page Architecture
Databases disk par raw rows nahi likhte; data fixed-size Pages / Blocks (typically 4 KB - 16 KB) me divide hota hai. Variable-length records efficiently store karne ke liye Slotted-Page Architecture use hota hai:
+-----------------------------------------------------------------------+
| PAGE HEADER |
| Page LSN | Free Space Pointer | Slot Count | Checksum |
+-----------------------------------------------------------------------+
| SLOT DIRECTORY (Grows Downwards ↓) |
| [Slot 0: Offset 4020, Len 60] | [Slot 1: Offset 3940, Len 80] |
+-----------------------------------------------------------------------+
| ... FREE SPACE ... |
+-----------------------------------------------------------------------+
| TUPLE HEAP STORAGE (Grows Upwards ↑) |
| Tuple 1 [len 80] |
| Tuple 0 [len 60] |
+-----------------------------------------------------------------------+
Record Identifier (RID / TID): Kisi bhi row ka physical disk address
RID = (Page_ID, Slot_Index) hota hai. Row update hone par agar length badal bhi jaye, toh sirf slot offset update hota hai; primary keys ya indexes ko re-point nahi karna padta.
3️⃣ Buffer Pool Management & Eviction
Disk I/O DRAM memory ke comparison me $1000\times$ slow hota hai. Database ek internal cache maintain karta hai jise Buffer Pool kehte hain:
- Frame Table: Track karta hai ki kaunsa disk page kis physical RAM frame me loaded hai.
- Dirty Pages: Wo pages jo memory me modify ho chuke hain par abhi disk par flush nahi huye.
- Pinning: Jab koi query page read kar rahi hoti hai, uska pin count $>0$ ho jata hai taaki eviction engine use RAM se swap out na kare.
- Clock Sweep & 2Q / LRU-K: Sequential scan loops (e.g.
SELECT *) se poora buffer pool pollute hone se rokne ke liye frequency-based replacement policies.
4️⃣ Write-Ahead Logging (WAL) & ARIES Protocol
Database updates perform karte samay disk par direct dirty pages flush karna ultra-slow random I/O cause karta hai. Isliye Write-Ahead Logging (WAL) enforce kiya jata hai:
The WAL Invariant: Kisi bhi database page ko disk par persist karne se pehle, us modification ka sequential append-only log record (WAL) disk par strictly
fsync() hona mandatory hai.
| ARIES Recovery Phase | Action on Restart after Crash |
|---|---|
| 1. Analysis Phase | Latest Checkpoint se aage WAL scan karke determine karta hai ki crash ke waqt kaunse dirty pages aur active uncommitted transactions the. |
| 2. Redo Phase | Crash se pehle ke committed transactions ke saare operations ko sequentially replay karta hai (Repeat history to restore consistency). |
| 3. Undo Phase | Jo transactions crash ke samay uncommitted reh gaye the, unke changes ko reverse (rollback) karta hai compensating log records (CLRs) emit karke. |
5️⃣ B+Trees: Read-Optimized In-Place Storage
Modern Relational Databases (PostgreSQL, MySQL InnoDB, Oracle) ka standard index format B+Tree hota hai:
| B+Tree Component | Storage Characteristics | Lookup Complexity |
|---|---|---|
| Internal Routing Nodes | Sirf search key delimiters aur child page pointers store karte hain (High fanout, $100\text{--}1000$ pointers per page). | $O(\log_B N)$ disk page access |
| Leaf Nodes | Actual data rows ya primary key pointers store karte hain; horizontally bi-directional linked list se connected rehte hain. | Range scan: $O(\log_B N + \frac{K}{\text{Page\_Capacity}})$ |
Live Storage Engine Simulator: B+Tree vs LSM-Tree
[Storage Engine Engine]: Ready. InnoDB Buffer Pool: 128MB | RocksDB LSM Engine: Online. Select an operation above...
6️⃣ LSM-Trees: Write-Optimized Storage Architecture
Log-Structured Merge-Trees (RocksDB, Cassandra, ScyllaDB, LevelDB) random disk writes ko eliminate karke 100% Sequential Append-Only Writes me convert kar dete hain:
[Write Request: Key=401, Val="Senior SDE"]
|
+---> Step 1: Append to WAL on Disk (Sequential fsync for durability)
|
+---> Step 2: Insert into In-Memory Skiplist (MemTable) [O(log N)]
|
+---> (When MemTable reaches 64MB)
|
v
Flush to Immutable SSTable on Disk (Sorted String Table: Level 0)
|
v
Background Leveled Compaction Merges L0 → L1 → L2| Criteria | B+Tree Engine (InnoDB) | LSM-Tree Engine (RocksDB) |
|---|---|---|
| Write Optimization | Lower (Random Page I/O + Page Splits). | Extremely High (Sequential memory writes + batch flush). |
| Read Optimization | Extremely High (Predictable single point lookups via leaf pages). | Lower (Point lookup may search MemTable + multiple SSTable files via Bloom Filters). |
| Space Amplification | High (Fragmented empty page space ~33%). | Very Low (SSTables are densely packed and heavily compressed). |
7️⃣ Multi-Version Concurrency Control (MVCC)
"Readers do not block writers, and writers do not block readers."
MVCC Tuple Header Fields (PostgreSQL Architecture):
•
•
• Snapshot Isolation: Jab koi read transaction start hota hai, use ek
• VACUUM Engine: Dead tuples (jinhe ab koi active transaction read nahi kar sakta) ko identify karke physical page storage reclaim karta hai.
•
xmin: Row create karne wale transaction ka 32-bit transaction ID (XID).•
xmax: Row delete ya update karne wale transaction ka XID (Default 0 for active un-deleted rows).• Snapshot Isolation: Jab koi read transaction start hota hai, use ek
Snapshot = (XMIN, XMAX, [active_xid_list]) assign hota hai. Query sirf un rows ko read karti hai jo uske snapshot time se pehle commit ho chuki thi.• VACUUM Engine: Dead tuples (jinhe ab koi active transaction read nahi kar sakta) ko identify karke physical page storage reclaim karta hai.
