B+ Tree Engines: On-Disk Storage in C++

Learning Goal: Designing and implementing an on-disk B+ Tree storage engine for a custom relational database in C++. You will learn how memory layout, physical hardware constraints, raw serialization, binary page organization (like slotted pages), and active buffer pool management interact to build a high-performance, disk-backed transaction-ready index from scratch.

Prerequisites: High-school algebra, basic programming concepts (variables, loops, arrays), and a passion for low-level systems programming. No prior database systems knowledge is required.
Estimated Total Study Time: 65 Hours

Course Map

This map outlines the recommended learning order and structural dependencies, revised to introduce conceptual design patterns before physical hardware layout.

Module 1: C++ Programming & Memory Management Foundations

This module builds the base systems programming knowledge required to write robust C++ code. You will master physical memory representation, pointer mechanics, references, and the execution differences between stack-allocated objects and heap-allocated objects.

Module 2: Data Structures: BST to B+ Trees

Before dealing with on-disk byte formats, you must understand the mathematical and logical structures of hierarchical index algorithms. This module moves from simple Binary Search Trees to B-Trees and explains why B+ Trees are uniquely suited for persistent database indexes.

Module 3: Disk I/O & Low-Level Byte Representation

To write a real database, you cannot rely on high-level serialization libraries. You must handle byte-level representation, address hardware write constraints, serialize structs into raw binary buffers, and write those buffers directly to physical files.

⚠️ Independent Gap Coverage: Memory Alignment & Struct Packing in C++

To successfully write a C++ struct to disk, you must prevent the C++ compiler from inserting arbitrary packing bytes between fields.

Compiler Directives: Use #pragma pack(push, 1) before your struct definition and #pragma pack(pop) after it. This forces the compiler to align all fields on 1-byte boundaries, guaranteeing that the file representation on disk matches the exact byte offset in memory.

Casting Example:

#pragma pack(push, 1)
struct PageHeader {
    uint32_t page_id;
    uint16_t free_space_pointer;
    uint16_t slot_count;
};
#pragma pack(pop)

// Serializing raw struct to byte buffer
char block[4096];
PageHeader header{1024, 4096, 0};
std::memcpy(block, &header, sizeof(PageHeader)); // Safe, dense copy

Module 4: B+ Tree Implementation and On-Disk Node Layout

This module bridges the gap between memory and physical storage. You will learn to design real binary page layouts (including Slotted Pages) and implement the algorithmic logic of leaf/internal node search, insertion, and split behaviors.

⚠️ Independent Gap Coverage: Writing an On-Disk B+ Tree Node Layout in C++

To implement this in C++, you must avoid using high-level dynamic arrays (like std::vector) inside the code that maps to raw disk blocks. A disk page is a fixed-size byte array of 4096 bytes. You must use reinterpret_cast to cast raw page pointers to typed structures.

class BPlusNode { public: static constexpr size_t PAGE_SIZE = 4096;

// Explicit byte-level layout using a C++ class with a backing raw array
struct Header {
    bool is_leaf;
    uint16_t num_keys;
    uint32_t next_page_id; // For leaf node linking
};

// Cast a raw 4KB memory frame directly to access the fields
static Header* GetHeader(char* page_data) {
    return reinterpret_cast<Header*>(page_data);
}

static int32_t* GetKeys(char* page_data) {
    // Keys start immediately after the Header
    return reinterpret_cast<int32_t*>(page_data + sizeof(Header));
}

static uint32_t* GetChildPointers(char* page_data) {
    // Child pointers (Page IDs) start after the maximum possible keys array
    // (Assuming max keys is calculated based on remaining space in 4KB)
    size_t offset = sizeof(Header) + (sizeof(int32_t) * 200); // e.g. Max 200 keys
    return reinterpret_cast<uint32_t*>(page_data + offset);
}

};

Module 5: Buffer Pool Management and Storage Engine Integration

This final module ties everything together. You will build a Buffer Pool Manager (BPM) that caches disk pages in memory, handles page eviction via an LRU cache, maintains dirty flags, and orchestrates atomic reads and writes to form a complete database storage engine.

⚠️ Independent Gap Coverage: Writing a Custom Buffer Pool Manager in C++

To implement your C++ Buffer Pool Manager, you must build a structure that manages a fixed number of in-memory page frames (a raw byte array pool) and a tracking table.

#include <unordered_map> #include <list> #include <vector> #include <iostream>

struct FrameMetadata { uint32_t page_id = 0; uint32_t pin_count = 0; bool is_dirty = false; };

