filter

Documentation

Overview

Package filter provides interface and implementation of probabilistic data structure.

The filter is resposible for creating small filter from a set of keys. These filter will then used to test whether a key is a member of the set. In many cases, a filter can cut down the number of disk seeks from a handful to a single disk seek per DB.Get call.

Index

• type Buffer
• type Filter
  • func NewBloomFilter(bitsPerKey int) Filter
• type FilterGenerator

Types

type Buffer

type Buffer interface {
	// Alloc allocs n bytes of slice from the buffer. This also advancing
	// write offset.
	Alloc(n int) []byte

	// Write appends the contents of p to the buffer.
	Write(p []byte) (n int, err error)

	// WriteByte appends the byte c to the buffer.
	WriteByte(c byte) error
}

Buffer is the interface that wraps basic Alloc, Write and WriteByte methods.

type Filter

type Filter interface {
	// Name returns the name of this policy.
	//
	// Note that if the filter encoding changes in an incompatible way,
	// the name returned by this method must be changed. Otherwise, old
	// incompatible filters may be passed to methods of this type.
	Name() string

	// NewGenerator creates a new filter generator.
	NewGenerator() FilterGenerator

	// Contains returns true if the filter contains the given key.
	//
	// The filter are filters generated by the filter generator.
	Contains(filter, key []byte) bool
}

Filter is the filter.

func NewBloomFilter

func NewBloomFilter(bitsPerKey int) Filter

NewBloomFilter creates a new initialized bloom filter for given bitsPerKey.

Since bitsPerKey is persisted individually for each bloom filter serialization, bloom filters are backwards compatible with respect to changing bitsPerKey. This means that no big performance penalty will be experienced when changing the parameter. See documentation for opt.Options.Filter for more information.

type FilterGenerator

type FilterGenerator interface {
	// Add adds a key to the filter generator.
	//
	// The key may become invalid after call to this method end, therefor
	// key must be copied if implementation require keeping key for later
	// use. The key should not modified directly, doing so may cause
	// undefined results.
	Add(key []byte)

	// Generate generates filters based on keys passed so far. After call
	// to Generate the filter generator maybe resetted, depends on implementation.
	Generate(b Buffer)
}

FilterGenerator is the filter generator.