Building my own database in c++

Table of Contents

• Implementing a database page
• Implementing the disk manager
• Implementing the LRUReplacer
• Implementing the buffer pool manager
• Introducing tuples and RID
• Implementing the tablePage
• Implementing the table heap

Implementing a Database Page

A page is the fundamental unit of storage in a database system. Rather than reading and writing individual records directly from disk, databases manage data in fixed-size pages. When data is fetched from disk, it is loaded into memory as a page object, allowing higher-level components such as table heaps, indexes, and the buffer pool manager to access it efficiently.

Our implementation uses a fixed page size of 4096 bytes. Each page contains a raw byte buffer that stores the page contents, along with metadata used by the buffer pool manager to track the page's state.

The page_id_ uniquely identifies the page on disk. The is_dirty_ flag indicates whether the page has been modified since it was loaded into memory. If a page is dirty, the buffer pool manager must eventually flush it back to disk so that the changes are persisted.

The pin_count_ tracks how many operations are currently accessing the page. A page with a non-zero pin count cannot be evicted from the buffer pool, preventing active readers or writers from referencing invalid memory.

The complete page interface is shown below:

1// ================================
2// File: include/db/page.h
3// Fixed-size page abstraction (disk + memory unit)
4// ================================
5#pragma once
6
7#include <array>
8#include "types.h"
9
10namespace db
11{
12
13    constexpr size_t PAGE_SIZE = 4096;
14    constexpr PageId INVALID_PAGE_ID = -1;
15
16    class Page
17    {
18    public:
19        Page();
20
21        PageId getId() const;
22
23        void setPageId(PageId id);
24
25        // Raw byte access for serializers / B-Tree nodes
26        uint8_t *data();
27        const uint8_t *data() const;
28
29        template <typename T>
30        T read(size_t offset) const
31        {
32            if (offset + sizeof(T) > PAGE_SIZE)
33            {
34                throw std::out_of_range("Reading past the DB page");
35            }
36            T val;
37            std::memcpy(&val, buffer_.data() + offset, sizeof(T));
38            return val;
39        }
40
41        template <typename T>
42        void write(size_t offset, const T &value)
43        {
44            if (offset + sizeof(T) > PAGE_SIZE)
45            {
46                throw std::out_of_range("Reading past the DB page");
47            }
48            std::memcpy(buffer_.data() + offset, &value, sizeof(T));
49            mark_dirty();
50        }
51
52        bool is_dirty() const;
53
54        void mark_dirty();
55
56        void clear_dirty();
57
58        int pin_count() const;
59
60        void pin();
61
62        void unpin();
63
64        void reset();
65
66    private:
67        PageId page_id_;
68        std::array<uint8_t, PAGE_SIZE> buffer_;
69        bool is_dirty_;
70        int pin_count_;
71    };
72
73} // namespace db

To support storing arbitrary data inside a page, the read() and write() functions use std::memcpy to copy raw bytes between the page buffer and application objects. This allows primitive values and serialized structures to be written directly to specific offsets within the page.

Before performing the copy, we verify that the requested operation remains within the page boundaries. This protects against accidental memory corruption caused by reading or writing past the end of the buffer.

The implementation of the page methods is shown below:

1#include "page.h"
2#include "types.h"
3
4using namespace db;
5
6Page::Page() : page_id_(INVALID_PAGE_ID), is_dirty_(false), pin_count_(0) {}
7
8PageId Page::getId() const
9{
10    return page_id_;
11}
12
13void Page::setPageId(PageId id)
14{
15    page_id_ = id;
16}
17
18uint8_t *Page::data()
19{
20    return buffer_.data();
21}
22
23const uint8_t *Page::data() const
24{
25    return buffer_.data();
26}
27
28bool Page::is_dirty() const
29{
30    return is_dirty_;
31}
32
33void Page::mark_dirty()
34{
35    is_dirty_ = true;
36}
37
38void Page::clear_dirty()
39{
40    is_dirty_ = false;
41}
42
43int Page::pin_count() const
44{
45    return pin_count_;
46}
47
48void Page::pin()
49{
50    pin_count_++;
51}
52
53void Page::unpin()
54{
55    if (pin_count_ > 0)
56        pin_count_--;
57}
58
59void Page::reset()
60{
61    page_id_ = INVALID_PAGE_ID;
62    std::memset(buffer_.data(), 0, PAGE_SIZE);
63    is_dirty_ = false;
64    pin_count_ = 0;
65}

