mini\Table\Index\BTreeIndex final class

Documentation

Append-only B-tree index with on-disk persistence.

File layout (4KB aligned pages):

  • Page 0: Header (64 bytes used, rest reserved for metadata)
  • Page 1+: B-tree nodes (internal and leaf)

Design:

  • Copy-on-write: pages never modified once written (except header)
  • Variable-length keys with offset arrays for O(log n) binary search within pages

TODO: Fully append-only design with separate log file

  • Main file: pages only, never overwritten
  • Log file: append-only sequence of [seq, root, checksum] entries
  • Commit: append pages, fsync, append log entry, fsync
  • Open: scan log from end for latest valid root
  • Removes header overwrites for better crash safety

Inheritance

Implements: mini\Table\Index\IndexInterface mini\Table\Index\HashIndexInterface

Constants (10)

Name Value
MAGIC 1112822345
VERSION 1
HEADER_SIZE 64
PAGE_SIZE 4096
MAX_KEY_LENGTH 4077
PAGE_INTERNAL 1
PAGE_LEAF 2
PAGE_INTERNAL_ROOT 129
PAGE_LEAF_ROOT 130
CRC_OFFSET 4092

Properties (13)

private mixed $file
private mixed $lockFile
private string $path
private int $rootPage
private int $nextPage
private int $sequence
private bool $inTransaction
private array $unwrittenPages
private int $unwrittenPageCount
private array $pageCache
private float $maxReadLatency
private float $lastRootRefresh

Methods (39)

public __construct()

Documentation missing

public static fromGenerator()

Build index from a generator function.

public static fromArray()

Build index from array of [key, rowId] pairs.

public __destruct()

Documentation missing

public begin()

Begin a transaction for bulk operations.

public commit()

Commit unwritten pages to disk.

public commitBulk()

Commit with bulk rebuild - use for initial loading only.

public rollback()

Rollback pending changes.

private splitOversizedPages()

Split any oversized pages before writing to disk.

private setParentReferences()

Set parent references on all pages in unwrittenPages by traversing from root.

private setParentReferencesRecursive()

Recursively set parent references on children.

public insert()

Documentation missing

public delete()

Documentation missing

public eq()

Documentation missing

public range()

Documentation missing

public has()

Documentation missing

public count()

Documentation missing

public close()

Documentation missing

public compact()

Documentation missing

private open()

Documentation missing

private writeFileHeader()

Write minimal file header (page 0) - just magic and version.

private writeRootWithCrc()

Write root page object with CRC marker (for new overlay approach).

private findLatestRoot()

Find the latest valid root page by scanning backwards from file end.

private refreshRootIfStale()

Documentation missing

private withWriteLock()

Documentation missing

private readPageRaw()

Read raw page from disk (no caching).

private getPage()

Load a page from unwritten overlay, cache, or disk.

private allocatePage()

Allocate a new page in the overlay. Returns the page number.

private getPageForWrite()

Get a page for modification. If from disk/cache, moves to overlay.

private releaseLeaf()

Release a leaf page back to pool, but only if it's not in the overlay.

private findChildIndex()

Find child index for given key in internal node.

private findPath()

Find path from root to leaf for given key.

private insertIntoTree()

Documentation missing

private propagateSplit()

Propagate a split up the tree.

private updatePath()

Update parent pointers after a child was replaced.

private deleteFromTree()

Documentation missing

private rangeForward()

Documentation missing

private rangeReverse()

Documentation missing

private rewritePages()

Recursively rewrite reachable pages to temp file.

Source

src/Table/Index/BTreeIndex.php:756-2294