A database needs more than a data file.
It needs a structure that can quickly locate a key without scanning every document.
LioranDB uses a disk-based B+ tree for this job.
What is a B+ tree?
A B+ tree is a balanced search tree designed for storage systems.
It contains two main page types:
Internal pages
Store separator keys and child pointers
Leaf pages
Store actual keys and values
A simplified tree looks like this:
[m]
/ \
[a ... l] [m ... z]
Every lookup follows a path from the root to one leaf.
Because every level can contain many keys, the tree remains shallow even when the database contains millions of records.
Pages, not objects
LioranDB stores B+ tree nodes inside fixed-size disk pages.
Each page contains metadata such as:
Page magic
Page version
Page type
Page ID
Page LSN
CRC32 checksum
The checksum helps detect corrupted pages.
The Page LSN records the latest WAL position reflected by that page, which is useful during recovery and checkpointing.
Why not use a hash table?
A hash table is excellent for exact-key lookups, but it does not naturally support ordered scans.
A B+ tree can efficiently execute:
Find user 100
Find every user from 100 to 200
Find every key starting with "email:"
Walk records in sorted order
This is important because database indexes frequently rely on range and prefix scans.
Bulk loading
LioranDB also contains a bulk-load path for building a new B+ tree from sorted input.
Instead of repeatedly traversing and splitting pages, the engine can construct leaf and internal pages in batches.
That can avoid:
- Repeated root-to-leaf lookups
- Online page splits
- Extra page decoding
- Unnecessary cache pollution
A B+ tree may sound old-school, but it remains one of the most practical foundations for a disk database.
Good database architecture is often less about inventing a new tree and more about implementing an existing one without setting the disk on fire.
Built by Swaraj Puppalwar at Lioran Group.
Explore:
Top comments (0)