class BufferPoolManager { private: static constexpr size_t PAGE_SIZE = 4096; size_t pool_size_;

// Physical memory array containing cached page frames
std::vector<char> memory_pool_; 

// Map tracking which PageID is loaded into which physical FrameID
std::unordered_map<uint32_t, uint32_t> page_table_; 

// Metadata array matching frames
std::vector<FrameMetadata> frame_table_;

// LRU list tracking eviction candidates (only frames with pin_count == 0)
std::list<uint32_t> lru_list_;

public: BufferPoolManager(size_t pool_size) : pool_size_(pool_size), memory_pool_(pool_size * PAGE_SIZE), frame_table_(pool_size) {}

char* FetchPage(uint32_t page_id) {
    // 1. If page is in memory, increment pin count and return
    if (page_table_.find(page_id) != page_table_.end()) {
        uint32_t frame_id = page_table_[page_id];
        frame_table_[frame_id].pin_count++;
        // Remove from LRU list since it is currently pinned/active
        lru_list_.remove(frame_id); 
        return &memory_pool_[frame_id * PAGE_SIZE];
    }

    // 2. If page is not in memory, we need to load it. Find eviction candidate from LRU list.
    if (lru_list_.empty() && page_table_.size() >= pool_size_) {
        std::cerr << "Out of memory! All pages are currently pinned." << std::endl;
        return nullptr;
    }

    uint32_t victim_frame = 0;
    if (page_table_.size() >= pool_size_) {
        victim_frame = lru_list_.back();
        lru_list_.pop_back();
        
        // If dirty, write back to disk before evicting
        if (frame_table_[victim_frame].is_dirty) {
            WriteToDisk(frame_table_[victim_frame].page_id, &memory_pool_[victim_frame * PAGE_SIZE]);
        }
        page_table_.erase(frame_table_[victim_frame].page_id);
    } else {
        victim_frame = page_table_.size();
    }

    // 3. Load page from disk into the frame
    ReadFromDisk(page_id, &memory_pool_[victim_frame * PAGE_SIZE]);
    
    frame_table_[victim_frame].page_id = page_id;
    frame_table_[victim_frame].pin_count = 1;
    frame_table_[victim_frame].is_dirty = false;
    page_table_[page_id] = victim_frame;

    return &memory_pool_[victim_frame * PAGE_SIZE];
}

void UnpinPage(uint32_t page_id, bool is_dirty) {
    if (page_table_.find(page_id) == page_table_.end()) return;
    uint32_t frame_id = page_table_[page_id];

    if (is_dirty) frame_table_[frame_id].is_dirty = true;
    
    frame_table_[frame_id].pin_count--;
    if (frame_table_[frame_id].pin_count == 0) {
        // Safe to evict later
        lru_list_.push_front(frame_id); 
    }
}

private: void ReadFromDisk(uint32_t page_id, char* dest) { // Physical disk read implementation using fstream goes here }

void WriteToDisk(uint32_t page_id, const char* source) {
    // Physical disk write implementation using fstream goes here
}

};

Key People Index

Andy Pavlo (Associate Professor of Database Systems, Carnegie Mellon University): Architect of the open-source CMU database curriculum and leading researcher in in-memory and autonomous database engines. His lectures (featured in Module 5) are standard material for modern database systems design.
Cherno (Software Engineer & Educator): Former EA Frostbite Engine developer. His deep C++ tutorials are widely used for learning manual pointer manipulation, low-level optimization, and custom memory allocators.
Michael Stonebraker (Pioneer of Relational Databases, Turing Award Winner): Lead designer of historical systems including INGRES, Postgres, and C-Store. His foundational work on OS-level interactions vs DBMS-level buffering informs why we build custom buffer managers instead of relying on the operating system.

Final Self-Assessment

Complete this comprehensive final checklist to verify that your custom on-disk B+ Tree engine matches industry standards:

Explore Further

Related Computer Science Roadmaps

View All→

computer-science

B+ Tree Engines: On-Disk Storage in C++

Course Map

Module 1: C++ Programming & Memory Management Foundations

Recommended Videos

Module 2: Data Structures: BST to B+ Trees

Recommended Videos

Module 3: Disk I/O & Low-Level Byte Representation

Recommended Videos

⚠️ Independent Gap Coverage: Memory Alignment & Struct Packing in C++

Module 4: B+ Tree Implementation and On-Disk Node Layout

Recommended Videos

⚠️ Independent Gap Coverage: Writing an On-Disk B+ Tree Node Layout in C++

Module 5: Buffer Pool Management and Storage Engine Integration

Recommended Videos

⚠️ Independent Gap Coverage: Writing a Custom Buffer Pool Manager in C++

Key People Index

Final Self-Assessment

Related Computer Science Roadmaps

Building BitTorrent: Go, P2P & Concurrency

Actor Models (C++ Concurrency & Lock-Free)

Coding HM Type Inference: Algorithm W & OCaml

Building OAuth 2.0: Node.js OIDC Server