node

package
v0.4.0 Latest Latest
Warning

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

 Go to latest Published: Apr 3, 2026 License: MIT Imports: 8 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	FlagInline    = 0x00
	FlagPointer   = 0x01
	FlagTombstone = 0x02
)
View Source 
const (
	// NodeHeaderSize is the size of the page header (16 bytes).
	NodeHeaderSize = page.PageHeaderSize

	// DirectoryEntrySize is the size of an offset (uint16).
	DirectoryEntrySize = 2
)

Variables

View Source 
var (
	ErrKeyTooLarge                 = errors.New("key too large")
	ErrValueTooLarge               = errors.New("value too large")
	ErrNodeFull                    = errors.New("node is full")
	ErrInvalidType                 = errors.New("invalid node type")
	ErrKeyNotFound                 = errors.New("key not found")
	ErrCorruptedNode               = errors.New("corrupted node: invalid offsets")
	ErrInternalBaseDeltaOutOfRange = errors.New("internal base-delta child range exceeds uint32")
)

Common errors

Functions

This section is empty.

Types

type Builder 

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

Builder facilitates O(N) sequential construction of a node. It avoids the O(log N) search and O(N) shift of standard insertion.

func NewBuilder 

func NewBuilder(data []byte, pType page.PageType) *Builder

NewBuilder initializes a builder for the given buffer.

func NewBuilderWithOptions 

func NewBuilderWithOptions(data []byte, pType page.PageType, opts BuilderOptions) *Builder

func (*Builder) AddInternalChild 

func (b *Builder) AddInternalChild(key []byte, childPageID uint64) error

AddInternalChild appends a child pointer. Assumes keys are added in sorted order.

func (*Builder) AddLeafEntry 

func (b *Builder) AddLeafEntry(key, value []byte, flags byte, valPtr page.ValuePtr) error

AddLeafEntry appends a leaf entry. Assumes keys are added in sorted order.

func (*Builder) AddLeafEntryWithPrefix 

func (b *Builder) AddLeafEntryWithPrefix(key, value []byte, flags byte, valPtr page.ValuePtr, entrySize, prefixLen, suffixLen int) error

AddLeafEntryWithPrefix appends a leaf entry using precomputed size/prefix data. The caller must ensure prefixLen/suffixLen are computed for this builder state.

func (*Builder) Count 

func (b *Builder) Count() uint16

func (*Builder) Data 

func (b *Builder) Data() []byte

Data returns the underlying buffer.

func (*Builder) Finish 

func (b *Builder) Finish() *Node

Finish finalizes the page header and checksum. Returns a Node wrapper for convenience.

func (*Builder) FinishNoNode added in v0.4.0 

func (b *Builder) FinishNoNode()

FinishNoNode finalizes the page header and checksum without allocating a Node wrapper. Use this in hot paths that only need the encoded page bytes.

func (*Builder) FreeSpace 

func (b *Builder) FreeSpace() int

func (*Builder) LeafEntrySize 

func (b *Builder) LeafEntrySize(key, value []byte, flags byte) int

LeafEntrySize returns the encoded size for a leaf entry if it were appended next, based on the builder's current prefix-compression state.

func (*Builder) LeafEntrySizeWithPrefix 

func (b *Builder) LeafEntrySizeWithPrefix(key, value []byte, flags byte) (entrySize, prefixLen, suffixLen int)

LeafEntrySizeWithPrefix returns the encoded size and prefix/suffix lengths for a leaf entry if it were appended next.

func (*Builder) LeafPrevKey 

func (b *Builder) LeafPrevKey() []byte

LeafPrevKey returns the last key appended to a leaf builder. It is only maintained when leaf prefix compression is enabled.

func (*Builder) PageID 

func (b *Builder) PageID() uint64

PageID returns the configured page ID.

func (*Builder) ReleaseScratch added in v0.4.0 

func (b *Builder) ReleaseScratch()

ReleaseScratch returns pooled scratch resources held by the builder and drops references so the builder can be reused safely.

func (*Builder) ResetWithOptions added in v0.4.0 

func (b *Builder) ResetWithOptions(data []byte, pType page.PageType, opts BuilderOptions)

ResetWithOptions reinitializes an existing builder instance for reuse.

func (*Builder) SetInternalFenceBounds added in v0.3.0 

func (b *Builder) SetInternalFenceBounds(low, high []byte)

SetInternalFenceBounds configures exact subtree bounds for internal pages. low is inclusive and high is exclusive; nil high means unbounded.

func (*Builder) SetPageID 

