Building my own database in c++
Table of Contents
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 dbTo 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 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 dbDuring 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.