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.

~45 min Advanced 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 Algorithm Coding Lab 0/4 Steps Completed

Code & Verify SQL & Storage Engine Invariants in the Browser Workbench

Complete 4 progressive algorithmic steps with guided hints in C++20 (WebAssembly), TypeScript, or JavaScript against automated unit test assertions — zero local setup required.

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.