SQL SQL In Depth
0%
Guided SQL & Engine Coding Lab

B+Tree Page Simulator & Automated Workload Index Advisor

An in-memory B+Tree index simulator with doubly linked leaf sibling pointers for range scans and an automated workload index advisor applying the Equality -> Sort -> Range + INCLUDE covering rule.

~25 min Intermediate Lessons: Hands-On Build: B+Tree Page Simulator & Automated Workload Index Advisor, Why Indexes Work: Full Table Scan O(N) vs Index Seek O(log_B N) I/O Physics, B-Tree vs B+Tree Internal Anatomy: High Fanout, Routing Keys & Leaf Links, Clustered Indexes (InnoDB / WITHOUT ROWID) vs Heap + Secondary Index (Postgres), Composite Indexes (a, b, c): Leftmost Prefix Rule & Equality-Before-Range, Covering Indexes, INCLUDE Columns & Index-Only Scans (Visibility Map)
Guided SQL & Storage Engine Lab 0/3 Steps Completed

Execute & Verify SQL & Storage Engine Invariants in the Browser SQL Studio

Complete 3 progressive relational steps with guided hints in PostgreSQL 18 WASM, SQLite 3 & Step-by-Step Relational Table Visualizer against automated result-set and query-plan assertions — zero local setup required.

01 Phase 1 · Base Relation & SARGable Predicate
Base Relation Scan & SARGable Filter (ecommerce)
Establish the base relation scan in ecommerce for Hands-On Build: B+Tree Page Simulator & Automated Workload Index Advisor with a SARGable predicate and explicit Three-Valued Logic NULL handling.
4 SQL assertions
02 Phase 2 · Relational Join, Aggregation & 3VL Guard
Relational Join, Grouping & NULL-Safe Aggregation
Combine normalized tables via explicit JOIN conditions and fold group buckets or window partitions without losing NULL boundary rows.
4 SQL assertions
03 Phase 3 · Production Query & Plan Verification
Production Query & Execution Plan Verification (Hands-On Build: B+Tree Page Simulator & Automated Workload Index Advisor)
Verify final column projections, ordering, and physical B+Tree access paths via EXPLAIN QUERY PLAN and automated relational assertions.
4 SQL assertions

Architectural Overview

An in-memory B+Tree index simulator with doubly linked leaf sibling pointers for range scans and an automated workload index advisor applying the Equality -> Sort -> Range + INCLUDE covering rule.

In production relational and analytical database systems—spanning PostgreSQL, SQLite, MySQL/InnoDB, and DuckDB—understanding how query clauses, schema constraints, index structures, and storage engines execute under the hood separates surface-level query authors from staff-level database engineers. This capstone build lab guides you through implementing B+Tree Page Simulator & Automated Workload Index Advisor from first principles with deterministic self-test invariants.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: B+Tree Sorted Leaf Insertion & Midpoint Split

  • Core Database Concept: Splitting Overflowing Leaf Pages and Linking Sibling Pointers
  • Target Module: index.js (BPlusTreeIndexAdvisor.insertKey)
  • Engineering Specification: Implement insertKey(key, rowId) to insert into the appropriate sorted leaf page and split any leaf exceeding this.maxKeys, linking leftLeaf.next = rightLeaf.
  • Implementation Hint: Insert { key, rowId } in sorted order; when leaf exceeds maxKeys, split at mid and link left.next = right.
  • Verification Invariant: deterministic assertion verified in test.js step 1

Step 2: Leaf-Chain Range Scan Traversal

  • Core Database Concept: Point-Seek to Lower Bound Followed by Sequential Leaf Pointer Walk
  • Target Module: index.js (BPlusTreeIndexAdvisor.rangeScan)
  • Engineering Specification: Implement rangeScan(minKey, maxKey) to find the starting leaf and traverse sibling next pointers, returning { rowIds, pagesRead }.
  • Implementation Hint: Locate the first leaf capable of holding minKey, then walk leaf.next until key > maxKey.
  • Verification Invariant: deterministic assertion verified in test.js step 2

Step 3: Leftmost Prefix Utilization Analyzer

  • Core Database Concept: Why Range Predicates Stop Subsequent Index Key Columns From Narrowing the Scan
  • Target Module: index.js (BPlusTreeIndexAdvisor.matchedPrefixCount)
  • Engineering Specification: Implement matchedPrefixCount(indexCols, equalityCols, rangeCols) to compute how many leading columns of indexCols can be used as B+Tree search bounds.
  • Implementation Hint: Walk indexCols in order: increment count on equality; if range col encountered, increment once and break.
  • Verification Invariant: deterministic assertion verified in test.js step 3

Step 4: Automated Equality -> Sort -> Range + INCLUDE Index Advisor

  • Core Database Concept: Synthesizing an Optimal Covering Index for a Parameterized Query Shape
  • Target Module: index.js (BPlusTreeIndexAdvisor.recommendIndex)
  • Engineering Specification: Implement recommendIndex({ table, equalityCols, rangeCols, orderCols, selectCols }) to synthesize { keyCols, includeCols, ddl } following the ESR + covering index design pattern.
  • Implementation Hint: Order equalityCols by selectivity, then orderCols (if no range before sort), then rangeCols, and put remaining selectCols in includeCols.
  • Verification Invariant: deterministic assertion verified in test.js step 4

Relational & Storage Engine Guarantees

  • Curriculum Domain: B+Trees & Indexing Architecture
  • Difficulty & Time Budget: Advanced (~45 minutes)
  • Key Architectural Highlights:
    • B+Tree leaf node splits with upward separator key promotion and sibling leaf pointer linking
    • O(log_B N + K) range scan traversal walking leaf next pointers without re-descending internal nodes
    • Automated composite index synthesis ordering Equality -> ORDER BY -> Range columns with INCLUDE payload
  • Core Primitives & Tags: B+Tree, Composite Index, ESR Rule, Covering Index, Range Scan

Related Curriculum Units

Production Database Context & Verification

This from-scratch relational engine component is engineered with zero external dependencies and deterministic verification harnesses. Every internal database invariant—from three-valued logic (TRUE / FALSE / UNKNOWN), referential integrity, and fan-out-free join pre-aggregation to B+Tree page splits, MVCC snapshot visibility (xmin / xmax), slotted-page compaction, and ARIES write-ahead log crash recovery—is asserted directly in test.js. Use the interactive browser workbench above to complete the 4 guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.