bptree

README

bptree

on-disk bptree (b+ tree) data structure implementation. Code was copied and modified from this repository.

Documentation

Overview

Package bptree implements an on-disk bptree indexing scheme that can store key-value pairs and provide fast lookups and range scans. keys and values can be blobs binary data.

Index

• type BPlusTree
  • func Open(fileName string, opts *Options) (*BPlusTree, error)
  • func (tree *BPlusTree) AddSuffix(key [][]byte, flag suffixOption) [][]byte
  • func (tree *BPlusTree) CanInsert(key, suffix [][]byte) bool
  • func (tree *BPlusTree) CheckConsistency(list [][]byte) bool
  • func (tree *BPlusTree) ClearCache()
  • func (tree *BPlusTree) Close() error
  • func (tree *BPlusTree) Del(key, suffix [][]byte) (int, error)
  • func (tree *BPlusTree) DelMem(key, suffix [][]byte) (int, error)
  • func (tree *BPlusTree) Get(key, suffix [][]byte) ([][]byte, error)
  • func (tree *BPlusTree) IsUniq() bool
  • func (tree *BPlusTree) Options() Options
  • func (tree *BPlusTree) PrepareSpace(size uint32)
  • func (tree *BPlusTree) Print()
  • func (tree *BPlusTree) Put(key, suffix [][]byte, val []byte, opt PutOptions) (bool, error)
  • func (tree *BPlusTree) PutMem(key, suffix [][]byte, val []byte, opt PutOptions) (bool, error)
  • func (tree *BPlusTree) Remove()
  • func (tree *BPlusTree) RemoveSuffix(key [][]byte) [][]byte
  • func (tree *BPlusTree) Scan(opts ScanOptions, scanFn func(key [][]byte, val []byte) (bool, error)) error
  • func (tree *BPlusTree) Size() int64
  • func (tree *BPlusTree) String() string
  • func (tree *BPlusTree) WriteAll() error
• type Options
• type PutOptions
• type ScanOptions

Types

type BPlusTree

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

BPlusTree represents an on-disk bptree. Size of each node is decided based on key size, value size and tree degree.

func Open

func Open(fileName string, opts *Options) (*BPlusTree, error)

Open opens the named file as a bptree index file and returns an instance bptree for use. Use ":memory:" for an in-memory bptree instance for quick testing setup. Degree of the tree is computed based on maxKeySize and pageSize used by the pager. If nil options are provided, defaultOptions will be used.

func (*BPlusTree) AddSuffix

func (tree *BPlusTree) AddSuffix(key [][]byte, flag suffixOption) [][]byte

AddSuffix adds extra counter bytes at end of key if Uniq option was set to False while creating BPTree.

func (*BPlusTree) CanInsert

func (tree *BPlusTree) CanInsert(key, suffix [][]byte) bool

CanInsert returns true if passed (key + suffix) key can be inserted. Othervise false will be returned.

func (*BPlusTree) CheckConsistency

func (tree *BPlusTree) CheckConsistency(list [][]byte) bool

CheckConsistency checks consistency of tree. It traverses tree and checks all bptree rules on each node and if something is wront false will be returned.

func (*BPlusTree) ClearCache

func (tree *BPlusTree) ClearCache()

ClearCache flushes all cached data to disk (marked as 'dirty') and frees memory.

func (*BPlusTree) Close

func (tree *BPlusTree) Close() error

Close flushes any writes and closes the underlying pager.

func (*BPlusTree) Del

func (tree *BPlusTree) Del(key, suffix [][]byte) (int, error)

Del removes the key-value entry from the bptree. If the key does not exist, returns error.

func (*BPlusTree) DelMem

func (tree *BPlusTree) DelMem(key, suffix [][]byte) (int, error)

Del removes the key-value entry from the bptree. If the key does not exist, returns error. Unlike Del DelMem will not force to flush dirty nodes to disk after deletion.

func (*BPlusTree) Get

func (tree *BPlusTree) Get(key, suffix [][]byte) ([][]byte, error)

Get fetches the values associated with the given key. Returns empty slice if key not found.

