node

package
v0.3.0 Latest Latest
Warning

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

 Go to latest Published: Feb 7, 2026 License: MIT Imports: 6 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) 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) 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
}

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