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) 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 Metadata
• type Node

Constants

const ReservedMetadataBlockID = 2 // Reserved block ID for metadata

Types

type BTree

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

BTree represents the tree. An append only immutable B-tree implementation optimized for range and prefix iteration.

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) 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 matches your existing implementation

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 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