Although the implementation is relatively small, the page abstraction forms the foundation of the storage engine. Every table page, B+ Tree node, and buffer pool frame ultimately relies on this class to manage data safely and efficiently in memory.

Implementing the Disk Manager

The Disk Manager is responsible for persisting database pages to disk and loading them back into memory when needed. It acts as the storage layer of the database, providing a simple interface for reading and writing pages without exposing the underlying file operations to higher-level components such as the buffer pool manager.

Since pages contain raw binary data rather than human-readable text, the database file is opened using std::ios::binary. This ensures that bytes are written to disk exactly as they appear in memory, without any platform-specific text encoding or newline transformations.

Each page occupies a fixed-size region within the database file. Given a page identifier, we can calculate its location on disk using the formula page_id * PAGE_SIZE. This offset allows us to jump directly to a page without scanning through the file, providing constant-time access to any page stored on disk.

The Disk Manager interface is shown below:

1// ================================
2// File: include/db/disk_manager.h
3// Responsible for reading/writing pages to disk
4// ================================
5#pragma once
6
7#include <string>
8#include "page.h"
9#include <fstream>
10
11namespace db
12{
13
14    class DiskManager
15    {
16    public:
17        explicit DiskManager(const std::string &db_file);
18
19        // Read a page from disk into memory
20        void read_page(PageId page_id, Page &page);
21
22        // Write a page from memory to disk
23        void write_page(const Page &page);
24
25    private:
26        std::fstream stream_;
27    };
28
29}

When reading a page, we first position the file's read pointer using seekg() before copying PAGE_SIZE bytes into the page buffer. The page stores its contents as raw bytes, so we pass the underlying buffer returned by page.data() directly to the file stream.

A special case occurs when reading beyond the end of the file. In this situation, the stream may return fewer than PAGE_SIZE bytes. Rather than leaving the remainder of the page uninitialized, we fill the unused region with zeros using std::memset. This mirrors the behavior of many database systems, where pages that have not yet been written are treated as empty pages.

Writing follows a similar process. We position the write pointer using seekp(), write exactly one page worth of bytes to disk, and then call flush() to ensure that buffered data is pushed to the operating system. This guarantees that recently modified pages are not left sitting in the stream's internal buffer.

The implementation is shown below:

1#include "disk_manager.h"
2#include "iostream"
3#include <cstring>
4
5using namespace db;
6
7DiskManager::DiskManager(const std::string &db_file) : stream_(db_file, std::ios::in | std::ios::out | std::ios::binary)
8{
9    if (!stream_)
10    {
11        std::fstream create(db_file, std::ios::out | std::ios::binary);
12        create.close();
13
14        stream_.open(db_file, std::ios::in | std::ios::out | std::ios::binary);
15        if (!stream_)
16        {
17            std::cerr << "Error opening file!" << std::endl;
18        }
19    }
20};
21
22void DiskManager::read_page(PageId page_id, Page &page)
23{
24    size_t offset = page_id * PAGE_SIZE;
25    stream_.seekg(offset, std::ios::beg);
26
27    stream_.read(reinterpret_cast<char *>(page.data()), PAGE_SIZE);
28
29    std::streamsize bytes_read = stream_.gcount();
30    if (bytes_read < PAGE_SIZE)
31    {
32        std::memset(page.data() + bytes_read, 0, PAGE_SIZE - bytes_read);
33        stream_.clear();
34    }
35}
36
37void DiskManager::write_page(const Page &page)
38{
39    size_t offset = page.getId() * PAGE_SIZE;
40    stream_.seekp(offset, std::ios::beg);
41
42    stream_.write(reinterpret_cast<const char *>(page.data()), PAGE_SIZE);
43
44    if (!stream_)
45    {
46        std::cerr << "Error writing page to disk" << std::endl;
47    }
48
49    stream_.flush();
50}

