Unit 2: Storage Engine Internals, 8KB Slotted Pages & Index Architectures 45 mins study timeADVANCED

DBA Masterclass: 8KB Slotted Pages, WAL Durability & B+ Tree vs Hash Indexes

Production DBA blueprint of database storage engines: 8KB disk page binary layouts, Item Pointer arrays, Write-Ahead Logging (WAL), and why B+ Trees power relational engines over Hash indexes.

Verified: Faculty Peer Review Board

Learning Objectives

•Dissect the binary internal structure of an 8KB slotted database page.
•Explain how Write-Ahead Logging (WAL) and checkpointing ensure zero data loss during power outages.
•Calculate the depth and fanout of a B+ Tree index given page size and key width.
•Demonstrate why B+ Tree indexes can satisfy ORDER BY clauses without in-memory sorting.

Essential Prerequisites

•Relational tables and PRIMARY KEY constraints
•Binary tree concepts and disk block I/O

Layer 1: Intuition & Why It Matters

The Core Mental Model

“Think of a B+ Tree like a gigantic library directory. The lobby computer (Root) tells you which floor (Internal Node) has books starting with 'D'. That floor tells you which aisle (Leaf Page) to walk to. Once you reach the aisle, the books are shelved side-by-side in exact alphabetical order, so you can walk down the aisle picking up 50 books in a row (Range Scan).”

Why This Exists

Junior developers add indexes blindly when a query is slow. A Senior Database Administrator knows that an unneeded index penalizes every INSERT, UPDATE, and DELETE by forcing extra disk page splits and WAL generation. Mastering page layout and B+ Trees is what separates a novice from an infrastructure DBA.

Beginner Foundation

If you have 10 million rows and ask for one user, looking at every row one by one (Sequential Scan) takes 10 seconds. An index is like an alphabetized phonebook: with just 3 quick flips, the database finds the exact page and row in 1 millisecond.

Micro Concepts Decomposition

MICRO CONCEPT 1Canonical Object

The 8KB Slotted Page Architecture

Relational storage engines (like PostgreSQL) store data in fixed 8KB pages. The Slotted Page design splits each page: Page Header at the top (24 bytes), followed by Item Pointers (4 bytes each) growing downwards, a Free Space gap in the middle, and actual row tuple payloads growing upwards from the bottom of the page.

Key Takeaway: Item pointers provide stable Tuple Identifiers (TID: block_num, offset_num) even when rows are defragmented within the page.

MICRO CONCEPT 2Canonical Object

Write-Ahead Logging (WAL) & ARIES Crash Recovery

Random I/O writes to 8KB data pages across disk are extremely slow. Under WAL, changes are appended sequentially to a high-speed write-ahead log buffer and flushed via `fsync` BEFORE dirty data pages are written to tablespace disk. On power crash, the ARIES algorithm executes REDO then UNDO to restore state.

Key Takeaway: WAL transforms random disk writes into high-speed sequential writes while guaranteeing ACID Durability.

MICRO CONCEPT 3Canonical Object

B+ Tree Index Anatomy: Root, Internal Nodes & Leaf Chains

A B+ Tree is a self-balancing search tree with high fanout (100 to 300 children per node). All user data pointers reside exclusively in Leaf Pages. Internal pages hold only routing keys and downlink block addresses. Crucially, all Leaf Pages are linked as a bi-directional linked list, enabling O(log N) + K range scans.

Key Takeaway: High fanout ensures B+ Tree depth rarely exceeds 3 or 4 levels even for 100,000,000 rows (only 3-4 disk block reads!).

MICRO CONCEPT 4Canonical Object

B+ Tree vs Hash Index: The Production DBA Decision

Hash indexes offer O(1) equality lookups (`WHERE id = 500`) but CANNOT perform range queries (`<, >, BETWEEN`), prefix searches (`LIKE 'abc%'`), or ordering (`ORDER BY`). B+ Trees support equality, range scans, sorting, and min/max operations natively in O(log N).

Key Takeaway: Use B+ Tree (PostgreSQL default) for 99% of workloads. Reserve Hash indexes strictly for massive exact-match string hashes.

Layer 3 & 4: Formal Specification & Mechanism

Hardware State Machine Architecture

B+ Tree Fanout & Depth Calculation: Page size = 8192 bytes. Header = 24 bytes. Usable space = 8168 bytes. Key size (BIGINT 8 bytes) + Downlink Pointer (6 bytes) + Item Pointer (4 bytes) = 18 bytes per routing entry. Fanout $F = \lfloor 8168 / 18 \rfloor \approx 453$. Capacity at depth $D$: - Depth 1 (Root only): 453 rows. - Depth 2: $453^2 \approx 205,000$ rows. - Depth 3: $453^3 \approx 93,000,000$ rows. - Depth 4: $453^4 \approx 42,000,000,000$ rows! With depth 3, any record among 93 million rows is retrieved in at most 3 page reads.