func (b *Builder) SetPageID(id uint64)

SetPageID sets the page ID (can be done at finish too).

type BuilderOptions 

type BuilderOptions struct {
	LeafPrefixCompression bool
	LeafColumnar          bool
	InternalBaseDelta     bool
	PackedValuePtr        bool
}

func AdaptiveLeafBuilderOptions added in v0.4.0 

func AdaptiveLeafBuilderOptions(base BuilderOptions, entries []LeafHeuristicEntry) BuilderOptions

AdaptiveLeafBuilderOptions chooses per-page leaf encoding flags from a base capability set using a deterministic lightweight heuristic.

Heuristic goals: - prefer columnar for pointer-heavy pages, - prefer prefix compression for high shared-prefix key runs, - avoid extra metadata overhead on short, low-prefix, pointer-dense pages.

type InternalEntry 

type InternalEntry struct {
	Key         []byte
	ChildPageID uint64
}

InternalEntry represents a parsed entry from an Internal Node.

type LeafEntry 

type LeafEntry struct {
	Key      []byte
	Value    []byte
	ValuePtr page.ValuePtr // Valid if Flags & FlagPointer
	Flags    byte
}

LeafEntry represents a parsed entry from a Leaf Node.

type LeafHeuristicEntry added in v0.4.0 

type LeafHeuristicEntry struct {
	Key   []byte
	Flags byte
}

LeafHeuristicEntry describes one logical leaf entry for adaptive encoding selection.

type Node 

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

Node is a wrapper around a raw page byte slice. It implements the Slotted Page layout.

func NewNode 

func NewNode(data []byte) *Node

NewNode creates a Node wrapper around the given page data.

func NewNodeView 

func NewNodeView(data []byte) Node

NewNodeView wraps the given page data without allocating a *Node. It is useful in hot paths that store Node values directly (e.g. iterators).

func (*Node) AddInternalChild 

func (n *Node) AddInternalChild(key []byte, childPageID uint64) error

AddInternalChild inserts or updates an internal entry while maintaining sorted order.

It is intended for point updates and small in-memory manipulations. Write paths that rebuild pages in bulk should prefer Builder.

func (*Node) AddLeafEntry 

func (n *Node) AddLeafEntry(key, value []byte, flags byte, valPtr page.ValuePtr) error

AddLeafEntry inserts a new entry into the Leaf Node. It maintains the sorted order of keys. If the key already exists, it updates it (by rewriting the entry). NOTE: This implementation assumes simple append-to-heap and shift-directory. It DOES NOT handle fragmentation (holes in heap) yet. A full implementation would compact the heap if FreeSpace check fails but logical space exists.

func (*Node) Checksum 

func (n *Node) Checksum() uint32

Checksum returns the checksum from the header.

func (*Node) Compact 

func (n *Node) Compact() error

Compact rebuilds the node's slotted-page layout in-place, removing heap holes created by overwrites/splits. It preserves logical entry order (directory order) and updates offsets and checksum.

func (*Node) Count 

func (n *Node) Count() uint16

Count returns the number of items in the node.

func (*Node) Data 

func (n *Node) Data() []byte

Data returns the underlying byte slice.

func (*Node) FreeSpace 

func (n *Node) FreeSpace() int

FreeSpace returns the number of bytes available for new items. Free space is the gap between the end of the Directory and the start of the Heap.

func (*Node) GetInternalChildID 

func (n *Node) GetInternalChildID(index uint16) (uint64, error)

GetInternalChildID returns only the child page ID at the given index.

func (*Node) GetInternalEntry 

func (n *Node) GetInternalEntry(index uint16) (InternalEntry, error)

GetInternalEntry reads the entry at the given index.

func (*Node) GetInternalEntryView 

func (n *Node) GetInternalEntryView(index uint16) (key []byte, childID uint64, err error)

GetInternalEntryView returns a view of the entry at the given index. For uncompressed internal pages, the returned key slice points directly into the node's backing page.

For internal base-delta pages, the returned key slice is backed by a node scratch buffer and is only valid until the next internal entry decode call on the same node. Callers that need to retain the key must copy it.

func (*Node) GetLeafEntry 

func (n *Node) GetLeafEntry(index uint16) (LeafEntry, error)

GetLeafEntry reads the entry at the given index.

func (*Node) GetLeafEntryView 

func (n *Node) GetLeafEntryView(index uint16) (key []byte, val []byte, valPtr page.ValuePtr, flags byte, err error)