func (*BPlusTree) IsUniq

func (tree *BPlusTree) IsUniq() bool

IsUniq returns true if tree keys are configured as uniq. Othervise false.

func (*BPlusTree) Options

func (tree *BPlusTree) Options() Options

Options returns copy of tree options.

func (*BPlusTree) PrepareSpace

func (tree *BPlusTree) PrepareSpace(size uint32)

PrepareSpace allocates size bytes on underlying bptree file. This is usefull if big amount of data is going to be inserted. It's increases performance of insertion.

func (*BPlusTree) Print

func (tree *BPlusTree) Print()

Print pretty prints tree into terminal. Not recomended to call if tree is too big.

func (*BPlusTree) Put

func (tree *BPlusTree) Put(key, suffix [][]byte, val []byte, opt PutOptions) (bool, error)

Put puts the key-value pair into the B+ tree. Value will be updated or inserted depending on passed PutOptions.

func (*BPlusTree) PutMem

func (tree *BPlusTree) PutMem(key, suffix [][]byte, val []byte, opt PutOptions) (bool, error)

PutMem puts the key-value pair into the B+ tree. Value will be updated or inserted depending on passed PutOptions. Unlike Put PutMem will not force to flush dirty nodes to disk after insertion/update.

func (*BPlusTree) Remove

func (tree *BPlusTree) Remove()

Remove removes tree data from disk.

func (*BPlusTree) RemoveSuffix

func (tree *BPlusTree) RemoveSuffix(key [][]byte) [][]byte

reverse version of AddSuffix.

func (*BPlusTree) Scan

func (tree *BPlusTree) Scan(
	opts ScanOptions,
	scanFn func(key [][]byte, val []byte) (bool, error),
) error

Scan performs an index scan starting at the given key. Each entry will be passed to the scanFn. If the key is zero valued (nil or len=0), then the left/right leaf key will be used as the starting key. Scan continues until the right most leaf node is reached or the scanFn returns 'true' indicating to stop the scan.

func (*BPlusTree) Size

func (tree *BPlusTree) Size() int64

Size returns the number of entries in the entire tree.

func (*BPlusTree) String

func (tree *BPlusTree) String() string

String prints tree general info.

func (*BPlusTree) WriteAll

func (tree *BPlusTree) WriteAll() error

WriteAll writes all the nodes marked 'dirty' to the underlying pager.

type Options

type Options struct {
	// PageSize to be for file I/O. All reads and writes will always
	// be done with pages of this size. Must be multiple of 4096.
	PageSize int `json:"page_size"`

	// MaxKeySize represents the maximum size allowed for the key.
	// Put call with keys larger than this will result in error.
	MaxKeySize int `json:"max_key_size"`

	// Count of columns of key
	KeyCols int `json:"key_cols"`

	// Count of columns of suffix in key
	// If set 0, bptree will take value from counter
	SuffixCols int `json:"suffix_cols"`

	// Max size allowed for suffix
	MaxSuffixSize int `json:"max_suffix_size"`

	// MaxValueSize represents the maximum size allowed for the value.
	// Put call with values larger than this will result in error.
	// Branching factor reduces as this size increases. So smaller
	// the better.
	MaxValueSize int `json:"max_value_size"`

	// number of children per node
	Degree int `json:"degree"`

	// if set true, values inserted must be unique, othervise values can repeat
	// but BPTree will add extra bytes at end of key to maintain uniqueness
	Uniq bool `json:"uniq"`

	// Max count of in-memory cached nodes to avoid io
	CacheSize int `json:"cache_size"`
}

Options represents the configuration options for the B+ tree index.

type PutOptions

type PutOptions struct {
	// if set true, will try to find key-value pair with given key and update value.
	// Othervise will insert new key-value pair
	Update bool
}

PutOptions tells bptree how to put kev-value pair

type ScanOptions

type ScanOptions struct {
	// if Key present, scan will start from given key
	Key [][]byte

	// if set true, scan will be in decreasing order on keys.
	Reverse bool

	// if set true, given key will be included in scan.
	Strict bool
}

ScanOptions tells bptree how to start tree scan