Documentation
¶
Index ¶
- Constants
- type HashDBKV
- type Iter
- type KVStore
- type Meta
- type Node
- type NodeID
- type NodeType
- type Options
- type RevIter
- type Tree
- func (t *Tree) Delete(key []byte) error
- func (t *Tree) Get(key []byte) ([]byte, error)
- func (t *Tree) Put(key, value []byte) error
- func (t *Tree) PutMany(keys, values [][]byte) error
- func (t *Tree) Range(start, end []byte) (*Iter, error)
- func (t *Tree) ReverseRange(start, end []byte) (*RevIter, error)
- func (t *Tree) ScanAll() (*Iter, error)
Constants ¶
const MaxKeys = 128
MaxKeys defines the maximum number of keys a node can hold before splitting. A fan-out of 128 keeps nodes compact while providing good branching.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type HashDBKV ¶
type HashDBKV struct {
Store *hashdb.HashDB
}
HashDBKV adapts HashDB to the KVStore interface.
type Iter ¶
type Iter struct {
// contains filtered or unexported fields
}
Iter iterates over the B+Tree in ascending key order. It holds a read lock on the tree for its lifetime; callers must Close().
func (*Iter) Next ¶
func (it *Iter) Next()
Next advances the iterator. Optimized for inlining: Keep this function small and simple.
type KVStore ¶
type KVStore interface {
Get(key []byte) ([]byte, error)
Put(key, value []byte) error
Delete(key []byte) error
}
KVStore is the minimal interface the B+Tree expects from the backing store.
type Node ¶
type Node struct {
ID NodeID
Type NodeType
// Common
Keys [][]byte
// Internal
Children []NodeID // len(Children) == len(Keys)+1 when Type == NodeInternal
// Leaf
Values [][]byte // len(Values) == len(Keys) when Type == NodeLeaf
NextLeaf NodeID
PrevLeaf NodeID
}
Node represents an in-memory B+Tree node. Keys are kept sorted in ascending lexicographic order.
type Options ¶
type Options struct {
CacheSize int // Number of nodes to keep in memory. Default 128.
}
Options configures the BTree.
type RevIter ¶
type RevIter struct {
// contains filtered or unexported fields
}
RevIter iterates over the B+Tree in descending key order. It holds a read lock on the tree for its lifetime; callers must Close().
func (*RevIter) Next ¶
func (it *RevIter) Next()
Next advances the iterator backwards. Optimized for inlining.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree implements a B+Tree on top of an abstract KV store. Concurrency is handled with a coarse-grained RWMutex.
func NewTreeOnHashDB ¶
NewTreeOnHashDB constructs a Tree backed by HashDB.
func OpenTree ¶
OpenTree loads an existing tree or initializes a new one if no metadata exists. Meta read errors are returned to the caller; only an absent meta entry triggers initialization.
func (*Tree) Delete ¶
Delete removes a key from the tree. It is a lazy delete and performs no rebalancing.
func (*Tree) Range ¶
Range returns an iterator over [start, end). start == nil begins from the smallest key; end == nil iterates through the largest key.
func (*Tree) ReverseRange ¶
ReverseRange returns a descending iterator over [start, end). start == nil iterates down to the smallest key; end == nil starts from the largest key.
Source Files