Recently, I completed a major project titled “Design and Performance Analysis of a File-Based Database Engine with B-Tree Indexing in C++” alongside my team (Ankit, Bishal, Aaryan, and myself). The motivation was simple: modern database systems offer excellent performance but often hide their internal implementations behind high-level interfaces. We wanted to look under the hood and build an educational, from-scratch storage engine to understand how indexing, file storage, and query execution actually work.

The Motivation and Objectives

While production-grade databases like SQLite, MySQL, or PostgreSQL employ advanced features (transaction management, concurrency control, caching), they are often too complex for educational purposes. We set out to bridge this gap by developing a simplified file-based database engine that exposes the core concepts of storage management and indexing.

Our main objectives were to:

• Design and implement a file-based database engine using C++.
• Develop a B-Tree indexing mechanism for efficient insertion, searching, and deletion of records stored in binary files.
• Evaluate the performance of B-Tree indexing by comparing it with sequential linear search across varying dataset sizes.

System Architecture and Design

Our system, referred to as CDB1 (Custom Database Binary Format v1), follows a modular architecture accessed through a Command-Line Interface (CLI). It consists of:

1. Storage Manager: Handles reading and writing fixed-size pages to disk.
2. Record Manager: Manages the internal structure of pages and records.
3. Index Manager: Maintains the B-Tree index structure for fast lookups.
4. Query Processor: Executes queries like point lookups, range scans, and prefix searches.

Storage-Layer Database Design

To emulate the physical storage layout of mature systems, we designed a custom binary file format:

• 4KB Fixed Pages: The database is divided into fixed-size 4,096-byte pages, matching the typical OS filesystem block size to minimize physical disk I/O.
• Slotted-Page Format: Each page contains a header, a slot directory, and up to 32 fixed 128-byte slots for storing records.
• Buffer Pool Management: We implemented an in-memory buffer pool using a clock-based replacement policy to avoid the sequential-flooding failure mode seen with standard LRU policies during full range scans.

Why B-Tree Indexing?

We implemented a B+-Tree index to map primary keys to physical file locations. A B-Tree maintains sorted data and enables searches, insertions, and deletions in logarithmic time—O(log n).

• Internal Pages: Store separator keys and child page pointers to route searches.
• Leaf Pages: Store the actual key and record-offset pairs. They also hold a pointer to the next leaf page, supporting highly efficient ordered range scans without re-traversing the tree.

By fixing our branching factor at approximately m = 32, a fully populated 1-million-record CDB1 index requires at most 4 page reads to reach a leaf!

Performance Analysis & Benchmarks

To evaluate the effectiveness of our indexing mechanism, we benchmarked the CDB1 engine against SQLite, the most widely used embedded database engine globally.

We benchmarked three distinct indexing strategies:

1. Linear Scan: No secondary index; every lookup performs a full sequential scan (O(n)).
2. Hash Index: An in-memory hash map providing O(1) average-case lookups.
3. B-Tree Index: Our custom on-disk B+-Tree giving O(log n) lookups.

The results were phenomenal. At a scale of 1,000,000 records, our custom B-Tree index performed exceptionally well on read-heavy operations:

• Point Lookup (100 records): CDB1 took 0.361 ms vs SQLite’s 1.304 ms.
• Range Query (100 records): CDB1 took 0.033 ms vs SQLite’s 0.066 ms.
• Prefix Search (GLOB): CDB1 took 0.048 ms vs SQLite’s 0.208 ms.

Because CDB1 avoids SQLite’s general-purpose overhead (like SQL parsing and query planning), we were able to match or even outperform SQLite on indexed read access!

Challenges and Limitations

Building a custom engine also revealed the massive engineering gap between an academic project and a decades-optimized production system.

Our primary bottleneck was Write-Path Maintenance. For update and delete operations, SQLite updates records in-place using an optimized Write-Ahead Log (WAL) and page-level free-space management. In contrast, our current CDB1 implementation performs index maintenance by re-locating and rewriting the affected node. This resulted in update and delete times that were significantly slower than SQLite at the 1-million record scale.

Conclusion and Future Enhancements

Overall, the project successfully validated our core architectural choices—a B-Tree index over a slotted 4KB page layout—proving that a from-scratch engine can achieve production-comparable read performance.

Looking forward, there are several exciting areas for enhancement:

• Implementing in-place slot updates and deferred node rebalancing to close the update/delete performance gap.
• Extending the write-ahead logging system to support full crash recovery.
• Introducing a background compaction strategy.

If you are interested in exploring the codebase and learning more about how databases operate internally, check out the full source code for the CDB1 and Btree-Indexing projects on my GitHub profile.