tree

Documentation

Overview

Package tree

(C) Copyright Alex Gaetano Padula

Licensed under the Mozilla Public License, v. 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

https://www.mozilla.org/en-US/MPL/2.0/

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Index

• Constants
• type BTree
  • func Open(blockManager BlockManager, order int, extraMeta interface{}) (*BTree, error)
  • func (bt *BTree) BulkPutSorted(entries []KeyValue) error
  • func (bt *BTree) Close() error
  • func (bt *BTree) Get(key []byte) (interface{}, bool, error)
  • func (bt *BTree) GetExtraMeta() interface{}
  • func (bt *BTree) Iterator(ascending bool) (*Iterator, error)
  • func (bt *BTree) PrefixIterator(prefix []byte, ascending bool) (*Iterator, error)
  • func (bt *BTree) Put(key []byte, value interface{}) error
  • func (bt *BTree) RangeIterator(startKey, endKey []byte, ascending bool) (*Iterator, error)
• type BlockManager
• type Iterator
  • func (iter *Iterator) BTree() *BTree
  • func (iter *Iterator) HasNext() bool
  • func (iter *Iterator) Key() []byte
  • func (iter *Iterator) Next() bool
  • func (iter *Iterator) NextItem() ([]byte, interface{}, bool)
  • func (iter *Iterator) Peek() ([]byte, interface{}, bool)
  • func (iter *Iterator) Prev() bool
  • func (iter *Iterator) Seek(seekKey []byte) error
  • func (iter *Iterator) SeekToFirst() error
  • func (iter *Iterator) SeekToLast() error
  • func (iter *Iterator) SetDirection(ascending bool)
  • func (iter *Iterator) Valid() bool
  • func (iter *Iterator) Value() interface{}
• type KeyValue
• type Metadata
• type Node

Constants

const ReservedMetadataBlockID = 2

Types

type BTree

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

BTree is the main struct for the b-tree

func Open

func Open(blockManager BlockManager, order int, extraMeta interface{}) (*BTree, error)

Open retrieves/opens a btree instance. Block manager should be opened with read/write!!

func (*BTree) BulkPutSorted

func (bt *BTree) BulkPutSorted(entries []KeyValue) error

BulkPutSorted builds the B-tree from a sorted slice of key-value pairs in one bottom-up pass. Entries must be sorted by key (bytes.Compare(entries[i].Key, entries[i+1].Key) <= 0). Intended for a newly created empty B-tree (e.g. when flushing a memtable). If the tree already has keys, behavior is undefined; the existing structure may be replaced. Empty entries: no-op, current empty root is kept.

func (*BTree) Close

func (bt *BTree) Close() error

Close closes the B-tree and its block manager

func (*BTree) Get

func (bt *BTree) Get(key []byte) (interface{}, bool, error)

Get finds a value by key

func (*BTree) GetExtraMeta

func (bt *BTree) GetExtraMeta() interface{}

GetExtraMeta retrieves extra metadata associated with the B-tree. This is set on btree creation.

func (*BTree) Iterator

func (bt *BTree) Iterator(ascending bool) (*Iterator, error)

Iterator returns a general-purpose iterator that can seek to any position

func (*BTree) PrefixIterator

func (bt *BTree) PrefixIterator(prefix []byte, ascending bool) (*Iterator, error)

PrefixIterator returns an iterator for all keys with the given prefix

func (*BTree) Put

func (bt *BTree) Put(key []byte, value interface{}) error

Put adds a key-value pair to the B-tree, updates if the key already exists

func (*BTree) RangeIterator

func (bt *BTree) RangeIterator(startKey, endKey []byte, ascending bool) (*Iterator, error)

RangeIterator returns an iterator for keys in the range [startKey, endKey]

type BlockManager

type BlockManager interface {
	Append(data []byte) (int64, error)
	Read(blockID int64) ([]byte, int64, error)
	Update(blockID int64, newData []byte) (int64, error)
	Close() error
}

BlockManager interface defines methods for managing blocks of data

type Iterator

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

Iterator provides bidirectional iteration capabilities

func (*Iterator) BTree

func (iter *Iterator) BTree() *BTree

BTree returns the B-tree instance associated with this iterator

func (*Iterator) HasNext

func (iter *Iterator) HasNext() bool

HasNext checks if there are more items

func (*Iterator) Key

func (iter *Iterator) Key() []byte

Key returns the current key (without advancing the iterator)

func (*Iterator) Next

func (iter *Iterator) Next() bool

Next moves to the next item (direction depends on ascending flag) Returns true if successful, false if no more items

func (*Iterator) NextItem

func (iter *Iterator) NextItem() ([]byte, interface{}, bool)

NextItem returns the current key-value pair and advances the iterator (for backward compatibility)

func (*Iterator) Peek

func (iter *Iterator) Peek() ([]byte, interface{}, bool)

Peek returns the current key and value without advancing the iterator

func (*Iterator) Prev

func (iter *Iterator) Prev() bool

Prev moves to the previous item (regardless of ascending flag)

func (*Iterator) Seek

func (iter *Iterator) Seek(seekKey []byte) error

Seek positions the iterator at the first key >= seekKey (for ascending) or <= seekKey (for descending)

func (*Iterator) SeekToFirst

func (iter *Iterator) SeekToFirst() error

SeekToFirst positions the iterator at the first key in the tree

func (*Iterator) SeekToLast

func (iter *Iterator) SeekToLast() error

SeekToLast positions the iterator at the last key in the tree

func (*Iterator) SetDirection

func (iter *Iterator) SetDirection(ascending bool)

SetDirection changes the iteration direction

func (*Iterator) Valid

func (iter *Iterator) Valid() bool

Valid returns true if the iterator is positioned at a valid key

func (*Iterator) Value

func (iter *Iterator) Value() interface{}

Value returns the current value (without advancing the iterator)

type KeyValue

type KeyValue struct {
	Key   []byte
	Value interface{}
}

KeyValue is a key-value pair for bulk loading. Used by BulkPutSorted.

type Metadata

type Metadata struct {
	RootBlockID int64       // Block ID of the root node
	Order       int         // Minimum degree t
	Extra       interface{} // Extra metadata, can be any type
}

Metadata represents the metadata of the B-tree

type Node

type Node struct {
	BlockID  int64         // BlockID in which node lives
	IsLeaf   bool          // Is this a leaf node?
	Keys     [][]byte      // Keys in the node, sorted
	Values   []interface{} // Used in both leaf and internal nodes for consistency
	Children []int64       // Block IDs of child nodes
	Parent   int64         // Block ID of parent node (for efficient traversal)
	NextLeaf int64         // Block ID of next leaf (for range iteration)
	PrevLeaf int64         // Block ID of previous leaf (for bidirectional iteration)
}

Node represents a B-tree node