Every embedded store needs an on-disk format, and a brand-new one comes with no tools: when a file breaks, nobody can look inside until someone writes them. btree sidesteps that by writing the table and index B-trees of the SQLite file format. The sqlite3 shell and DB Browser can open and inspect its files. The API is a persistent ordered map from int64 rowids to strings (Table) and a persistent ordered set of strings (Index).

Those are the two kinds of B-tree in the specification. A table B-tree is a B+tree, with data only in the leaves and rowid keys plus child pointers in the interior pages. An index B-tree keeps keys in interior and leaf pages alike.

Pages are a power of 2 from 512 to 65536 bytes. Call U the usable page size, the page size less any bytes reserved at the end of each page. A payload over U - 35 bytes on a table leaf, or over ((U - 12) * 64 / 255) - 23 bytes on an index page, continues in overflow pages. The library itself does no I/O: the pager takes an open file, and what the device guarantees, from a Block.Platform. That is why the same code runs on Eio (btree.eio) and on the simulated Block.Sim. The page cache is capped in bytes and evicts with the clock algorithm.

Installation #

Install with opam:

$ opam install btree

If opam cannot find the package, it is not in the public opam-repository yet. Add the overlay repository first:

$ opam repo add samoht https://tangled.org/gazagnaire.org/opam-overlay.git
$ opam update
$ opam install btree

Usage #

Table: insert, find, iterate #

let demo () =
  let pager = Btree.Pager.mem ~page_size:4096 () in
  let table = Btree.Table.v pager in
  Btree.Table.insert table ~rowid:1L "Hello";
  Btree.Table.insert table ~rowid:2L "World";
  (match Btree.Table.find table 1L with
   | Some v -> Fmt.pr "1 -> %s@." v
   | None -> ());
  Btree.Table.iter table (fun rowid data ->
      Printf.printf "%Ld: %s\n" rowid data)

Index: add, membership, range scan #

let index_demo () =
  let pager = Btree.Pager.mem ~page_size:4096 () in
  let index = Btree.Index.v pager in
  Btree.Index.insert index "key";
  Btree.Index.mem index "key"

File-backed #

To store the tree in a file, create the pager on an Eio file with btree.eio, then call Pager.sync to write it out. sqlite3 can open the result:

let persist ~fs =
  Eio.Path.with_open_out
    ~create:(`If_missing 0o644) Eio.Path.(fs / "demo.db")
    (fun file ->
      let pager = Btree_eio.Pager.v ~page_size:4096 file in
      let table = Btree.Table.v pager in
      Btree.Table.insert table ~rowid:1L "persisted";
      Btree.Pager.sync pager)

To reopen the table, create a pager on the same file and call Btree.Table.open_ pager ~root_page. The root page number is the one Btree.Table.save_root returned, or 1 for a new file.

API #

Table #

v pager / open_ pager ~root_page
insert t ~rowid data / find t rowid / delete t rowid
iter t f / fold t ~init ~f
save_root t / restore_root t root: persist the root for reopen

Index #

v pager / open_ pager ~root_page
insert t key / mem t key / find t key / delete t key
iter t f / fold_from / fold_prefix / by_prefix for ordered and prefix scans

Btree_eio.Pager.v ~page_size file: over an Eio file
Pager.Make (P).v ~page_size file: over any Block.Platform
Pager.mem ~page_size (): over Block.Sim, in memory
Pager.sync t: flush dirty pages
Pager.snapshot t / rollback t snap: capture and restore the dirty pages, to abort a logical transaction

Internals #

Modules #

Module	Purpose
`Pager`	Page cache and file I/O (file-backed or in-memory)
`Table`	B+tree for rowid-keyed records (`int64 -> string`)
`Index`	B-tree for string key sets
`Page`	Page header parsing, binary helpers
`Cell`	Cell encoding/decoding (table leaf, interior, index)
`Record`	SQLite record format (serial types, column values)
`Overflow`	Chains of overflow pages for payloads too large for a cell

Offset	Size	Description
0	1	Page type: `0x0d` leaf table, `0x05` interior table, `0x0a` leaf index, `0x02` interior index
1	2	First freeblock offset (0 if none)
3	2	Cell count
5	2	Cell content area start (0 = 65536)
7	1	Fragmented free bytes (max 60)
8	4	Right-most child pointer (interior pages only)

Overflow #

Take a cell whose record is P bytes long. A page stores a payload whole if it is at most X bytes, where X is U - 35 on a table leaf and ((U - 12) * 64 / 255) - 23 on an index page. Past that, the page keeps the first local bytes and the rest goes into a chain of overflow pages, each starting with the 4-byte number of the next one (0 on the last) and holding up to U - 4 bytes of data. Cell.local_size computes local as section 1.6 of the SQLite specification does, in integer arithmetic:

M = ((U - 12) * 32 / 255) - 23
K = M + ((P - M) mod (U - 4))
local = if K <= X then K else M

The page always keeps at least M bytes. K is the prefix of at least M bytes that leaves a remainder divisible by U - 4, so the last overflow page comes out full; when K is over X, the page falls back to M. For a 4096-byte page with no reserved bytes, U = 4096, X = 4061 on a table leaf, and M = 130688 / 255 - 23 = 512 - 23 = 489. A 10,000-byte payload gives K = 489 + (9511 mod 4092) = 489 + 1327 = 1816. That is below X, so the leaf keeps 1,816 bytes and the remaining 8,184 bytes fill two overflow pages of 4,092 bytes each.

Design choices #

With the SQLite format the tools (the sqlite3 CLI, DB Browser) already exist, and the specification has been in use for over twenty years. It also answers a few design questions the other way from copy-on-write engines such as LMDB and sanakirja:

Feature	SQLite format	LMDB / sanakirja
Updates	In place	Copy-on-write, with lock-free readers
Range scans	Through the parent pages	Along leaf sibling pointers
Crash safety	Rollback journal or WAL	Atomic swap of the root pointer

What you pay for the SQLite tools is throughput under concurrent load. Pages are updated in place, so a reader cannot go on reading a page that a writer is rewriting. Readers and the writer either lock each other out or go through a write-ahead log (WAL), which holds new pages until a checkpoint copies them into the file. A copy-on-write tree writes every changed page to a fresh location and then swaps one root pointer, and a reader that started from the old root keeps seeing a consistent tree without waiting.

SQLite file format: the specification this library implements.
ocaml-sqlite: the database layer built on this library (KV API, named tables, schema).
LMDB: a C B+tree with memory-mapped copy-on-write.
sanakirja: a Rust copy-on-write B-tree, used by Pijul.
bbolt: a Go B+tree, used by etcd.
Limbo: a Rust reimplementation of SQLite.

Licence #

ISC. See LICENSE.md.

Clone this repository

btree #