Bedrock.DataPlane.Materializer.Olivine.Index.Page (bedrock v0.5.2)

View Source

Page management routines for the Olivine storage driver.

Pages are the fundamental storage unit in the Olivine B-tree index. Each page contains sorted key-locator pairs and chain pointers for traversal.

Key Features

  • Binary encoding: Pages are stored as optimized binary data for efficiency
  • Chain linking: Pages form a linked list via next_id pointers
  • Sorted keys: Keys within each page are maintained in ascending order
  • Version tracking: Each key has an associated locator for MVCC support
  • Size limits: Pages are split when they exceed 256 keys to maintain performance

Operations

  • Page creation, encoding, and decoding
  • Page splitting for size management
  • Key range queries within pages
  • Chain traversal for ordered iteration
  • Validation of page structure and invariants

Summary

Types

id()
operation()
page_map()
segment()
t()

Functions

apply_operations(page, operations)

Applies a map of operations to a binary page, returning the updated binary page. Operations can be {:set, locator} or :clear.

apply_operations_as_segments(page, operations)

Applies operations to a binary page, returning per-key segments for efficient splitting.

build_from_segments(page_id, segments, key_count, original_page, rightmost_key)

Builds a binary page from pre-computed segments.

build_from_segments_iodata(page_id, iodata, key_count, rightmost_key)

Builds a binary page from iodata (already materialized segments).

decode_entry_at_position(entries_data, position, key_count)
empty?(page)

Checks if a page is empty (has no keys).

id(arg1)
key_count(arg1)
key_locators(arg1)
keys(page)
left_key(arg)
locator_for_key(arg, target_key)
new(id, key_locators)

Creates a page with key-locator tuples. Returns the binary-encoded page with next_id set to 0.

right_key(page)
search_entries_with_position(data, count, target_key)
stream_key_locators_in_range(pages_stream, start_key, end_key)

Types

id()

@type id() :: non_neg_integer()

operation()

@type operation() ::
  {:set, Bedrock.DataPlane.Materializer.Olivine.Database.locator()} | :clear

page_map()

@type page_map() :: %{
  id: id(),
  next_id: id(),
  key_locators: [
    {binary(), Bedrock.DataPlane.Materializer.Olivine.Database.locator()}
  ]
}

segment()

@type segment() :: {non_neg_integer(), non_neg_integer()} | binary()

t()

@type t() :: binary() | page_map()

Functions

apply_operations(page, operations)

@spec apply_operations(binary(), %{required(Bedrock.key()) => operation()}) ::
  binary()

Applies a map of operations to a binary page, returning the updated binary page. Operations can be {:set, locator} or :clear.

apply_operations_as_segments(page, operations)

@spec apply_operations_as_segments(binary(), %{required(Bedrock.key()) => operation()}) ::
  {[segment()], key_count :: non_neg_integer(), rightmost_key :: binary() | nil}

Applies operations to a binary page, returning per-key segments for efficient splitting.

Returns a tuple of:

  • page_id: The page ID from the header
  • segments: Reversed list of per-key segments (each segment is one {key, locator} entry)
    • {offset, length} for unchanged keys (reference to old binary)
    • <<binary>> for new/modified keys
  • key_count: Final number of keys after operations
  • rightmost_key: The rightmost key in the page (or nil if empty)

The segments list is in reverse order (rightmost key first), which is natural from the merge algorithm and gives us the rightmost key for free.

build_from_segments(page_id, segments, key_count, original_page, rightmost_key)

@spec build_from_segments(
  id(),
  [segment()],
  non_neg_integer(),
  binary(),
  binary() | nil
) :: binary()

Builds a binary page from pre-computed segments.

Takes a page ID, list of segments (in reverse order), final key count, original page, and the rightmost key. The segments list and rightmost key should come from apply_operations_as_segments/2.

Returns a complete binary page with proper header and payload.

build_from_segments_iodata(page_id, iodata, key_count, rightmost_key)

@spec build_from_segments_iodata(id(), iodata(), non_neg_integer(), binary() | nil) ::
  binary()

Builds a binary page from iodata (already materialized segments).

Takes a page ID, iodata payload, key count, and rightmost key. This is used when segments have already been materialized by take_and_materialize.

Returns a complete binary page with proper header and payload.

decode_entry_at_position(entries_data, position, key_count)

@spec decode_entry_at_position(binary(), non_neg_integer(), non_neg_integer()) ::
  {:ok, {key :: binary(), locator :: binary()}} | :out_of_bounds

empty?(page)

@spec empty?(t() | binary()) :: boolean()

Checks if a page is empty (has no keys).

id(arg1)

@spec id(t()) :: id()

key_count(arg1)

@spec key_count(t()) :: non_neg_integer()

key_locators(arg1)

@spec key_locators(t()) :: [
  {binary(), Bedrock.DataPlane.Materializer.Olivine.Database.locator()}
]

keys(page)

@spec keys(t()) :: [binary()]

left_key(arg)

@spec left_key(t()) :: binary() | nil

locator_for_key(arg, target_key)

@spec locator_for_key(t(), Bedrock.key()) ::
  {:ok, Bedrock.DataPlane.Materializer.Olivine.Database.locator()}
  | {:error, :not_found}

new(id, key_locators)

@spec new(
  id :: id(),
  key_locators :: [
    {binary(), Bedrock.DataPlane.Materializer.Olivine.Database.locator()}
  ]
) :: binary()

Creates a page with key-locator tuples. Returns the binary-encoded page with next_id set to 0.

right_key(page)

@spec right_key(t()) :: binary() | nil

search_entries_with_position(data, count, target_key)

@spec search_entries_with_position(binary(), non_neg_integer(), Bedrock.key()) ::
  {:found, pos :: non_neg_integer()}
  | {:not_found, insertion_point :: non_neg_integer()}

stream_key_locators_in_range(pages_stream, start_key, end_key)

@spec stream_key_locators_in_range(Enumerable.t(t()), Bedrock.key(), Bedrock.key()) ::
  Enumerable.t(
    {Bedrock.key(), Bedrock.DataPlane.Materializer.Olivine.Database.locator()}
  )