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 v1 implementation is a sorted-array index — sufficient to meet the Sprint 2 acceptance criteria (sub-microsecond Range first- result on a 10^7-element index, multi-million-entry bulk-load in seconds). The public API is designed so that a future replacement with a fan-out-tuned B+ tree (or skip list) can land without breaking callers; per-key Insert is O(n) today and should be avoided on the hot path in favour of Index.BulkLoad.
All operations are safe for concurrent use; a single sync.RWMutex guards the array.
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 Index
- func (*Index[V]) Apply(index.Change)
- func (i *Index[V]) BulkLoad(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]) Range(lo, hi V) *roaring64.Bitmap
- func (i *Index[V]) RangeFirst(lo, hi V) (V, graph.NodeID, bool)
- 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.
Functions ¶
This section is empty.
Types ¶
type Index ¶
Index is an order-preserving property index keyed by V.
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 (*Index[V]) Apply ¶
Apply is a no-op for the generic B+ tree index. See the matching note on hash.Index.Apply — the index cannot auto-project arbitrary index.Change values without caller-supplied bindings.
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]) 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. 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.
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.
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]) 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]) 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]) 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