A B-Tree implementation in OCaml
MIT License
A B-Tree implementation in OCaml
This library implement a B-Tree for fixed sized keys and fixed size values. In other word the size (in bytes) of both the key and the value is known in advanced and is constant.
The main OCaml module is Btree.
The B-Tree is assumed to be entirely stored in a single continuous storage. That storage can be a file of course but not required. In fact the module Btree_bytes implement the B-Tree storage in an in-memory byte array.
The storage is not required to be entirely dedicated to storing the B-Tree; the caller application is responsible to allocate new B-Tree node in the storage and make sure no other part of the application will override that data. For instance the caller application could choose to write in the same file multiple B-Trees.
The core module Btree does not make any assumption about how the following disk operation are implemented; they are delegated to the caller through the returned type of each module function:
The module Btree should therefore never be used directly by application code but it should rather be used as the core implementation of an opinionated B-Tree which implements the actual disk operation. In short this library provides a building block to use B-Trees in your own storage solution.
Additionally this package provides 2 example of B-Tree implementation which are using the Btree module as their code logic:
Unix
module part of the OCaml distributionThe original motivation for this project was my RAFT personal project which consists in implementing a generic and robust RAFT system. The RAFT protocol requires a reliable file storage; while I started to look at standard solution like SQLite, I got curious and wanted to learn more about file storing and indexing. This library will be a fundamental building block of the storage solution required for my project.
Furthermore recent reading picked my interest regarding various topics:
Implementing this Btree was a good way to learn more about the details of disk storage (which is far from trivial).