Although the Disk Manager is relatively small, it forms the bridge between persistent storage and in-memory data structures. Every page fetched by the buffer pool and every modification eventually written back to disk passes through this component.

Implementing the LRUReplacer

Once the buffer pool becomes full, the database needs a way to decide which page should be removed from memory to make room for a new one. This is the responsibility of the LRUReplacer. It keeps track of frames that are currently eligible for eviction and selects the least recently used frame when the buffer pool needs additional space.

Not every frame in the buffer pool can be evicted. A page with a non-zero pin_count is currently being used by another operation and must remain in memory. Therefore, the LRUReplacer only stores frames whose pin count has reached zero.

To implement the LRU policy efficiently, we use two data structures: a std::list and a std::unordered_map. The list maintains the frames in LRU order, while the hash map allows us to quickly locate a specific frame inside the list.

The front of the list represents the least recently used frame, while the back represents the most recently added frame. The hash map stores an iterator pointing to each frame's position in the list. This allows us to remove a specific frame without having to search through the entire list.

The complete interface and implementation are shown below:

1// ================================
2// File: include/db/lru_replacer.h
3// LRU eviction policy for buffer pool frames
4// ================================
5#pragma once
6
7#include <list>
8#include <unordered_map>
9
10namespace db
11{
12    class LRUReplacer // stores frames that are currently evictable(pin count = 0)
13    {
14    public:
15        explicit LRUReplacer(size_t capacity);
16
17        // Remove the least recently used frame — return the frame id
18        bool evict(size_t &frame_id);
19
20        // Remove frame from LRU-Replacer(when a page gets pinned again)
21        void remove(size_t frame_id);
22
23        // When pin count becomes 0, frame becomes evictable
24        void add(size_t frame_id);
25
26        // How many frames are currently evictable?
27        size_t size();
28
29    private:
30        std::unordered_map<size_t, std::list<size_t>::iterator> map_;
31        std::list<size_t> lru_;
32    };
33}

1// ================================
2// File: src/lru_replacer.cpp
3// ================================
4
5#include "lru_replacer.h"
6
7using namespace db;
8
9LRUReplacer::LRUReplacer(size_t capacity)
10{
11}
12
13// Add an evictable frame to the LRU list
14void LRUReplacer::add(size_t frame_id)
15{
16    if (map_.count(frame_id))
17    {
18        return;
19    }
20
21    lru_.push_back(frame_id);
22    auto it = std::prev(lru_.end());
23    map_.emplace(frame_id, it);
24}
25
26// Remove a frame when its page becomes pinned
27void LRUReplacer::remove(size_t frame_id)
28{
29    auto it = map_.find(frame_id);
30
31    if (it == map_.end())
32    {
33        return;
34    }
35
36    lru_.erase(it->second);
37    map_.erase(it);
38}
39
40// Evict the least recently used frame
41bool LRUReplacer::evict(size_t &frame_id)
42{
43    if (lru_.empty())
44    {
45        return false;
46    }
47
48    frame_id = lru_.front();
49    lru_.pop_front();
50    map_.erase(frame_id);
51
52    return true;
53}
54
55// Return the number of currently evictable frames
56size_t LRUReplacer::size()
57{
58    return map_.size();
59}

The add() method adds an evictable frame to the back of the LRU list when its pin count reaches zero. The hash map stores an iterator to the frame, allowing it to be found and removed efficiently. Duplicate frames are ignored.

When a page is fetched again and becomes pinned, remove() removes its frame from the replacer. The hash map lets us locate the frame directly without traversing the list.

When the buffer pool needs a frame, evict() takes the frame at the front of the list, which is the least recently used evictable frame, and removes it from both data structures. If the list is empty, no frames are available for eviction.

The size() method simply returns the number of evictable frames stored in the hash map.

