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.
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).
func (*Index[V]) Cardinality ¶
Cardinality returns the number of NodeIDs associated with value.
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.
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).
func (*Index[V]) DistinctValues ¶
DistinctValues returns the number of distinct values currently indexed.
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.
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. The returned bitmap is freshly allocated; the caller owns 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.
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