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, internal nodes hold separator keys + child pointers, and leaves are singly linked low→high for forward range scans. 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.
All operations are safe for concurrent use; a single sync.RWMutex guards the tree for the whole duration of each operation. Because the mutex fully excludes a writer's split/unlink from any in-flight reader, a reader can never observe a half-applied split or a dangling leaf. The mutex provides index-internal isolation only; transaction isolation across multiple calls is the engine's responsibility.
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]) 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]) 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).
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]) 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]) Delete ¶
Delete removes node from the set associated with value. No-op when absent. The (value, bitmap) entry is removed when its bitmap becomes empty, and a leaf that becomes entirely empty is unlinked (see the delete policy in bplus.go). Like Index.Insert, value is matched under the total order, so Delete addresses a NaN-keyed entry.
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.
func (*Index[V]) DistinctValues ¶
DistinctValues returns the number of distinct values currently indexed. It is O(1): the tree maintains a running key count.
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).
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.
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