Together, the list and hash map provide efficient LRU management: the list gives constant-time access to the least recently used frame, while the hash map allows specific frames to be found and removed efficiently. The replacer therefore tracks which unpinned frames can be reused when the buffer pool runs out of space.

Implementing the Buffer Pool Manager

With the Page,DiskManager, and LRUReplacer completed, we can now build the heart of the storage engine: the BufferPoolManager. Its responsibility is to manage a fixed-size pool of in-memory pages, ensuring that frequently accessed pages remain cached while pages that are no longer being used can be safely evicted back to disk.

The buffer pool manager owns several important data structures. It stores a fixed-size vector of Page objects, which represent the physical frames in the buffer pool. A page_table_ maps each logical PageId to its corresponding frame index, allowing pages to be located in constant time. When the buffer pool becomes full, the LRUReplacer determines which unpinned frame should be evicted. Finally, a queue of free frames keeps track of frames that have never been used, allowing new pages to be loaded without performing eviction whenever possible.

1#pragma once
2
3#include <unordered_map>
4#include <mutex>
5#include "disk_manager.h"
6#include <vector>
7#include "lru_replacer.h"
8#include <atomic>
9#include <unordered_set>
10#include <queue>
11
12namespace db
13{
14
15    class BufferPoolManager
16    {
17    public:
18        explicit BufferPoolManager(DiskManager &disk, size_t pool_size);
19
20        PageId fetch_next_page();
21
22        // Fetch a page into memory (pin it), can be used to read or write from it
23        // another external process that reads/write must be in charge of marking dirty
24        Page *fetch_page(PageId page_id);
25
26        // Unpin page (allow eviction)
27        void unpin_page(PageId page_id);
28
29        void flush_page(PageId page_id);
30        // void flush_all();
31
32    private:
33        DiskManager &disk_;
34        std::mutex latch_;
35        std::vector<Page> pages;                        // Fixed size pool, pages lives here permanently
36        std::unordered_map<PageId, size_t> page_table_; // maps the pageId to the index in the vector
37        LRUReplacer cache_;
38        std::atomic<PageId> nextpage_;
39        std::queue<size_t> free_frames_;
40    };
41
42} // namespace db

During construction, the buffer pool allocates a fixed number of page frames and places every frame index into free_frames_. Since all frames are initially empty, newly requested pages can be loaded directly into these unused frames before the eviction policy ever needs to be consulted.

