Function radarbase::binarytree::lookup_in_raw

pub(crate) fn lookup_in_raw<'a, K: RadbKey + ?Sized>(
    page: Page<'a>,
    table: u64,
    query: &[u8],
    manager: &'a PageManager
) -> Option<(Page<'a>, usize, usize)>

Returns a tuple of the form (Page<'a>, usize, usize) representing the value for a queried key within a binary tree if present.

The binary tree is composed of Nodes serialized into Pages and maintained by a PageManager. This function attempts to locate a key within this tree and if found, returns a tuple where:

• The first element is the Page in which the value is located
• The second element is the offset within that page where the value begins
• The third element is the length of the value

Given a key, the function begins at the root of the tree and traverses to the left or right child depending on whether the key is less or greater than the current node’s key. The process is recursive and continues until the key is either found or it is determined that the key does not exist in the tree.

This function might not be space efficient since it allocates a whole page for each node, leading to a waste of space when nodes don’t fully occupy their corresponding pages. Future optimizations could involve storing multiple nodes within a single page, or having variable size pages to better match the size of nodes.

Arguments

• page - The Page object representing the current node being inspected.
• query - The key being searched for.
• manager - The PageManager managing the pages.

Returns

An Option that contains a tuple (Page<'a>, usize, usize). If the key is found, it returns Some, with the Page containing the value, the offset of the value within the page, and the length of the value. If the key is not found in the tree, it returns None.

Panics

This function will panic if it encounters a byte in the Page memory that does not correspond to a recognized node type (1 for leaf node or 2 for internal node).