index

Documentation

Overview

Package index holds the membership filters and the page-index layout a tatami file carries to skip data it does not need to read. The structures here are self-contained: they take and return bytes and never import the root package, so the writer and reader compose them without a cycle.

The bloom filter is the classic Kirsch-Mitzenmacher double-hashing construction from kv's lsm/bloom.go, frozen so a filter written by one build reads identically in the next. A negative answer is definitive, which is the one-sided guarantee the read path leans on: a row group whose filter says no is skipped without touching a data page.

Index

• Constants
• type Bloom
  • func BuildBloom(keys [][]byte, bitsPerKey int) *Bloom
  • func LoadBloom(raw []byte) (*Bloom, error)
  • func (b *Bloom) Encode() []byte
  • func (b *Bloom) MayContain(key []byte) bool

Constants

const BloomBitsPerKey = 10

BloomBitsPerKey is the default budget. Ten bits per key gives k = 7 probes and roughly a one percent false-positive rate, the same default kv ships.

Types

type Bloom

type Bloom struct {
	// contains filtered or unexported fields
}

Bloom is a built filter over a set of keys. The zero value is not usable; build one with BuildBloom or load one with LoadBloom.

func BuildBloom

func BuildBloom(keys [][]byte, bitsPerKey int) *Bloom

BuildBloom builds a filter over keys at the given bits-per-key budget. Passing bitsPerKey <= 0 uses BloomBitsPerKey. An empty key set yields a tiny filter that rejects everything, which is the correct answer for an empty group.

func LoadBloom

func LoadBloom(raw []byte) (*Bloom, error)

LoadBloom parses a filter encoded by Encode.

func (*Bloom) Encode

func (b *Bloom) Encode() []byte

Encode serializes the filter: k (u32 LE), nbits (u32 LE), then the bit array.

func (*Bloom) MayContain

func (b *Bloom) MayContain(key []byte) bool

MayContain reports whether key might be in the set. False is definitive; true may be a false positive at the configured rate.