Documentation
¶
Overview ¶
Package btree provides an order-preserving property index over a constraints.Ordered value type, answering range predicates against the NodeIDs that carry each value.
The implementation is a cache-friendly in-memory B+ tree (task #1514): all (value, NodeID-set) data lives in the leaves and internal nodes hold separator keys + child pointers. Insert and Delete of a distinct key are O(log n); point reads (Lookup, Cardinality) are O(log n); a range scan is O(log n + k) over the k keys it spans; and Index.BulkLoad builds the tree bottom-up in O(n) from sorted input. This replaces the original sorted-array index, whose per-key Insert and Delete were O(n) (an array shift) — the win is on write-heavy indexed workloads while every read path keeps its prior complexity. The tree internals live in bplus.go.
Concurrency ¶
Every operation is safe for concurrent use by any number of goroutines, and NO read path takes a lock on the tree (task #2683).
The tree is an IMMUTABLE snapshot published through an atomic.Pointer. A read performs one atomic load and then traverses the snapshot with no synchronisation at all; nothing it can reach will ever change shape underneath it. A structural write — creating or destroying a key — copies the root-to-leaf path, leaves every off-path node shared, and publishes the new spine with one atomic store, serialised against other structural writes by a mutex that no reader ever acquires. Adding or removing a NodeID under an EXISTING key touches no tree node at all: it takes only that key's own lock, so two writers on different keys never interact and a writer never blocks a reader of another key.
This is the Lehman & Yao premise restored. PostgreSQL's own B-tree README (REL_17_2, src/backend/access/nbtree/README lines 63-68) records why it could not use it: "Lehman and Yao don't require read locks, but assume that in-memory copies of tree pages are unshared. Postgres shares in-memory buffers among backends. As a result, we do page-level read locking on btree pages in order to guarantee that no record is modified while we are examining it. This reduces concurrency but guarantees correct behavior." A copy-on-write snapshot makes the pages a reader examines genuinely unshared with any writer, so the read lock that assumption forced is not needed here.
What a scan guarantees:
- The KEY SET a scan observes is snapshot-atomic. It is exactly the set of keys the index held at the instant of the scan's atomic load: a concurrent structural write can neither add a key to a scan already in flight nor take one away from it, and a scan can never observe a half-applied split or a detached node.
- Each key's NodeID set is read at the instant the scan REACHES that key, not all at one instant. A multi-key scan (Index.Range, Index.RangeFrom, Index.RangeCount, Index.RangeCountFrom, Index.Serialize) is therefore not a point-in-time image of the node sets, and may mix a node added under an early key before the scan started with one added under a late key after it started.
- SINGLE-key operations (Index.Lookup, Index.LookupAppend, Index.Cardinality, Index.RangeFirst) ARE atomic with respect to that key's node set: they hold the key's lock while reading it.
The per-key relaxation is sound for both consumers in this module, and both were verified rather than assumed:
- cypher/exec/scan_index_btree.go documents the range result as an inclusive SUPERSET and stacks a MANDATORY residual predicate Filter that re-checks the property against the live node, so a stale or early NodeID is rejected there, exactly as an out-of-interval one already is.
- Index.Serialize's only production caller is the checkpointer, which drains store writers to zero before opening its capture instant (store/checkpoint). Serializing a concurrently mutating index is outside that contract.
The index provides index-internal isolation only; transaction isolation across multiple calls is the engine's responsibility.
Index.BulkLoad, Index.BulkLoadSorted and Index.Deserialize REPLACE the whole index rather than editing it. They publish a tree of brand-new entries, so a concurrent Insert or Delete that had already resolved a key against the outgoing tree writes to an entry the new tree does not contain and is lost. They are load-time operations — backfill before registration, snapshot recovery — and every caller in this module runs them before the index is shared; callers must not race them against index maintenance.
Key ordering ¶
Keys are ordered by the TOTAL order of cmp.Compare / cmp.Less, not by the raw < operator. The two orders agree everywhere except IEEE 754 NaN: under the total order a floating-point NaN key is less than every other value (including math.Inf(-1)), every NaN bit pattern compares equal to every other NaN, and ±0.0 are one key. Raw < is only a partial order over floats — every comparison with NaN is false — so a single NaN insert used to break the monotone predicate that sort.Search requires and silently corrupted the index for ordinary keys (task #1354). With the total order the sorted invariant holds for every representable input: NaN is a regular, deduplicated key that Lookup/Delete address and that no range with a non-NaN lower bound ever returns.
Index ¶
- Variables
- type Binding
- type Index
- func (i *Index[V]) Apply(c index.Change)
- func (i *Index[V]) ApplyInState(c index.Change, st index.NodeState)
- func (i *Index[V]) ApplyResolved(c index.Change, current any, eligible bool)
- func (i *Index[V]) BoundNode() (label, property string, ok bool)
- func (i *Index[V]) BulkLoad(values []V, nodes []graph.NodeID) error
- func (i *Index[V]) BulkLoadSorted(values []V, nodes []graph.NodeID) error
- func (i *Index[V]) Cardinality(value V) uint64
- func (i *Index[V]) Concerns(c index.Change) bool
- func (i *Index[V]) Delete(value V, node graph.NodeID)
- func (i *Index[V]) Deserialize(r io.Reader) error
- func (i *Index[V]) DistinctValues() int
- func (i *Index[V]) Insert(value V, node graph.NodeID)
- func (*Index[V]) Kind() string
- func (i *Index[V]) Lookup(value V) *roaring64.Bitmap
- func (i *Index[V]) LookupAppend(value V, dst []uint64) []uint64
- func (i *Index[V]) Range(lo, hi V) *roaring64.Bitmap
- func (i *Index[V]) RangeCount(lo, hi V, budget uint64) (count uint64, exact bool)
- func (i *Index[V]) RangeCountFrom(lo V, budget uint64) (count uint64, exact bool)
- func (i *Index[V]) RangeFirst(lo, hi V) (V, graph.NodeID, bool)
- func (i *Index[V]) RangeFrom(lo V) *roaring64.Bitmap
- func (i *Index[V]) Serialize(w io.Writer) error
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrMismatchedLengths = errors.New("btree: values and nodes slices must have the same length")
ErrMismatchedLengths is returned by Index.BulkLoad when the values and nodes slices supplied to it do not share a common length. Before sprint 21 this condition panicked; the error returned here lets callers handle it as a recoverable input validation failure.
var ErrNotSorted = errors.New("btree: values must be in ascending order for BulkLoadSorted")
ErrNotSorted is returned by Index.BulkLoadSorted when the values slice is not in ascending total order, so the caller's pre-sorted precondition is violated. It is a recoverable input-validation failure; the index is left untouched.
Functions ¶
This section is empty.
Types ¶
type Binding ¶ added in v0.3.1
type Binding[V cmp.Ordered] struct { // Project converts a Change.OldValue / Change.NewValue payload to the // index key type. ok is false when the payload is absent or not indexable // (wrong kind), in which case the event is skipped for that direction. Project func(v any) (V, bool) // Eligible reports whether the node should currently be present in the // index: it must be live (not deleted) and carry the bound label, // evaluated against the graph's final state. Eligible func(node graph.NodeID) bool // CurrentValue returns the node's current value for the bound property, // projected to the key type. ok is false when the node is not live, lacks // the property, or the value is not indexable. It is consulted on label // add/remove events, which carry no property payload. CurrentValue func(node graph.NodeID) (V, bool) // Label and Property are the source names behind PropertyID and LabelID. // They let a query planner match the index against a (label, property) // predicate without access to the registries. Label, Property string // PropertyID is the interned property-key identifier this index covers. // Property changes whose Change.Property differs are ignored. PropertyID uint32 // LabelID is the interned label identifier this index is scoped to. // Label changes whose Change.Label differs are ignored. LabelID uint32 }
Binding ties an Index to a single (label, property) pair of a live node graph. The shape mirrors hash.Binding so the engine's CREATE INDEX wiring can build either kind from the same closures. Because changes are fanned out at commit time — after the transaction's mutations were applied eagerly to the graph — the callbacks observe the transaction's FINAL state, which is exactly the state the index must converge to.
type Index ¶
Index is an order-preserving property index keyed by V, backed by an in-memory B+ tree (see bplus.go). It is safe for concurrent use by any number of goroutines; see the Concurrency section of the package documentation for exactly what a concurrent scan observes.
Example ¶
ExampleIndex shows an order-preserving property index keyed by an ordered value type: insert (value, NodeID) pairs, then read back the NodeIDs carrying one exact value and the half-open count of distinct values.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/btree"
)
func main() {
// An index over an integer "age" property.
idx := btree.New[int]()
idx.Insert(30, graph.NodeID(1))
idx.Insert(25, graph.NodeID(2))
idx.Insert(30, graph.NodeID(3)) // same value, different node
// Lookup returns the NodeID set carrying exactly age == 30.
bm := idx.Lookup(30)
fmt.Println("age==30 nodes:", bm.ToArray())
fmt.Println("age==30 cardinality:", idx.Cardinality(30))
fmt.Println("distinct ages:", idx.DistinctValues())
}
Output: age==30 nodes: [1 3] age==30 cardinality: 2 distinct ages: 2
func NewBound ¶ added in v0.3.1
NewBound returns an empty B+tree index bound to b. Unlike New, the returned index has a functional Index.Apply: it subscribes to the node property and label changes selected by b and keeps itself consistent with the graph. Returns an error when b is missing its Label, Property, or any of the three callbacks.
func (*Index[V]) Apply ¶
Apply maintains a bound index (see NewBound) from the index.Manager change fan-out; it is a no-op for an unbound index (see New), which cannot reliably interpret arbitrary index.Change values without the caller-supplied binding (property key + value-type coercion). The bound rules live in [Index.applyBound] (bound.go).
func (*Index[V]) ApplyInState ¶ added in v0.16.0
ApplyInState applies c resolving the node's eligibility and current value from st, the state the committing transaction produces, instead of from the binding's own reads of the graph's present — index.StateApplier. It shares [Index.applyBound] with Index.Apply and Index.ApplyResolved, so the three rule sets cannot drift, and it is a no-op for an unbound index or for a change that does not concern the binding (rmp #2931).
func (*Index[V]) ApplyResolved ¶ added in v0.14.1
ApplyResolved applies a change RECORDED DURING THIS INDEX'S BUILD, taking the node state from the recording instead of reading it back off the graph — index.ResolvedApplier. It mirrors hash.Index.ApplyResolved, shares [Index.applyBound] with Index.Apply so the two rule sets cannot drift, and is a no-op for an unbound index for the same reason Apply is. See index.ResolvedApplier for the defect it closes (rmp #2793).
func (*Index[V]) BoundNode ¶ added in v0.3.1
BoundNode returns the (label, property) pair this index is bound to, with ok reporting whether the index is bound at all. Query planners use it to decide whether the index may serve a predicate: a bound index covers exactly its (label, property) pair, while an unbound index carries no coverage metadata and must NOT be served by a range seek (it is never maintained from the fan-out).
func (*Index[V]) BulkLoad ¶
BulkLoad replaces the contents of the index with the given (value, node) pairs in O(n log n) time. The pairs slice is left untouched. Calling BulkLoad on a non-empty index discards previous data. Returns ErrMismatchedLengths when len(values) != len(nodes). Values are sorted and deduplicated under the total order described in the package documentation, so NaN inputs collapse into one leading entry instead of corrupting (or, before task #1354, hanging) the load.
func (*Index[V]) BulkLoadSorted ¶ added in v0.6.0
BulkLoadSorted is Index.BulkLoad for input already in ascending total order — the order Index.Serialize emits and the snapshot stores. It skips the copy-into-pairs and the sort that BulkLoad performs, so a pre-sorted load (e.g. snapshot recovery) avoids that throwaway O(n) materialization. Equal keys must be adjacent (guaranteed by ascending order) and their nodes are unioned into one entry, exactly as BulkLoad does, so for the same data the resulting tree is identical.
It returns ErrMismatchedLengths when the lengths differ and ErrNotSorted when values is not ascending. The order precondition is checked by a cheap allocation-free scan, so a mis-sorted input is rejected rather than silently building a corrupt tree.
func (*Index[V]) Cardinality ¶
Cardinality returns the number of NodeIDs associated with value, matched under the total order (see Index.Lookup).
func (*Index[V]) Concerns ¶ added in v0.16.0
Concerns reports whether applying c could modify this index — index.ChangeFilter. It is false for an unbound index, whose Apply is a no-op, and for any change whose property or label is not the binding's.
func (*Index[V]) Delete ¶
Delete removes node from the set associated with value. No-op when absent. The (value, node-set) entry is removed when its set becomes empty, and a leaf that becomes entirely empty is dropped from the tree (see the delete policy in bplus.go). Like Index.Insert, value is matched under the total order, so Delete addresses a NaN-keyed entry.
Removing a node that does not empty the key's set takes no lock but that key's own; emptying the set falls through to the structural detach, which is serialised across the whole index.
func (*Index[V]) Deserialize ¶
Deserialize replaces the receiver's state with the contents of r. Because the writer dumps entries in ascending key order, the reader can build the sorted entries slice directly without an extra sort pass; the loader is therefore O(n) instead of Index.BulkLoad's O(n log n).
Keys must be STRICTLY ascending under the cmp.Compare total order — the only shape Index.Serialize produces. A payload that violates it fails fail-stop with index.ErrIndexCorrupted rather than load an index whose binary searches would silently miss live keys. In particular, a float64 payload written before the total-order fix (task #1354) that carries a NaN key after a real key, or duplicate NaN entries, is rejected; the index is derived data, so the caller recovers by rebuilding it from the primary graph. A single NaN entry in the leading position is the legitimate post-fix encoding and loads normally.
index deserialize: header + per-entry decode + per-step bounds checks
func (*Index[V]) DistinctValues ¶
DistinctValues returns the number of distinct values currently indexed. It is O(1) and takes no lock at all: the count is a field of the published snapshot, which the tree maintains as it is built.
func (*Index[V]) Insert ¶
Insert records that node carries value. Keys follow the total order described in the package documentation, so a floating-point NaN is a valid key: it sorts before every other value and all NaN bit patterns share one entry. Inserting a new distinct key is O(log n).
Adding a node to a key the index ALREADY holds takes no lock but that key's own: it does not touch the tree and does not exclude a writer on any other key. Creating a new key falls through to the structural path, which is serialised across the whole index.
func (*Index[V]) Kind ¶
Kind returns "btree" — satisfies index.Subscriber.
func (*Index[V]) Lookup ¶
Lookup returns a clone of the bitmap associated with value, or an empty bitmap when value is unknown. Matching uses the total order, so Lookup(NaN) returns the NaN entry when one exists.
func (*Index[V]) LookupAppend ¶ added in v0.6.0
LookupAppend appends the NodeIDs associated with value to dst and returns the extended slice — the allocation-light equivalent of Index.Lookup for callers that iterate the result once, the dominant equality-seek shape. A singleton or small posting list appends straight from the set's inline fields with no heap allocation when dst has spare capacity (e.g. a reused seek buffer), where Lookup clones (or materialises) a full roaring bitmap. Only a promoted bitmap entry allocates a single iterator.
Matching uses the total order, so LookupAppend(NaN) appends the NaN entry when one exists, exactly as Index.Lookup returns it. An unknown value appends nothing. The appended ids are an independent snapshot the caller may iterate after the call returns, with the same ownership as Lookup's clone.
func (*Index[V]) Range ¶
Range returns a Roaring bitmap that is the union of the per-value bitmaps for every key v with lo <= v <= hi under the total order. The returned bitmap is freshly allocated; the caller owns it. A NaN key is below every other value, so any range with a non-NaN lo — including Range(math.Inf(-1), math.Inf(1)) — never returns it.
Example ¶
ExampleIndex_Range shows an inclusive range predicate [lo, hi]: Range returns every NodeID whose value satisfies lo <= v <= hi, and RangeFirst returns the smallest matching value together with one of its NodeIDs (the order-preserving property the index exists for).
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/btree"
)
func main() {
idx := btree.New[int]()
if err := idx.BulkLoad(
[]int{10, 20, 30, 40},
[]graph.NodeID{1, 2, 3, 4},
); err != nil {
fmt.Println("bulk load:", err)
return
}
// Range is inclusive on both ends: [20, 40] selects 20, 30 and 40.
bm := idx.Range(20, 40)
fmt.Println("nodes in [20,40]:", bm.ToArray())
v, node, ok := idx.RangeFirst(20, 40)
fmt.Printf("first in [20,40]: value=%d node=%d ok=%t\n", v, node, ok)
}
Output: nodes in [20,40]: [2 3 4] first in [20,40]: value=20 node=2 ok=true
func (*Index[V]) RangeCount ¶ added in v0.3.1
RangeCount returns the exact number of NodeIDs whose value falls within the inclusive interval [lo, hi] under the total order, but stops accumulating as soon as the running total exceeds budget and returns (budget+1, false) — the caller learns only that the count is "more than budget" without paying to walk the whole range. When the full count is ≤ budget it is returned with exact == true.
The entries are pairwise-disjoint node-sets (each node carries exactly one value for the property), so the sum of per-entry cardinalities equals the union cardinality exactly, with no allocation and no union materialisation (graph-theory-expert, #1505). The early-exit bounds the gate cost to O(budget) cardinality probes regardless of how many distinct values the range spans, which keeps a non-selective range cheap to reject.
func (*Index[V]) RangeCountFrom ¶ added in v0.8.0
RangeCountFrom returns the exact number of NodeIDs whose value is >= lo under the total order (no upper bound), with the same early-exit-at-budget contract as Index.RangeCount. It is the open-ended counterpart used by the unbounded-above selectivity gate so the count and the executed Index.RangeFrom scan agree on the same key space (#F-CY1).
func (*Index[V]) RangeFirst ¶
RangeFirst returns the first NodeID in the smallest indexed value not less than lo and not greater than hi, plus that value. The second return value reports whether any match exists. It is the allocation-free way to peek the first row of a range scan; the full union of matches is available via Index.Range. Bounds compare under the total order, so lo = NaN admits a NaN key while any non-NaN lo excludes it.
The value and NodeID returned are read together under that key's own lock, so they are a consistent pair even under concurrent writes.
func (*Index[V]) RangeFrom ¶ added in v0.8.0
RangeFrom returns a Roaring bitmap that is the union of the per-value bitmaps for every key v with lo <= v under the total order, with NO upper bound — it scans from lo to the largest key present. It is the open-ended counterpart of Index.Range for an unbounded-above predicate (e.g. a string range n.name >= 'A'), where no finite sentinel key is a true maximum: a variable-length key type such as string has no representable greatest value, so capping the scan at any fixed key would silently exclude every key sorting above it. Scanning to the last leaf is the only superset-complete way to serve an unbounded-above range (#F-CY1). A NaN key is below every other value (see Index.Range); a non-NaN lo therefore never returns it.
The returned bitmap is freshly allocated; the caller owns it.
func (*Index[V]) Serialize ¶
Serialize writes every (value, NodeID-set) pair in key order to w. The on-disk layout is:
uint32 magic ('SBTR')
uint32 formatVersion
uint64 entryCount
repeat entryCount times:
uint32 keyLen
[keyLen]byte key (kind-specific encoding)
uint64 idCount
[idCount]uint64 NodeIDs (sorted ascending)
uint32 crc32c (little-endian)
Writing in key order lets [Deserialize] use Index.BulkLoad indirectly: the reader appends one entry at a time and the sorted order is preserved.
Source Files