How data is stored
Part 1 of the series.
Everything a database does ends up as bytes in a file. Queries, transactions, threads and crash recovery all sit on top of one decision that is easy to forget about: how those bytes are laid out. If the layout is bad, nothing built on top of it can be good, so this is where I want to start.
A file made of pages
The whole database consists of one single file. This file is cut into pages of the same size. For memory alignment concerns, page size must be a power of two. In my database, the default page size is 4 KiB, and it can be any power of two up to 64 KiB.
Working with equal sizes buy you one very useful thing: finding a page costs nothing.
Page number n starts at offsetn × page sizein the database file, so there is no index to consult and no search to do. You multiply and seek. This saves you from creating a Page Directory (like PostgresSQL does, by the way), which mainly is a lookup table in which you store the location of each page in the file.
The first pages of the file always play the same role:
page 0 the header of the database
page 1 catalog: the list of tables
page 2 catalog: the list of indexes
page 3+ everything elsePage 0 starts with a magic number (the ASCII bytes for “AxmosDB”, so that opening a random file fails right away) and holds the information that describes the whole database: the page size, how many pages the file has, where the free pages are, and a few counters that are needed for transaction management and recovery.
Pages 1 and 2 are also reserved for the database catalog, which is where the database remembers what tables and indexes exist.
Everything after that is one of three kinds of page:
- A B+tree page.
- An overflow page
- A free page.
What is a B+Tree?
If you are not familiar with database data structures, you might have been overwhelmed by the term B+Tree. I am going to dive on this later, but for now just treat a B+Tree as a special type of binary tree.
If you remember from basic Data Structures and Algorithms class, binary trees allow you to perform binary search fast on very large collections of items. For instance, in the image below, if you wanted to search for key number 8, you start at the root (25), since 8 is less than 25, you go to the left of the tree. Repeat the same process until you reach the node with 5. 8 is higher than 5 so you go to the right and yay! there you found your key.
As I mentioned, a B+Tree is a special type of binary tree. The main problem with binary trees is that if you store all keys in sorted order, it ends up becoming a linked list, so in databases, where constant SLOs are key, we prefer using structures that stay balanced. That is the main advantage of B+Trees: they are Balanced Binary Trees.
This is an example of a B+Tree with order 4 (the order is the maximum number of keys a node can store). The main difference is that a node can have up to 4 keys and up to 5 children (one per key plus what is called the right most child).
Inside a page
A page has to store records of variable length, a name here and a long text there, and it has to let you insert and delete them without rewriting everything.
The classic approach, which PostgreSQL and SQLite also use, is called the slotted page approach.
The page has two areas that grow towards each other. At the front there is a small header and then an array of slots, which are just 2-byte numbers. Each slot says at which byte of the page a record starts. The records themselves (I call them cells) are written from the back of the page forwards. The free space is whatever remains in the middle.
+--------------------------------------------------------+
| header | slot 0 | slot 1 | slot 2 | -> |
| |
| free space |
| |
| <- | cell 2 | cell 1 | cell 0 | |
+--------------------------------------------------------+The reason for the slot array is that it lets the cells stay where they are while the slots are kept sorted by key. To insert a record in the middle of a page, I write the cell in the free space, and then shift a few 2-byte numbers to make room for its slot. This way, the records are never moved. It also means that the identity of a record inside a page is its slot number, not a byte position that changes every time something is rearranged.
The header of a B+tree page stores page metadata: its own page number, how many slots it has, where the free space starts, and pointers to other pages.
B+Tree pages are called this way because there are linekd together in a B+Tree structure. There is a root page, and every page has pointers to its children. This allows us to perform fast search on the database items.
This means that in the header of a B+Tree page, we basically need two links the page to the previous and next page at the same level of the tree. The third link stored in the header is a pointer to the right-most child, which is the child page containing keys higher than the one in this page.
Anatomy of a cell:
A cell is a small header followed by the payload.
+--------------------------------------------------------+
| header | payload (variable lenght).... |
+--------------------------------------------------------+The header contains certain metadata like the total cell size, whether part of the payload lives somewhere else (see: Rows that do not fit and overflow pages) and extra pointers used by the B+Tree traversal algorithm.
In a B+Tree leaf page the payload is a database row.
In an B+Tree interior page the payload is a copy of a key, that is used to traverse down the B+Tree and find the actual data.
Why every table is a B+tree
Now the question that decides most of the rest: when somebody inserts a row, where does it go?
Get Raul Moldes’s stories in your inbox
Join Medium for free to get updates from this writer.
There are two common answers to this question.
- PostgreSQL uses the heap approach: every table is a pile of pages, and a new row goes into whichever page has room. The table has no order at all. That makes inserting trivial, but it also means that to find anything you need an index.
- The other answer is to make the table itself a tree. Rows are stored in the leaves of a B+tree, sorted by a key, and so the table and its primary index are the same structure. Looking up a row by key means walking down the tree, and the row is right there where the walk ends. There is no second step to go and fetch it. MySQL’s InnoDB works like this, and so does SQLite for ordinary tables. SQLite was my starting point, which is why I ended up here. Additionally, this approach has the advantage that you can use the same structure you created to store tables in order to create indexes, which reduces the amount of code you need to write.
A full table scan is then just a walking along the leaves, from the leftmost to the right one, following the pointers in the page headers.
B+Tree search algorithm
A B+tree is a tree where all the data lives in the leaves. Interior pages hold only keys and pointers, and their only purpose is to guide the search.
An interior cell contains a key and a pointer to the child page that holds the keys smaller than it. For the keys bigger than all of the cells in the page, the header has one extra pointer, the right child. So a page with n cells has n+1 children:
To search for a key, you start at the root, and traverse the tree down using binary search, as you would do with a standard binary tree. I encourage you to try this B+Tree simulator if you want to understand it better: B Tree Visualization.
Keeping it balanced
Inserting a row means finding the right leaf and writing the cell into it. Then the tree checks how full the page is, using two limits that are fractions of the usable space in the page:
- If the page is more than three quarters full, the page is in overflow state,
- If the page is less than one quarter full, it is in underflow state.
In between, nothing happens. Outside of that range, the tree has to rebalance.
I followed the algorithm that SQLite documents for its own B-tree module, which looks at a group of neighbouring pages at once.
Say a leaf has overflown. The algorithm takes that leaf and up to two neighbours on each side, so as many as five pages. Then it does the following:
- It pulls every cell out of all those pages into one ordered list. For interior pages the separator keys that sit in the parent have to come along, because they move too.
- It works out the best way to pack the list into pages. It fills the first page up to the three-quarters limit, then starts the second one, and so on. If the last page ends up too empty, it takes cells from the page before it until both are above the one-quarter limit.
- It allocates more pages if it needs them, and frees the ones left empty.
- It writes the cells back, fixes the separators in the parent, and fixes the sibling links, including those of the pages at the edge of the group.
The nice thing about this is that you always redistribute and pack data among pages in the most efficient way. A classic split gives you two half-empty pages, and if you insert in ascending order, you leave a trail of half-empty pages behind you.
Redistributing among neighbours packs the half-empty pages you left.
The price is that a single insert can rewrite up to five pages instead of two, which makes my database more optimized for READ operations rather than WRITE operations.
Rows that do not fit and overflow pages
What if a row is bigger than a page? Or just big enough to be a problem?
A tree needs several cells in every page. If one page could hold only one cell, the tree would degenerate into a linked list, and the balancing algorithm would have nothing to work with. So there is a rule: a page must always be able to hold at least min_keys cells (default is three). That puts a limit on how much of a row may live in a leaf. With the defaults and a 4 KiB page, it is a bit over 1.3 KB.
When a row is bigger than that, the database first checks whether the row has padding that can be removed. If it still does not fit, the row is cut. The first part stays in the leaf, and the cell is flagged as an overflow cell. The last 8 bytes of that cell contain the number of the first overflow page. The rest of the row goes into a chain of overflow pages. Each one has a small header with the number of bytes it holds and a pointer to the next page, and it is filled completely before moving to the next one.
leaf page overflow page overflow page
+------------------+ +----------------+ +----------------+
| ... first 1.3 KB | ----> | next ----------+-----> | next = none |
| of the row, ptr | | bytes ... | | bytes ... |
+------------------+ +----------------+ +----------------+To read the row back, the database follows the chain and sticks the pieces together. If the key of a row is one of the things that spilled, the comparison logic reassembles it first, so searches keep working.
SQLite does the same thing. PostgreSQL goes further with TOAST, which moves large values to a separate table, and can compress them.
Free pages
Pages come and go. The balancing algorithm frees some when it merges, and the root gives one back when the tree shrinks. Those pages cannot just be forgotten, or the file would grow forever.
The free pages form a linked list that lives inside the pages themselves. A freed page is rewritten with the same small header as an overflow page, and its next pointer points at the next free page. Page 0 remembers where the list starts and where it ends. Freeing a page appends it at the end of the list. Asking for a page takes one from the start. If the list is empty, the file just grows by one page.
That costs no extra space, since a free page has nothing else to store. It also means free pages come back in the same order they left. SQLite has a free list stored in the pages as well, with a slightly different structure. PostgreSQL does it differently again, with a separate map of free space for each table, and it relies on vacuum to maintain it.
Next page:
If you want to keep reading, next page is about dealing with the operating system, direct io and how to manage the disk and memory in databases: Dealing with the operating system | by Raul Moldes | Nov, 2026 | Medium
The series:
This set of articles are designed as an explanation of each part of AxmosDB, in the order a statement meets them.
- How data is stored. Part 1 of the series. | by Raul Moldes | Nov, 2026 | Medium: The page format, why every table is a B+tree, how the tree balances itself, overflow pages and free pages.
- Dealing with the operating system | by Raul Moldes | Nov, 2026 | Medium: The pager, the page cache, and why the database skips the operating system cache with direct I/O.
- Crash recovery. Part 3 of the series. | by Raul Moldes | Nov, 2026 | Medium: The write-ahead log, and how the database gets back to a consistent state after the power goes out.
- Concurrency control. Part 4 of the series. | by Raul Moldes | Nov, 2026 | Medium: Transactions, snapshots and row versions.
