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

View Source

Tree operations for the Olivine storage driver.

Structure

The tree is a gb_trees structure with:

  • Key: Page's last_key (rightmost key in page)
  • Value: page_id (no first_key needed)
  • Ordering: Sorted by last_key for efficient range queries
  • Coverage: Pages cover the entire keyspace with no gaps

Key Operations

No Gaps Design

Every point in the keyspace belongs to exactly one page:

  1. Page 0 starts at <<>> (empty binary)
  2. Each page ends at its last_key
  3. Next page implicitly starts after previous page's last_key
  4. Final page extends to <<0xFF, 0xFF>> (infinity marker)

Summary

Types

page()
page_id()
t()

Functions

add_page_to_tree(tree, page)

Updates the interval tree by adding a new page range.

from_page_map(page_map)

Builds a page tree from a page map by adding each page to an empty tree.

page_for_key(tree, key)

Finds the page that contains a specific key. With no gaps, every key maps to exactly one page. Uses gb_trees iterator for efficiency.

remove_page_from_tree(tree, page)

Updates the interval tree by removing a page range.

update_page_in_tree(tree, old_page, new_page)

Updates a page's position in the tree by removing the old range and adding the new range. Only updates if the last_key actually changed for efficiency.

Types

page()

@type page() :: Bedrock.DataPlane.Materializer.Olivine.Index.Page.t()

page_id()

@type page_id() :: Bedrock.DataPlane.Materializer.Olivine.Index.Page.id()

t()

@type t() :: :gb_trees.tree()

Functions

add_page_to_tree(tree, page)

@spec add_page_to_tree(t(), page()) :: t()

Updates the interval tree by adding a new page range.

Empty pages are only added to the tree if they are page 0 (the leftmost page), which is always present and covers the beginning of the keyspace.

from_page_map(page_map)

@spec from_page_map(page_map :: map()) :: t()

Builds a page tree from a page map by adding each page to an empty tree.

page_for_key(tree, key)

@spec page_for_key(t(), Bedrock.key()) :: page_id()

Finds the page that contains a specific key. With no gaps, every key maps to exactly one page. Uses gb_trees iterator for efficiency.

Tree structure: key = last_key, value = page_id

When a key is beyond all pages in the tree, returns page 0 (which acts as the catch-all page extending to infinity).

remove_page_from_tree(tree, page)

@spec remove_page_from_tree(t(), page()) :: t()

Updates the interval tree by removing a page range.

Empty pages are only removed from the tree if they are page 0.

update_page_in_tree(tree, old_page, new_page)

@spec update_page_in_tree(t(), page(), page()) :: t()

Updates a page's position in the tree by removing the old range and adding the new range. Only updates if the last_key actually changed for efficiency.