tree

package
v0.6.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 1, 2026 License: MIT Imports: 15 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var ErrKeyNotFound = errors.New("key not found")

Functions

This section is empty.

Types

type CursorItem 

type CursorItem struct {
	PageID uint64
	Ref    page.ChildRef
	Node   node.Node
	Index  int
}

type GetManyReadStats added in v0.6.0 

type GetManyReadStats struct {
	CallsTotal          uint64
	GroupedCallsTotal   uint64
	FallbackCallsTotal  uint64
	LeafGroupsTotal     uint64
	LeafGroupItemsTotal uint64
	LeafLoadsSavedTotal uint64
}

func GetManyReadStatsSnapshot added in v0.6.0 

func GetManyReadStatsSnapshot() GetManyReadStats

type GetManyViewFunc added in v0.6.0 

type GetManyViewFunc func(index int, key []byte, value []byte, found bool) error

GetManyViewFunc receives one GetManyView result. The value slice is a read-only view that is valid only until the callback returns; callers must copy it before retaining it. Missing/tombstoned keys are reported with found=false and value=nil.

type Iterator 

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

func (*Iterator) Close 

func (it *Iterator) Close() error

func (*Iterator) Domain 

func (it *Iterator) Domain() (start, end []byte)

func (*Iterator) Error 

func (it *Iterator) Error() error

func (*Iterator) IsDeleted 

func (it *Iterator) IsDeleted() bool

func (*Iterator) Key 

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

func (*Iterator) KeyCopy 

func (it *Iterator) KeyCopy(dst []byte) []byte

func (*Iterator) Next 

func (it *Iterator) Next()

func (*Iterator) Seek 

func (it *Iterator) Seek(key []byte)

func (*Iterator) UnsafeEntry 

func (it *Iterator) UnsafeEntry() ([]byte, page.ValuePtr, byte)

func (*Iterator) UnsafeEntryWithRevision added in v0.6.1 

func (it *Iterator) UnsafeEntryWithRevision() ([]byte, page.ValuePtr, byte, page.EntryRevision)

func (*Iterator) UnsafeKey 

func (it *Iterator) UnsafeKey() []byte

func (*Iterator) UnsafeValue 

func (it *Iterator) UnsafeValue() []byte

func (*Iterator) Valid 

func (it *Iterator) Valid() bool

func (*Iterator) Value 

func (it *Iterator) Value() []byte

func (*Iterator) ValueCopy 

func (it *Iterator) ValueCopy(dst []byte) []byte

type IteratorMode added in v0.4.0 

type IteratorMode uint8

IteratorMode controls value materialization behavior while scanning. 

const (
	// IteratorModeFull resolves inline and pointer-backed values on demand.
	IteratorModeFull IteratorMode = iota
	// IteratorModeKeysOnly skips value materialization entirely.
	IteratorModeKeysOnly
	// IteratorModePointerProjection keeps pointer metadata visible via UnsafeEntry
	// but skips pointer payload decoding.
	IteratorModePointerProjection
)

type IteratorOptions added in v0.4.0 

type IteratorOptions struct {
	Mode IteratorMode
	// IncludeTombstones keeps tombstone rows visible to iteration callers.
	// Default false preserves user-facing behavior (tombstones hidden).
	IncludeTombstones bool
}

IteratorOptions configures scan-time value materialization behavior.

type LeafLogPageReadState added in v0.6.0 

type LeafLogPageReadState struct {
	RecordChecksumVerified bool
	CacheEntryPresent      bool
	PageChecksumVerified   bool
}

LeafLogPageReadState describes validation state carried by a leaf-log page read. RecordChecksumVerified is true when the bytes were produced by a checksum-enabled value-log read. CacheEntryPresent is true when the reader has an entry for this leaf pointer that may be marked after successful page checksum validation. PageChecksumVerified is true only when cached bytes had the B-tree page checksum validated successfully before being cached as verified.

type LeafLogPageViewChecksumMarker added in v0.6.0 

type LeafLogPageViewChecksumMarker interface {
	MarkLeafLogPageViewChecksumVerified()
}

LeafLogPageViewChecksumMarker can be implemented by a view lease to mark the leased cache entry as page-checksum verified while the view lock is still held.

type LeafLogPageViewLease added in v0.6.0 

type LeafLogPageViewLease interface {
	ReleaseLeafLogPageView()
}

LeafLogPageViewLease releases a read-only leaf-log page view.

type OuterLeafReadStats added in v0.5.0 

type OuterLeafReadStats struct {
	LoadsTotal            uint64
	PointLoadsTotal       uint64
	IteratorLoadsTotal    uint64
	BytesTotal            uint64
	SampleMod             uint64
	SamplesTotal          uint64
	Recent64HitsTotal     uint64
	Recent256HitsTotal    uint64
	Recent1KHitsTotal     uint64
	Recent4KHitsTotal     uint64
	ChecksumVerifiedTotal uint64
	ChecksumSkippedTotal  uint64
}

func OuterLeafReadStatsSnapshot added in v0.5.0 

func OuterLeafReadStatsSnapshot() OuterLeafReadStats

type ProbeFallbackStats added in v0.6.0 

type ProbeFallbackStats struct {
	FallbackCalls uint64
	FallbackItems uint64
}

type ReadPathStats added in v0.4.0 

type ReadPathStats struct {
	GetAppendInlineHitsTotal   uint64
	GetAppendInlineBytesTotal  uint64
	GetAppendPointerHitsTotal  uint64
	GetAppendPointerBytesTotal uint64
}

func ReadPathStatsSnapshot added in v0.4.0 

func ReadPathStatsSnapshot() ReadPathStats

type SlabReader 

type SlabReader interface {
	Read(ptr page.ValuePtr) ([]byte, error)
	ReadUnsafe(ptr page.ValuePtr) ([]byte, error)
}