1#include "buffer_pool.h"
2#include <utility>
3#include <vector>
4
5using namespace db;
6
7BufferPoolManager::BufferPoolManager(DiskManager &disk, size_t pool_size) : disk_(disk), cache_(pool_size), nextpage_(0)
8{
9    pages.resize(pool_size);
10    for (int i = 0; i < pool_size; i++)
11    {
12        free_frames_.push(i);
13    }
14}
15
16PageId BufferPoolManager::fetch_next_page()
17{
18    return nextpage_.fetch_add(1);
19}
20
21/*
221. If page already cached in page_table, then we pin page, remove from LRUReplacer, and return
232. Else, we need a free frame. We can first try free_frames, else we can try to evict from the LRUReplacer
24
25*/
26Page *BufferPoolManager::fetch_page(PageId page_id)
27{
28    std::scoped_lock lock(latch_);
29
30    auto it = page_table_.find(page_id);
31    if (it != page_table_.end()) // already in page table, loaded previously
32    {
33        size_t frame = it->second;
34        cache_.remove(frame);
35        Page &p = pages[frame];
36        p.pin();
37        return &p; // return a pointer to the page table, so that we can possibly modify this page
38    }
39
40    // Else we need a free frame. We can first try free_frames, else we can try to evict from LRUReplacer
41    if (free_frames_.empty()) // have to get from LRUReplacer
42    {
43        size_t evictedFrame;
44        if (cache_.evict(evictedFrame))
45        {
46            Page &p = pages[evictedFrame];
47            if (p.is_dirty())
48            {
49                disk_.write_page(p);
50            }
51            page_table_.erase(p.getId());
52            p.reset();
53            p.setPageId(page_id);
54            disk_.read_page(page_id, p);
55            page_table_[page_id] = evictedFrame;
56            p.pin();
57            return &p;
58        }
59        else
60        { // no possible frames to be evicted
61            return nullptr;
62        }
63    }
64    else
65    {
66        size_t frameId = free_frames_.front();
67        free_frames_.pop();
68        Page &p = pages[frameId];
69        p.reset();
70        p.setPageId(page_id);
71        disk_.read_page(page_id, p);
72        p.pin();
73        page_table_[page_id] = frameId;
74        return &p;
75    }
76}
77
78// Unpin page (allow eviction)
79// find page in page table, decrement pin count,
80void BufferPoolManager::unpin_page(PageId page_id)
81{
82    /* Usually the client would call fetch_page, work on it, if edit, call page->markDirty(), then they would call
83unpin_page, which would decrement pin_count, and call flush_page if pin_Count is 0.*/
84    std::scoped_lock lock(latch_);
85
86    auto it = page_table_.find(page_id);
87    if (it == page_table_.end())
88        return;
89    size_t frame = it->second;
90    Page &page = pages[frame];
91    page.unpin();
92    if (page.pin_count() == 0)
93    {
94        cache_.add(frame);
95    }
96}
97
98void BufferPoolManager::flush_page(PageId page_id)
99{
100    std::scoped_lock lock(latch_);
101
102    auto it = page_table_.find(page_id);
103    if (it == page_table_.end())
104    {
105        return;
106    }
107    size_t frame_id = it->second;
108    Page &p = pages[frame_id];
109    if (p.is_dirty())
110    {
111        disk_.write_page(p);
112        p.clear_dirty();
113    }
114}
115/*
116We can first obtain the frame_id from the page_table using this pageId, obtain the page, if it is dirty, we
117will call disk_manager.write_page(vector[frameId]), then we will clear out this page.data(maybe add a method
118page to reset the .data(), and add this frameId to the LRUReplacer.*/
119
120// void BufferPoolManager::flush_all()
121// {
122// }

The most important operation provided by the buffer pool manager is fetch_page(). Whenever a client requests a page, the method returns a pointer to the page and increments its pin count, ensuring that it cannot be evicted while it is actively being used.

The first step is to check whether the requested page already exists in the page_table_. If the page is already cached, there is no need to perform any disk I/O. We simply remove the frame from the LRUReplacer, increment the page's pin count, and immediately return the page.

If the page is not currently resident in memory, the buffer pool first attempts to obtain an unused frame from free_frames_. Since these frames have never been used before, no eviction is necessary. The requested page is read from disk, assigned its PageId, pinned, and inserted into the page_table_.

Once every frame has been allocated, the only way to load a new page is to evict an existing one. The LRUReplacer selects the least recently used unpinned frame as the eviction candidate. Before the frame is reused, the buffer pool checks whether the existing page is dirty. If so, it is first written back to disk to ensure no modifications are lost. The frame is then reset, the new page is loaded from disk, and the page_table_ is updated to reflect the new mapping.

After the caller has finished accessing a page, it invokes unpin_page(). This decrements the page's pin count, signalling that the page is no longer actively in use. Once the pin count reaches zero, the frame is added back into the LRUReplacer, making it eligible for eviction if additional space is required.

Finally,flush_page() persists any modified pages to disk. If the page is marked dirty, it is written back using the DiskManager, after which the dirty flag is cleared. Clean pages are skipped entirely, avoiding unnecessary disk writes while still guaranteeing that modified pages are eventually persisted.

Introducing Tuples and RIDs

Before we can store records inside a page, we first need two fundamental data structures: Tuple and RID. A Tuple represents the actual data stored in the database, while an RID (Record Identifier) provides a unique way to locate that tuple within the storage engine.

Instead of storing records directly in indexes or higher-level data structures, the database references them using an RID. This indirection allows records to be efficiently located and retrieved without exposing their physical memory addresses.