GetLeafEntryView returns a view of the entry at the given index. Key and Value slices point directly to the node's data when the node is not prefix-compressed. For prefix-compressed nodes, Key is reconstructed into a scratch buffer owned by the node and is only valid until the next call.

func (*Node) GetLeafKeyFlagsView added in v0.3.0 

func (n *Node) GetLeafKeyFlagsView(index uint16) (key []byte, flags byte, err error)

GetLeafKeyFlagsView returns the key and flags for the entry at index without decoding the value bytes/pointer payload.

func (*Node) GetLeafValueView added in v0.3.0 

func (n *Node) GetLeafValueView(index uint16) (val []byte, valPtr page.ValuePtr, flags byte, err error)

GetLeafValueView returns the value (inline or pointer) at the given index without reconstructing the key. This is useful for point reads after SearchLeaf.

func (*Node) InternalBaseDeltaEnabled added in v0.4.0 

func (n *Node) InternalBaseDeltaEnabled() bool

InternalBaseDeltaEnabled reports whether this internal node uses base-delta key encoding. When true, GetInternalEntryView keys are scratch-backed and callers that retain keys must copy them.

func (*Node) InternalFenceBounds added in v0.3.0 

func (n *Node) InternalFenceBounds() (low, high []byte, ok bool, err error)

InternalFenceBounds returns exact subtree bounds when persisted on this internal page: low inclusive and high exclusive. A nil/empty high bound means unbounded.

func (*Node) PageID 

func (n *Node) PageID() uint64

PageID returns the page ID from the header.

func (*Node) SearchInternal 

func (n *Node) SearchInternal(key []byte) (uint16, bool)

SearchInternal performs a binary search for the given key in an Internal Node. Returns the index of the child that covers the range containing key. Logic: Find largest index i such that Entry[i].Key <= key. If key < Entry[0].Key, returns index 0 (Left-most child rule usually handles this).

func (*Node) SearchInternalChildID added in v0.3.0 

func (n *Node) SearchInternalChildID(key []byte) (childID uint64, found bool, err error)

SearchInternalChildID resolves the child page ID for key in a single logical search. The found return value matches SearchInternal: true when key is >= at least one separator in this page.

func (*Node) SearchInternalWithCompare added in v0.3.0 

func (n *Node) SearchInternalWithCompare(key []byte, cmpFn func(a, b []byte) int) (uint16, bool)

SearchInternalWithCompare is like SearchInternal but uses the provided compare function to compare entry keys against the search key.

func (*Node) SearchLeaf 

func (n *Node) SearchLeaf(key []byte) (uint16, bool, error)

SearchLeaf performs a binary search for the given key in a Leaf Node. Returns the index of the first entry where Entry.Key >= key. If key is found, found=true. If key is greater than all entries, returns Count, false.

func (*Node) SetCount 

func (n *Node) SetCount(c uint16)

SetCount sets the number of items in the node.

func (*Node) SetKeyScratch added in v0.4.0 

func (n *Node) SetKeyScratch(buf []byte)

SetKeyScratch installs caller-owned key scratch for prefix key reconstruction. The slice must not be mutated concurrently while the node is in use.

func (*Node) SetPageID 

func (n *Node) SetPageID(id uint64)

SetPageID sets the page ID in the header.

func (*Node) SetType 

func (n *Node) SetType(t page.PageType)

SetType sets the page type in the header.

func (*Node) Split 

func (n *Node) Split(newNode *Node) ([]byte, error)

Split moves the upper half of the items from the receiver node (n) to the given new node (newNode). It returns the "pivot" key (the first key of the new node), which is used to insert into the parent.

func (*Node) TakeKeyScratch added in v0.4.0 

func (n *Node) TakeKeyScratch() []byte

TakeKeyScratch detaches and returns the node key scratch buffer, if any.

func (*Node) Type 

func (n *Node) Type() page.PageType

Type returns the page type from the header.

func (*Node) UpdateChecksum 

func (n *Node) UpdateChecksum()

UpdateChecksum calculates and updates the checksum in the header.

func (*Node) UpdateLeafValuePtr 

func (n *Node) UpdateLeafValuePtr(index uint16, oldPtr, newPtr page.ValuePtr) (bool, error)

UpdateLeafValuePtr updates the ValuePtr bytes for the entry at index if the entry is a pointer and currently matches oldPtr. It updates the page checksum on success.

This is intended for maintenance operations (e.g. value-log compaction) that need to swap pointers without rewriting the B+Tree structure.

func (*Node) VerifyChecksum 

func (n *Node) VerifyChecksum() bool

VerifyChecksum validates the node's checksum.

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.