type Tree 

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

func New 

func New(p *pager.Pager, sr SlabReader, root uint64) *Tree

func (*Tree) CollectPageIDs 

func (t *Tree) CollectPageIDs() ([]uint64, error)

CollectPageIDs returns the sorted set of pager-backed page IDs reachable from the Tree root. Leaf pages stored in the value log are excluded.

func (*Tree) Get 

func (t *Tree) Get(key []byte) ([]byte, error)

Get returns the value for key.

When the stored value is non-empty, Get returns an owned, mutable copy of that value.

If the key is missing or tombstoned, Get returns ErrKeyNotFound. When the stored value is zero-length but the key is present, Get returns a non-nil zero-length slice.

func (*Tree) GetAppend added in v0.4.0 

func (t *Tree) GetAppend(key, dst []byte) ([]byte, error)

GetAppend appends the value for key to dst and returns the grown slice. If key is missing/tombstoned, it returns dst and ErrKeyNotFound.

func (*Tree) GetEntry 

func (t *Tree) GetEntry(key []byte) (node.LeafEntry, error)

GetEntry returns the persisted leaf entry for key.

CAUTION: Returned entry Key/Value might point directly to mmap memory. Do not modify or hold reference for long.

func (*Tree) GetEntryExact added in v0.4.0 

func (t *Tree) GetEntryExact(key []byte) (node.LeafEntry, error)

GetEntryExact is an alias for GetEntry.

func (*Tree) GetManyAppend added in v0.6.0 

func (t *Tree) GetManyAppend(keys [][]byte, out [][]byte, arena []byte) ([]byte, error)

GetManyAppend resolves keys into out using arena for returned safe-copy values. Missing keys leave nil entries in out. Present empty values use a shared zero-length, capacity-zero slice.

func (*Tree) GetManyView added in v0.6.0 

func (t *Tree) GetManyView(keys [][]byte, fn GetManyViewFunc) error

GetManyView resolves keys and calls fn once per input key with a read-only value view. The callback may be invoked in any order, but the index argument always identifies the input key. Value views are valid only until fn returns; callers must copy values they need after the callback. Missing or tombstoned keys are reported with found=false and value=nil.

func (*Tree) GetUnsafe 

func (t *Tree) GetUnsafe(key []byte) ([]byte, error)

func (*Tree) GetVersionedAppend added in v0.6.1 

func (t *Tree) GetVersionedAppend(key, dst []byte) ([]byte, page.EntryRevision, error)

GetVersionedAppend appends the value for key to dst and returns the entry revision stored beside the value/pointer metadata. Missing keys return ErrKeyNotFound and LegacyEntryRevision; tombstones return ErrKeyNotFound with their stored tombstone revision.

func (*Tree) Has 

func (t *Tree) Has(key []byte) (bool, error)

func (*Tree) HasAnySorted added in v0.6.0 

func (t *Tree) HasAnySorted(keys [][]byte) (bool, error)

func (*Tree) HasAnySortedWithStats added in v0.6.0 

func (t *Tree) HasAnySortedWithStats(keys [][]byte) (bool, ProbeFallbackStats, error)

func (*Tree) HasMany added in v0.6.0 

func (t *Tree) HasMany(keys [][]byte) ([]bool, error)

func (*Tree) HasPrefixes added in v0.6.0 

func (t *Tree) HasPrefixes(prefixes [][]byte) ([]bool, error)

func (*Tree) HasPrefixesWithStats added in v0.6.0 

func (t *Tree) HasPrefixesWithStats(prefixes [][]byte) ([]bool, ProbeFallbackStats, error)

func (*Tree) Iterator 

func (t *Tree) Iterator(start, end []byte) iterator.UnsafeIterator

func (*Tree) IteratorWithOptions added in v0.4.0 

func (t *Tree) IteratorWithOptions(start, end []byte, opts IteratorOptions) iterator.UnsafeIterator

IteratorWithOptions returns a forward iterator over [start, end) using the provided value materialization mode.

func (*Tree) Reset 

func (t *Tree) Reset(p *pager.Pager, sr SlabReader, root uint64)

Reset re-initializes the tree with new parameters for reuse.

func (*Tree) ReverseIterator 

func (t *Tree) ReverseIterator(start, end []byte) iterator.UnsafeIterator

func (*Tree) ReverseIteratorWithOptions added in v0.4.0 

func (t *Tree) ReverseIteratorWithOptions(start, end []byte, opts IteratorOptions) iterator.UnsafeIterator

ReverseIteratorWithOptions returns a reverse iterator over [start, end) using the provided value materialization mode.

func (*Tree) SetRoot 

func (t *Tree) SetRoot(root uint64)

SetRoot updates the root page ID.

func (*Tree) UpdateValuePtrInPlace 

func (t *Tree) UpdateValuePtrInPlace(key []byte, oldPtr, newPtr page.ValuePtr) (updated bool, leafPageID uint64, err error)

UpdateValuePtrInPlace rewrites a pointer value in-place inside the current tree by updating the leaf page that contains key.

This is intended for maintenance operations (e.g. value-log compaction) that want to avoid full copy-on-write path rewrites. Callers must ensure snapshot safety (i.e. no readers are pinned to the current index generation) before using it.

Returns (updated=true, leafPageID) when the entry existed as a pointer and matched oldPtr. If the key is missing or has changed since oldPtr, it returns updated=false with a nil error.

func (*Tree) WalkPages 

func (t *Tree) WalkPages(fn func(pageID uint64, n node.Node) error) error

WalkPages visits each pager-backed page reachable from the Tree's current root exactly once. Leaf pages stored in the value log (typed leaf-log child refs) are skipped. It is primarily intended for diagnostics, vacuuming, and tests.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.