mini\Table\Index\TreapIndex final class

Documentation

Hybrid hash/sorted-array/treap index optimized for real-world access patterns.

Three stages based on usage:

  1. Hash only: eq() lookups, no range yet
  2. Sorted array: first range() called, assume no more inserts
  3. Treap: insert after range, convert sorted→treap once, stay in treap

This avoids merge overhead by using only one structure at a time for range().

Inheritance

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

Constants (3)

Name Value
MODE_HASH 0
MODE_SORTED 1
MODE_TREAP 2

Properties (4)

private array $hash
private int $mode
private ?array $sorted
private ?mini\Table\Index\TreapNode $treap

Methods (21)

public static fromGenerator()

Build index from a generator function.

public static fromArray()

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

public insert()

Documentation missing

public delete()

Documentation missing

public has()

Documentation missing

public eq()

Documentation missing

public count()

Count rowIds for a specific key.

public keyCount()

Count unique keys.

public rowCount()

Count total rowIds across all keys.

public clear()

Clear all data from the index.

public countRange()

Count rowIds in a range.

public range()

Documentation missing

private convertToTreap()

Convert sorted array to treap (called on first insert after range).

private buildBalanced()

Build balanced treap from sorted keys.

private sortedRange()

Documentation missing

private lowerBound()

Documentation missing

private upperBound()

Documentation missing

private treapInsert()

Documentation missing

private treapRangeWithBlobs()

Treap range with blob yielding (iterative, strict pruning).

private rotateRight()

Documentation missing

private rotateLeft()

Documentation missing

Source

src/Table/Index/TreapIndex.php:16-402