Documentation
¶
Overview ¶
Package hash provides a sharded hash index from arbitrary comparable property values to the set of NodeIDs that carry them, represented as a 64-bit Roaring bitmap.
The structure answers exact-match property predicates (for example "every node where email == 'x@y.com'") in O(1) average time. For range predicates use the B+ tree index in package github.com/FlavioCFOliveira/GoGraph/graph/index/btree (Sprint 2, T19).
Index is safe for concurrent use by any number of goroutines; the shard sharding aligns with graph.NodeID's low-bit shard scheme.
Index ¶
- type Index
- func (*Index[V]) Apply(index.Change)
- func (i *Index[V]) Cardinality(value V) uint64
- func (i *Index[V]) Contains(value V, node graph.NodeID) 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() uint64
- 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]) Serialize(w io.Writer) error
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Index ¶
type Index[V comparable] struct { // contains filtered or unexported fields }
Index maps property values of type V to the NodeIDs that carry them.
Example ¶
ExampleIndex shows a hash index answering an exact-match property predicate: insert (value, NodeID) pairs keyed by a string property, then read back the NodeID set carrying one exact value.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/hash"
)
func main() {
// An index over a string "email domain" property.
idx := hash.New[string]()
idx.Insert("example.com", graph.NodeID(1))
idx.Insert("example.org", graph.NodeID(2))
idx.Insert("example.com", graph.NodeID(3))
// Lookup answers "every node where domain == example.com".
bm := idx.Lookup("example.com")
fmt.Println("example.com nodes:", bm.ToArray())
fmt.Println("example.com cardinality:", idx.Cardinality("example.com"))
fmt.Println("distinct domains:", idx.DistinctValues())
}
Output: example.com nodes: [1 3] example.com cardinality: 2 distinct domains: 2
func (*Index[V]) Apply ¶
Apply is a no-op for the generic hash index. The Manager fans every change to every subscriber, but the hash index cannot reliably interpret arbitrary index.Change values without caller-supplied bindings (property key + value-type coercion). Callers that need automatic fan-out into a hash index should wrap the index in a thin shim that does the projection.
On recovery from a corrupted snapshot, the index is left empty; callers re-populate via Index.Insert from the live LPG.
func (*Index[V]) Cardinality ¶
Cardinality returns the number of NodeIDs associated with value. It is exposed for query planners to choose between index lookup and full-scan plans.
func (*Index[V]) Contains ¶
Contains reports whether node is in the set associated with value. Faster than Lookup when only existence matters.
Example ¶
ExampleIndex_Contains shows the point-membership query: Contains reports whether one specific NodeID carries a given value, without materialising the whole NodeID set.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph"
"github.com/FlavioCFOliveira/GoGraph/graph/index/hash"
)
func main() {
idx := hash.New[int]()
idx.Insert(404, graph.NodeID(7))
fmt.Println("node 7 has 404:", idx.Contains(404, graph.NodeID(7)))
fmt.Println("node 8 has 404:", idx.Contains(404, graph.NodeID(8)))
// Delete removes one membership; the value disappears once its last
// NodeID is gone.
idx.Delete(404, graph.NodeID(7))
fmt.Println("node 7 has 404 after delete:", idx.Contains(404, graph.NodeID(7)))
}
Output: node 7 has 404: true node 8 has 404: false node 7 has 404 after delete: false
func (*Index[V]) Deserialize ¶
Deserialize replaces the receiver's state with the contents of r. Returns index.ErrIndexCorrupted on structural or CRC errors and index.ErrIndexValueTypeUnsupported when V cannot be decoded.
func (*Index[V]) DistinctValues ¶
DistinctValues returns the number of distinct values currently indexed. Exposed for cardinality estimation by the query planner.
func (*Index[V]) Kind ¶
Kind returns "hash" — satisfies index.Subscriber.
func (*Index[V]) Lookup ¶
Lookup returns a clone of the Roaring bitmap of NodeIDs that carry the given value, or an empty bitmap when the value is unknown. Clone avoids returning the live bitmap to the caller, which could otherwise be mutated by concurrent writers.
func (*Index[V]) Serialize ¶
Serialize writes every (value, NodeID-set) pair currently in the index to w in the format documented in docs/persistence.md:
uint32 magic ('SHSH')
uint32 formatVersion
uint64 entryCount
repeat entryCount times:
uint32 valueLen
[valueLen]byte value (kind-specific encoding)
uint64 idCount
[idCount]uint64 NodeIDs (sorted ascending)
uint32 crc32c (little-endian, covers every byte above)
Returns index.ErrIndexValueTypeUnsupported when V is not one of the documented supported types.
Source Files