1#pragma once
2
3#include "types.h"
4#include "page.h"
5
6namespace db
7{
8
9    struct RID
10    {
11        PageId page_id;
12        uint16_t slot_num;
13
14        RID() : page_id(INVALID_PAGE_ID), slot_num(0) {}
15
16        RID(PageId pid, uint16_t slot) : page_id(pid), slot_num(slot) {}
17    };
18
19}

The RID consists of two fields. The page_id identifies the page that contains the record, while slot_num identifies the record's position within that page. Together, these two values uniquely identify every record stored in the database.

The record itself is represented by the Tuple class. Rather than interpreting the contents, the tuple simply stores the raw bytes that make up a row. Higher-level components, such as the table schema, are responsible for understanding how those bytes should be interpreted as individual columns and data types.

1#pragma once
2#include <vector>
3#include <cstring>
4
5// Represents one row
6
7namespace db
8{
9    class Tuple
10    {
11    public:
12        Tuple() = default;
13        explicit Tuple(const std::vector<char> &data) : data_(std::move(data)) {}
14
15        const char *data() const
16        {
17            return data_.data();
18        }
19
20        size_t size() const
21        {
22            return data_.size();
23        }
24
25    private:
26        std::vector<char> data_;
27    };
28}

The Tuple class is intentionally lightweight. It owns a std::vector<char>containing the serialized bytes of a row and exposes two simple methods: data(), which returns a pointer to the underlying bytes, and size(), which returns the length of the serialized record.

Although these two classes are relatively simple, they form the foundation for the remainder of the storage engine. Every record stored inside a page will be represented as a Tuple, and every record retrieved from the database will be identified by its RID. The next step is to design how these tuples are physically organized inside a page so that they can be efficiently inserted, deleted, and located.

Implementing the TablePage

With Tuple and RID in place, we can now organize tuples inside a database page. The TablePage manages the tuples stored within a single physical page. It does not manage the entire table; instead, it provides the layout and operations needed to insert and retrieve records from one page.

The page uses a slot-based layout. A small header stores metadata such as the number of tuples and the location of the remaining free space. A slot directory follows the header, with each slot storing the offset and size of a tuple. The tuple data itself is stored from the end of the page and grows towards the slot directory.

This layout allows tuples to have different sizes while still being easy to locate. Instead of searching through the page for a tuple, we can use its RID to find the corresponding slot and then use the stored offset and size to locate its bytes.

The page therefore looks roughly like this:

1+---------------------------+
2| Header                    |
3| tuple_count               |
4| free_space_ptr            |
5+---------------------------+
6| Slot 0                    |
7| Slot 1                    |
8| Slot 2                    |
9+---------------------------+
10|                           |
11|        FREE SPACE         |
12|                           |
13+---------------------------+
14| Tuple bytes               |
15| Tuple bytes               |
16| Tuple bytes               |
17+---------------------------+

The TablePageHeader tracks the number of tuples currently stored in the page and a pointer to the beginning of the free space. Since tuple data grows backwards from the end of the page while slots grow forwards from the header, the remaining gap between them represents the available space.

Each Slot stores the location and size of one tuple. This is what allows the page to support variable-sized tuples: given a slot number, we can determine exactly where the tuple starts and how many bytes belong to it.

The complete interface is shown below:

1/*
2One page contains many tuples.
3
4The TablePage manages tuples inside one physical page.
5It uses a slot directory to locate variable-sized tuples.
6
7+---------------------------+
8| Header                    |
9| tuple_count               |
10| free_space_ptr            |
11+---------------------------+
12| Slot 0                    |
13| Slot 1                    |
14| Slot 2                    |
15+---------------------------+
16|                           |
17|        FREE SPACE         |
18|                           |
19+---------------------------+
20| Tuple bytes               |
21| Tuple bytes               |
22| Tuple bytes               |
23+---------------------------+
24*/
25
26#pragma once
27
28#include "page.h"
29#include "tuple.h"
30#include "rid.h"
31
32namespace db
33{
34    struct TablePageHeader
35    {
36        uint16_t tuple_count;
37        uint16_t free_space_ptr;
38    };
39
40    struct Slot
41    {
42        uint16_t offset;
43        uint16_t size;
44    };
45
46    class TablePage
47    {
48    public:
49        explicit TablePage(Page *page);
50
51        void init();
52
53        bool insert_tuple(const Tuple &tuple, RID &rid);
54
55        bool get_tuple(const RID &rid, Tuple &tuple);
56
57        bool has_space(size_t tuple_size);
58
59    private:
60        Page *page_;
61
62        TablePageHeader *header();
63
64        Slot *slots();
65    };
66}

