A B-Tree tutorial series implementing an ABI-compatible BerkeleyDB clone.
Introduction
Welcome to the B-Tree tutorial.
Reading
Support for parsing and printing information contained in the header for BerkeleyDB pages.
Our next goal is to be able to walk the tree, and print out the values stored in the B-Tree.
Opening and closing databases as a BerkeleyDB ABI-compatible library.
Support for searching down the tree in search of a single value.
I’ll return to this series at some point, but it’s on temporary hold while I type out other posts. The likely future posts in this series are:
-
Range Reads
-
Page Cache
Writing
-
Modifying Existing Pages
-
Splitting
-
Merging
Recovery
-
WAL Format
-
Replaying WAL
-
Writing a WAL
And then transaction management needs to go somewhere.
See discussion of this page on Reddit, Hacker News, and Lobsters.