Documentation
¶
Overview ¶
Package hash provides a HTree implementation to provide key-value storage functionality for a StorageManager.
The HTree provides a persistent hashtable. Storing values in buckets on pages as the tree gorws. It is not possible to store nil values. Storing a nil value is equivalent to removing a key.
As the tree grows each tree level contains pages with links to underlying pages. The last link is always to a bucket. The default tree has 4 levels each with 256 possible children. A hash code for the tree has 32 bits = 4 levels * 8 bit.
Hash buckets are on the lowest level of the tree and contain actual keys and values. The object stores multiple keys and values if there are hash collisions. In a sparsely populated tree buckets can also be found on the upper levels.
Iterator ¶
Entries in the HTree can be iterated by using an HTreeIterator. The HTree may change behind the iterator's back. The iterator will try to cope with best effort and only report an error as a last resort.
Hash function ¶
The HTree uses an implementation of Austin Appleby's MurmurHash3 (32bit) function as hash function.
Reference implementation: http://code.google.com/p/smhasher/wiki/MurmurHash3
Index ¶
- Constants
- Variables
- func MurMurHashData(data []byte, offset int, size int, seed int) (uint32, error)
- type HTree
- func (t *HTree) Exists(key []byte) (bool, error)
- func (t *HTree) Get(key []byte) (interface{}, error)
- func (t *HTree) GetValueAndLocation(key []byte) (interface{}, uint64, error)
- func (t *HTree) Location() uint64
- func (t *HTree) Put(key []byte, value interface{}) (interface{}, error)
- func (t *HTree) Remove(key []byte) (interface{}, error)
- func (t *HTree) String() string
- type HTreeIterator
Constants ¶
const MaxBucketElements = 8
MaxBucketElements is the maximum umber of elements a bucket can contain before it is converted into a page except leaf buckets which grow indefinitely
const MaxPageChildren = 256
MaxPageChildren is the maximum of children per page - (stored in PageLevelBits bits)
const MaxTreeDepth = 3
MaxTreeDepth is the maximum number of non-leaf levels in the tree (i.e. the complete tree has a total of MAX_DEPTH+1 levels)
const PageLevelBits = 8
PageLevelBits is the number of significant bits per page level
Variables ¶
var ErrNoMoreItems = errors.New("No more items to iterate")
ErrNoMoreItems is assigned to LastError when Next() is called and there are no more items to iterate.
Functions ¶
func MurMurHashData ¶
MurMurHashData hashes a given array of bytes. This is an implementation of Austin Appleby's MurmurHash3 (32bit) function.
Reference implementation: http://code.google.com/p/smhasher/wiki/MurmurHash3
Types ¶
type HTree ¶
type HTree struct {
Root *htreePage // Root page of the HTree
// contains filtered or unexported fields
}
HTree data structure
func (*HTree) GetValueAndLocation ¶
GetValueAndLocation returns the value and the storage location for a given key.
type HTreeIterator ¶
type HTreeIterator struct {
LastError error // Last encountered error
// contains filtered or unexported fields
}
HTreeIterator data structure
func NewHTreeIterator ¶
func NewHTreeIterator(tree *HTree) *HTreeIterator
NewHTreeIterator creates a new HTreeIterator.
func (*HTreeIterator) HasNext ¶
func (it *HTreeIterator) HasNext() bool
HasNext returns if there is a next key / value pair.
func (*HTreeIterator) Next ¶
func (it *HTreeIterator) Next() ([]byte, interface{})
Next returns the next key / value pair.
func (*HTreeIterator) String ¶
func (it *HTreeIterator) String() string
Return a string representation of the iterator.
Source Files