Step-by-Step Slotted Page Ingestion: 1. Insert new row tuple T (size 120 bytes). 2. Allocate 4-byte Item Pointer at next available slot from top: `(offset=8072, length=120)`. 3. Write tuple bytes at bottom offset 8072..8191. 4. Shrink Free Space gap by `4 + 120 = 124` bytes. 5. If row is updated to smaller size, space remains available. If page overflows, B+ Tree triggers a Page Split.

Layer 7: Interactive Laboratory

Interactive Simulator

SQL • LABDatabase 8KB Slotted Page Physical Storage Lab

Launch Fullscreen Lab

SQL • RELATIONAL ALGEBRACartesian Product & Key Matching

Visual SQL Relational JOIN Laboratory

Executing SQL Query:

SELECT s.id, s.name, s.major, e.course, e.grade
FROM students s
INNER JOIN enrollments e
  ON s.id = e.student_id;

Left Table: students (s)

id (PK)	name	major
1	Aarav	CS
2	Diya	AI
3	Kabir	Data
4	Riya	Cyber

Right Table: enrollments (e)

student_id (FK)	course	grade
1	CS301	A
2	CS301	B+
2	CS304	A+
5	CS305	A

Relational Result Set (3 rows returned)Matched by s.id = e.student_id

s.id	s.name	s.major	e.course	e.grade
1	Aarav	CS	CS301	A
2	Diya	AI	CS301	B+
2	Diya	AI	CS304	A+

Relational Join Invariant:

In INNER JOIN: Only rows with matching keys in BOTH tables are preserved. Any unmatched student (like Kabir or Riya) or unmatched enrollment (like Student 5) is completely omitted.

Layer 5: Step-by-Step Worked Numerical Example

End-to-End Execution Trace

Problem: A query `SELECT * FROM orders WHERE customer_id = 42 ORDER BY order_date DESC LIMIT 5` runs slowly. DBA Analysis: - Table has an index on `(customer_id)`. - Engine uses Index Scan to fetch all 50,000 rows for customer 42, then runs an expensive Sort operation in memory (Sort Method: external merge Disk)! DBA Solution: Create a Composite Index: `CREATE INDEX idx_orders_cust_date ON orders (customer_id, order_date DESC)`. Result: The B+ Tree stores customer 42's rows already pre-sorted by `order_date DESC`. Engine reads top 5 leaf entries and halts immediately. Execution time collapses from 320ms to 0.4ms!

Layer 6: Active Runtime CodeLab

Step-by-Step Code Execution (SQL)

AURXON Sandbox

AURXON Digital Engine

Font

main.pyGlacier Light

Ln 1 • Python 3.12

-- Senior DBA Diagnostic Script: Inspecting Index Sizes, Bloat & Page Layouts
-- 1. Identify Index Sizes vs Table Sizes
SELECT 
    schemaname,
    tablename,
    pg_size_pretty(pg_relation_size(quote_ident(schemaname) || '.' || quote_ident(tablename))) AS table_size,
    pg_size_pretty(pg_total_relation_size(quote_ident(schemaname) || '.' || quote_ident(tablename)) - 
                   pg_relation_size(quote_ident(schemaname) || '.' || quote_ident(tablename))) AS index_size
FROM pg_tables
WHERE schemaname = 'public'
ORDER BY pg_total_relation_size(quote_ident(schemaname) || '.' || quote_ident(tablename)) DESC;
 
-- 2. Inspect Index Usage: Finding Unused Indexes Wasting Write IO
SELECT 
    schemaname,
    relname AS table_name,
    indexrelname AS index_name,
    idx_scan AS number_of_scans,
    pg_size_pretty(pg_relation_size(indexrelid)) AS wasted_index_size
FROM pg_stat_user_indexes
WHERE idx_scan = 0
ORDER BY pg_relation_size(indexrelid) DESC;

962 chars • 23 lines • Ln 1UTF-8 • 4 Spaces

Interactive Terminal Shell

Sandbox Terminal Ready

Click Run Code or press Ctrl+Enter to compile and execute.

⚡ AURXON Bitstream Runtime v4.8IDRAS Academic Virtual Node

Common Student Pitfalls & Mistakes

Where Students Lose Marks

❌ Mistake: Creating individual single-column indexes on every column in a table.

✓ Correct Understanding: Independent single-column indexes cannot satisfy multi-column filters efficiently and multiply write overhead. Create carefully ordered Composite Indexes matching actual query WHERE and ORDER BY clauses.

Layer 8: Practice & Knowledge Verification

Active Assessment Quiz

No Practice Questions Configured

Questions for this topic are currently undergoing faculty review.

Academic Evaluation Preparation

Viva Examination & University Scoring Strategy

Standard Viva Examination Questions

Q1: Why does Write-Ahead Logging (WAL) flush log records before writing dirty table pages to disk?

Answer: To guarantee Atomicity and Durability (the A and D of ACID). If the database crashes after writing a dirty page but before recording the transaction in WAL, the change cannot be rolled back or verified, leading to silent data corruption.

How to Write High-Scoring University Exam Answers

Draw the internal memory layout of an 8KB Slotted Page. Derive the B+ Tree depth formula given fanout and row count. Contrast B+ Tree and Hash indexing across 5 performance criteria. Explain the ARIES recovery protocol (Analysis, REDO, UNDO).