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

View Source

B-tree-like index structure for the Olivine storage driver.

Structure

The index consists of:

  • Tree: gb_trees keyed by page last_key, storing page_id
  • Page Map: Map of page_id → Page structs containing key-value pairs
  • Page Chain: Linked list of pages via next_id pointers, starting from page 0
  • Gap-Free Design: Pages cover entire keyspace with no gaps between them

Critical Invariants

  1. Page 0 Existence: Page 0 must always exist as the leftmost page
  2. Tree Ordering: Pages in tree order have strictly ascending last_key values
  3. Chain Integrity: Page chain starts at 0, terminates at 0, covers all pages
  4. Key Ordering: Following page chain yields all keys in strictly ascending order
  5. Non-overlapping: Pages have non-overlapping key ranges
  6. Page Keys: Within each page, keys are sorted; first_key <= last_key

Page Chain Reconstruction

When pages are added or modified, the page chain is automatically rebuilt from tree ordering to maintain consistency. This ensures proper key ordering across page boundaries and prevents chain corruption during concurrent operations and page splits.

Multi-Split Support

Pages can be split into multiple pages when they exceed size limits. The original page ID is preserved for the first split to maintain consistency, especially for page 0. Chain pointers are updated to maintain traversal integrity.

Algorithms

Key Lookup

  1. Use Tree.page_for_key(key) to find page containing key
  2. Search within page for exact key match

Mutation Application

  1. Use Tree.page_for_key(key) to find target page (no gaps exist)
  2. Apply operations to page, maintaining sorted order within page

Page Splitting

  1. When page exceeds 512 keys, split at 3/4 of max capacity (384 keys per page)
  2. First page keeps original page_id (preserves page 0 as leftmost)
  3. Subsequent pages get new page_ids
  4. Update tree entries and rebuild page chain from tree ordering
  5. Chain integrity is automatically maintained through reconstruction

Range Clearing

  1. Find all pages intersecting the range using tree
  2. For single page: clear keys within range
  3. For multiple pages: delete middle pages, clear edges
  4. Chain integrity maintained through automatic reconstruction

Summary

Types

operation()
t()

Functions

delete_pages(index, page_ids)

Removes multiple pages from the index by their IDs. Updates both the tree structure and page_map. Returns the updated index.

get_page!(index, page_id)

Gets a page by its ID from the index. Raises if the page is not found.

get_page_with_next_id!(index, page_id)

Gets a page and its cached next_id from the index. Returns {page_binary, next_id}.

load_from(arg, opts \\ [])

Loads an Index from the database by traversing the page chain and building the tree structure. Returns {:ok, index, max_id, free_ids, total_key_count} or an error.

locator_for_key(index, key)
multi_split_page_from_segments(index, original_page_id, original_next_id, original_page, segments, key_count, id_allocator)

Splits a page into multiple pages using per-key segments for efficiency.

new(opts \\ [])

Creates a new empty Index with an initial page covering the entire keyspace.

page_for_key(index, key)

Finds the page containing the given key in this index.

pages_for_range(index, start_key, end_key)

Finds all pages that contain keys within the given range in this index. Returns {:ok, [Page.t()]} with the list of pages (may be empty).

Types

operation()

@type operation() :: Bedrock.DataPlane.Materializer.Olivine.IndexManager.operation()

t()

@type t() :: %Bedrock.DataPlane.Materializer.Olivine.Index{
  max_key: Bedrock.key(),
  max_keys_per_page: pos_integer(),
  min_key: Bedrock.key(),
  page_map: map(),
  target_keys_per_page: pos_integer(),
  tree: :gb_trees.tree()
}

Functions

delete_pages(index, page_ids)

@spec delete_pages(t(), [Bedrock.DataPlane.Materializer.Olivine.Index.Page.id()]) ::
  t()

Removes multiple pages from the index by their IDs. Updates both the tree structure and page_map. Returns the updated index.

get_page!(index, page_id)

@spec get_page!(t(), Bedrock.DataPlane.Materializer.Olivine.Index.Page.id()) ::
  Bedrock.DataPlane.Materializer.Olivine.Index.Page.t()

Gets a page by its ID from the index. Raises if the page is not found.

get_page_with_next_id!(index, page_id)

@spec get_page_with_next_id!(
  t(),
  Bedrock.DataPlane.Materializer.Olivine.Index.Page.id()
) ::
  {Bedrock.DataPlane.Materializer.Olivine.Index.Page.t(),
   Bedrock.DataPlane.Materializer.Olivine.Index.Page.id()}

Gets a page and its cached next_id from the index. Returns {page_binary, next_id}.

load_from(arg, opts \\ [])

@spec load_from(
  Bedrock.DataPlane.Materializer.Olivine.Database.t(),
  keyword()
) ::
  {:ok, t(), Bedrock.DataPlane.Materializer.Olivine.Index.Page.id(),
   [Bedrock.DataPlane.Materializer.Olivine.Index.Page.id()], non_neg_integer()}
  | {:error, :missing_pages}

Loads an Index from the database by traversing the page chain and building the tree structure. Returns {:ok, index, max_id, free_ids, total_key_count} or an error.

Options

  • max_keys_per_page - Maximum keys per page (default: 256)

locator_for_key(index, key)

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

multi_split_page_from_segments(index, original_page_id, original_next_id, original_page, segments, key_count, id_allocator)

@spec multi_split_page_from_segments(
  t(),
  Bedrock.DataPlane.Materializer.Olivine.Index.Page.id(),
  Bedrock.DataPlane.Materializer.Olivine.Index.Page.id(),
  Bedrock.DataPlane.Materializer.Olivine.Index.Page.t(),
  [Bedrock.DataPlane.Materializer.Olivine.Index.Page.segment()],
  non_neg_integer(),
  Bedrock.DataPlane.Materializer.Olivine.IdAllocator.t()
) ::
  {t(), [Bedrock.DataPlane.Materializer.Olivine.Index.Page.id()],
   Bedrock.DataPlane.Materializer.Olivine.IdAllocator.t()}

Splits a page into multiple pages using per-key segments for efficiency.

This version accepts pre-computed segments from Page.apply_operations_as_segments/2, avoiding the need to decode an oversized binary page.

Uses floor division to minimize chunks and distribute remainder evenly. Example: 462 keys with target 230 → [231, 231] rather than [230, 230, 2]

The original page ID is preserved for the first page in the chain. The last page points to the original page's next_id.

Returns {updated_index, new_page_ids, updated_allocator}.

new(opts \\ [])

@spec new(keyword()) :: t()

Creates a new empty Index with an initial page covering the entire keyspace.

Options

  • max_keys_per_page - Maximum keys per page before splitting (default: 256)

page_for_key(index, key)

@spec page_for_key(t(), Bedrock.key()) ::
  Bedrock.DataPlane.Materializer.Olivine.Index.Page.t()

Finds the page containing the given key in this index.

pages_for_range(index, start_key, end_key)

@spec pages_for_range(t(), Bedrock.key(), Bedrock.key()) ::
  {:ok, [Bedrock.DataPlane.Materializer.Olivine.Index.Page.t()]}

Finds all pages that contain keys within the given range in this index. Returns {:ok, [Page.t()]} with the list of pages (may be empty).