The implementation begins by treating the raw page buffer as the table page's storage. The header() and slots() methods usereinterpret_cast to access the appropriate regions of the page as structured metadata.

When the page is initialized, the tuple count starts at zero and the free space pointer is placed at the end of the page. This means tuple data will be written backwards from PAGE_SIZE, while the slot directory grows forwards from the header.

Before inserting a tuple, has_space() checks whether enough room remains for both the tuple data and its slot metadata. This prevents the tuple data from growing into the slot directory.

1using namespace db;
2
3TablePage::TablePage(Page *page) : page_(page)
4{
5}
6
7TablePageHeader *TablePage::header()
8{
9    return reinterpret_cast<TablePageHeader *>(page_->data());
10}
11
12Slot *TablePage::slots()
13{
14    return reinterpret_cast<Slot *>(page_->data() + sizeof(TablePageHeader));
15}
16
17void TablePage::init()
18{
19    auto *h = header();
20    h->tuple_count = 0;
21    h->free_space_ptr = PAGE_SIZE;
22}
23
24bool TablePage::has_space(size_t tuple_size)
25{
26    auto *h = header();
27
28    size_t slot_end =
29        sizeof(TablePageHeader) + h->tuple_count * sizeof(Slot);
30
31    size_t space_left = h->free_space_ptr - slot_end;
32
33    return space_left >= tuple_size + sizeof(Slot);
34}

To insert a tuple, we first check that enough space is available. The free space pointer is then moved backwards by the size of the tuple, and the tuple's bytes are copied into that location. A new slot records the tuple's offset and size, while the slot number becomes part of the tuple's RID.

Finally, the tuple count is incremented and the page is marked dirty so that the buffer pool knows the page must eventually be written back to disk.

1bool TablePage::insert_tuple(const Tuple &tuple, RID &rid)
2{
3    if (!has_space(tuple.size()))
4    {
5        return false;
6    }
7
8    auto *h = header();
9
10    h->free_space_ptr -= tuple.size();
11
12    uint16_t offset = h->free_space_ptr;
13
14    std::memcpy(
15        page_->data() + offset,
16        tuple.data(),
17        tuple.size()
18    );
19
20    Slot *slot_array = slots();
21
22    uint16_t slot_num = h->tuple_count;
23
24    slot_array[slot_num].offset = offset;
25    slot_array[slot_num].size = tuple.size();
26
27    rid = RID(page_->getId(), slot_num);
28
29    h->tuple_count++;
30
31    page_->mark_dirty();
32
33    return true;
34}

Retrieving a tuple works in the opposite direction. The RID provides the page ID and slot number, so we first validate the slot and then use it to locate the corresponding Slot. The stored offset and size tell us exactly which bytes belong to the tuple.

We copy those bytes into a std::vector<char> and reconstruct the Tuple object from them.

1bool TablePage::get_tuple(const RID &rid, Tuple &tuple)
2{
3    auto *h = header();
4
5    if (rid.slot_num >= h->tuple_count)
6    {
7        return false;
8    }
9
10    Slot *slot_array = slots();
11    Slot &slot = slot_array[rid.slot_num];
12
13    uint16_t offset = slot.offset;
14    uint16_t size = slot.size;
15
16    const uint8_t *data = page_->data() + offset;
17
18    std::vector<char> bytes(
19        reinterpret_cast<const char *>(data),
20        reinterpret_cast<const char *>(data + size)
21    );
22
23    tuple = Tuple(bytes);
24
25    return true;
26}

