Documentation
¶
Overview ¶
Package filter defines and implements data structures and interfaces for skipping index.
Index ¶
- Constants
- func OptimalBitsSize(n int) int
- type BloomFilter
- func (bf *BloomFilter) Add(item []byte) bool
- func (bf *BloomFilter) Bits() []uint64
- func (bf *BloomFilter) ContainsAll(items [][]byte) bool
- func (bf *BloomFilter) MightContain(item []byte) bool
- func (bf *BloomFilter) N() int
- func (bf *BloomFilter) Reset()
- func (bf *BloomFilter) ResizeBits(n int)
- func (bf *BloomFilter) SetBits(bits []uint64)
- func (bf *BloomFilter) SetN(n int)
- type DictionaryFilter
Constants ¶
const ( // B specifies the number of bits allocated for each item. // Using B=16 (power of 2) maintains memory alignment and enables shift-based math. // With 8k items per block: memory = 8192 * 16 / 8 = 16KB per block. // FPR with k=10, B=16: ~0.042%. B = 16 )
Variables ¶
This section is empty.
Functions ¶
func OptimalBitsSize ¶
OptimalBitsSize returns the optimal number of uint64s needed for n items. With B=16, this is simply n/4 (n >> 2), with a minimum of 1.
Types ¶
type BloomFilter ¶
type BloomFilter struct {
// contains filtered or unexported fields
}
BloomFilter is a probabilistic data structure designed to test whether an element is a member of a set.
func NewBloomFilter ¶
func NewBloomFilter(n int) *BloomFilter
NewBloomFilter creates a new Bloom filter with the number of items n and false positive rate p.
func (*BloomFilter) Add ¶
func (bf *BloomFilter) Add(item []byte) bool
Add adds an item to the Bloom filter.
func (*BloomFilter) Bits ¶
func (bf *BloomFilter) Bits() []uint64
Bits returns the underlying bitset.
func (*BloomFilter) ContainsAll ¶ added in v0.10.0
func (bf *BloomFilter) ContainsAll(items [][]byte) bool
ContainsAll checks if all items might be in the Bloom filter. Returns true only if ALL items might be present (subject to false positives).
func (*BloomFilter) MightContain ¶
func (bf *BloomFilter) MightContain(item []byte) bool
MightContain checks if an item might be in the Bloom filter.
func (*BloomFilter) ResizeBits ¶
func (bf *BloomFilter) ResizeBits(n int)
ResizeBits resizes the underlying bitset.
func (*BloomFilter) SetBits ¶
func (bf *BloomFilter) SetBits(bits []uint64)
SetBits sets the underlying bitset.
type DictionaryFilter ¶ added in v0.10.0
type DictionaryFilter struct {
// contains filtered or unexported fields
}
DictionaryFilter is a filter implementation backed by a dictionary. For non-array types: uses linear iteration through values. For array types: uses iterative approach, extracting and sorting on-the-fly.
func (*DictionaryFilter) ContainsAll ¶ added in v0.10.0
func (df *DictionaryFilter) ContainsAll(items [][]byte) bool
ContainsAll checks if all items are present. For non-array types: returns true only if ALL items exist as dictionary values (AND semantics). For array types: returns true only if ALL items form a subset of ANY stored array (AND semantics).
func (*DictionaryFilter) MightContain ¶ added in v0.10.0
func (df *DictionaryFilter) MightContain(item []byte) bool
MightContain checks if an item is in the dictionary. For non-array types: linear iteration through values. For array types: checks if the single item exists as an element in any stored array.
func (*DictionaryFilter) Reset ¶ added in v0.10.0
func (df *DictionaryFilter) Reset()
Reset resets the dictionary filter.
Source Files