Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Catalog · How the catalog works

Random project

arborix

View on GitHub

Anyone may press Interesting, signed in or not. It helps others find this project.

Member rating

No ratings yet.

Sign in to rate this project.

README

arborix

An embeddable on-disk B+tree index for Free Pascal / Delphi.

arborix provides a small, dependency-free key/value index with the properties you would expect from a serious storage engine:

  • Variable-length binary keys (up to 1023 bytes) and values (up to 64 KiB).
  • A buffer pool with clock-style replacement and write-back.
  • A redo write-ahead log with CRC32 framing and crash recovery.
  • Range scans that follow leaf sibling links.
  • Bulk-load mode for sorted input.

It targets Free Pascal 3.2+ and Delphi 11+, on 32-bit and 64-bit targets.

Quick start

pascal
uses arborix;

var
  Idx: TArborixIndex;
  V:   TBytes;
begin
  Idx := TArborixIndex.Create;
  try
    Idx.Open('catalog.aix', [aoCreate, aoSync]);
    Idx.Put(BytesOf('sku-00417'), BytesOf('widget'));
    if Idx.Get(BytesOf('sku-00417'), V) then
      Writeln(StringOf(V));
    Idx.Commit;
  finally
    Idx.Free;
  end;
end;

Layout

Unit Purpose
arborix.pas Public API (Open/Close/Get/Put/Delete/Range/Commit).
arborix.types.pas Shared records, page layout, error codes.
arborix.pager.pas File I/O, buffer pool, free list.
arborix.btree.pas Node search, split, merge, range cursor.
arborix.wal.pas Write-ahead log writer and replayer.
arborix.crc.pas CRC32 (IEEE 802.3 polynomial).

File format

A database file is a sequence of fixed-size pages (default 4096 bytes). Page 0 holds the superblock; pages 1..N are tree nodes, free-list pages, or overflow pages. The WAL is kept in a sibling file <name>.wal and is truncated on a clean shutdown.

Building

pascal
make            # builds libarborix.a and the test binary
make test

License

MIT.