The TablePage therefore provides the first layer of physical record organization. It manages the layout of tuples within a single page, tracks free space, and uses the slot directory to locate variable-sized records efficiently. Higher-level components can then work with Tuple and RID without needing to understand the underlying byte layout.

Implementing the Table Heap

With the buffer pool in place, we can now build a higher-level component for managing the pages that belong to a table. The TableHeap is responsible for inserting and retrieving tuples while coordinating with the BufferPoolManager to fetch and release pages.

When inserting a tuple, the table heap first checks its existing pages for one with enough free space. If a suitable page is found, it is fetched from the buffer pool and the tuple is inserted into it. If none of the existing pages have enough space, the table heap allocates a new page and uses that instead.

The table heap keeps track of all of its pages using a std::vector<PageId>. This allows insert_tuple() to iterate through the existing pages and find one that can accommodate the new tuple.

1#include "buffer_pool.h"
2#include "table_page.h"
3#include "tuple.h"
4#include "rid.h"
5
6namespace db
7{
8    class TableHeap
9    {
10    public:
11        explicit TableHeap(BufferPoolManager &bpm);
12
13        /*
14            This becomes the real database insertion
15            1. Find page with space
16            2. fetch page from bpm
17            3. Insert tuple into TablePage
18            4. mark dirty
19            5. unpin
20        */
21        RID insert_tuple(const Tuple &tuple);
22
23        /*
24            1. Fetch page
25            2. read tuple
26            3. unpin
27        */
28        bool get_tuple(const RID &rid, Tuple &tuple);
29
30    private:
31        BufferPoolManager &bpm_;
32        std::vector<PageId> pages;
33    };
34}

1using namespace db;
2
3TableHeap::TableHeap(BufferPoolManager &bpm) : bpm_(bpm) {};
4
5RID TableHeap::insert_tuple(const Tuple &tuple)
6{
7    RID rid;
8
9    // 1. Try existing pages
10    for (PageId pid : pages)
11    {
12        Page *page = bpm_.fetch_page(pid);
13
14        if (page == nullptr)
15            continue;
16
17        TablePage tp(page);
18
19        if (tp.has_space(tuple.size()))
20        {
21            tp.insert_tuple(tuple, rid);
22            bpm_.unpin_page(pid);
23            return rid;
24        }
25
26        bpm_.unpin_page(pid);
27    }
28
29    // 2. No space --> allocate new page
30    PageId new_pid = bpm_.fetch_next_page();
31    Page *page = bpm_.fetch_page(new_pid);
32
33    TablePage tp(page);
34    tp.init();
35
36    tp.insert_tuple(tuple, rid);
37
38    pages.push_back(new_pid);
39    bpm_.unpin_page(new_pid);
40
41    return rid;
42}
43
44bool TableHeap::get_tuple(const RID &rid, Tuple &tuple)
45{
46    Page *page = bpm_.fetch_page(rid.page_id);
47
48    if (page == nullptr)
49    {
50        return false;
51    }
52
53    TablePage tp(page);
54
55    bool success = tp.get_tuple(rid, tuple);
56
57    bpm_.unpin_page(rid.page_id);
58
59    return success;
60}

The constructor stores a reference to the BufferPoolManager, which the table heap uses to fetch and unpin pages.

In insert_tuple(), we first check each existing page for enough space. If one is available, we fetch it, insert the tuple through TablePage, unpin it, and return the resulting RID.

If none of the existing pages have enough space, we allocate a new page using fetch_next_page(). The page is initialized, the tuple is inserted, and the new page ID is added to the table's pages vector before unpinning it.

Retrieving a tuple is simpler. The RID already contains the page ID, so we fetch that page and delegate the lookup to TablePage::get_tuple(). Afterward, we unpin the page and return whether the lookup succeeded.

The TableHeap therefore coordinates between the BufferPoolManager and TablePage: it manages which pages belong to the table, while the buffer pool handles page memory and the table page handles the actual tuple storage.