Struct Stree 

pub struct Stree<K: Key> { /* private fields */ }

S-Tree

Implementations

impl<K: Key> Stree<K>

pub const DEFAULT_NODE_SIZE: u16 = 16

pub const DEFAULT_PAYLOAD_PREFETCH_SIZE: usize

Default size for prefetching payload data (1MB)

pub fn compute_payload_prefetch_size( num_items: usize, estimated_avg_payload_size: Option<usize>, prefetch_factor: Option<f32>, ) -> usize

Compute the optimal payload prefetch size based on tree characteristics.

This method estimates the appropriate size to prefetch from the payload section. It takes into account the number of items in the tree and adapts the prefetch size to balance between memory usage and HTTP request reduction.

Arguments

• num_items - Number of items in the tree
• estimated_avg_payload_size - Estimated average size of each payload entry (default: 64 bytes)
• prefetch_factor - Adjustment factor for the prefetch size (default: 1.0)

Returns

The recommended payload prefetch size in bytes

pub fn build(nodes: &[NodeItem<K>], branching_factor: u16) -> Result<Stree<K>>

pub fn from_buf( data: impl Read, num_items: usize, branching_factor: u16, ) -> Result<Stree<K>>

pub async fn from_http<T: AsyncHttpRangeClient>( client: &mut AsyncBufferedHttpRangeClient<T>, index_begin: usize, num_items: usize, node_size: u16, ) -> Result<Stree<K>>

pub fn find_exact(&self, key: K) -> Result<Vec<SearchResultItem>>

pub fn stream_find_exact<R: Read + Seek + ?Sized>( data: &mut R, num_items: usize, branching_factor: u16, key: K, ) -> Result<Vec<SearchResultItem>>

pub fn find_range(&self, lower: K, upper: K) -> Result<Vec<SearchResultItem>>

Finds all items with keys in the specified range [lower, upper]

This implementation uses a partition-based approach for efficient range searches:

1. Find partition points for both the lower and upper bounds
2. Process only the relevant leaf nodes between these partition points
3. Filter items within those leaf nodes by the actual range bounds

Special cases:

• If lower > upper, returns an empty result (invalid range)
• If lower == upper, delegates to find_exact for consistent behavior

pub fn find_range_strict( &self, lower: K, lower_strict: bool, upper: K, upper_strict: bool, ) -> Result<Vec<SearchResultItem>>

Finds all items whose key lies within the range, with each bound independently strict (exclusive) or inclusive.

This is what Gt/Lt/Ne lower to. They must NOT be expressed as an inclusive range minus find_exact: the subtraction removes FEATURE OFFSETS, but a feature’s CityObjects can carry several values of the same indexed attribute and the writer indexes each occurrence, so one feature offset appears under several keys. A feature holding both k and some k' > k is returned by the range scan (via k') and also by find_exact(k) (via k), so subtracting deletes a genuine match. Filtering by bound strictness at the leaf cannot make that mistake, and costs one traversal instead of two.

pub fn stream_find_range<R: Read + Seek + ?Sized>( data: &mut R, num_items: usize, branching_factor: u16, lower: K, upper: K, ) -> Result<Vec<SearchResultItem>>

pub fn stream_find_range_strict<R: Read + Seek + ?Sized>( data: &mut R, num_items: usize, branching_factor: u16, lower: K, lower_strict: bool, upper: K, upper_strict: bool, ) -> Result<Vec<SearchResultItem>>

Streaming counterpart of Stree::find_range_strict: each bound is independently strict (exclusive) or inclusive, so Gt/Lt/Ne need no unsound subtraction on feature offsets.

pub fn find_partition(&self, key: K) -> Result<usize>

Finds the partition point for a key in the tree Returns the index in the leaf level where the key would be inserted

This is a key function that powers efficient range searches by finding the exact location where a key would be inserted in the leaf level. For range queries, we use this function to find the start and end points in the leaf level for a given range, then scan through just those leaf nodes.

pub fn stream_find_partition<R: Read + Seek + ?Sized>( data: &mut R, num_items: usize, branching_factor: u16, key: K, ) -> Result<usize>

pub async fn http_stream_find_exact<T: AsyncHttpRangeClient>( client: &mut AsyncBufferedHttpRangeClient<T>, index_begin: usize, feature_begin: usize, num_items: usize, branching_factor: u16, key: K, combine_request_threshold: usize, ) -> Result<Vec<HttpSearchResultItem>>

pub async fn http_stream_find_partition<T: AsyncHttpRangeClient>( client: &mut AsyncBufferedHttpRangeClient<T>, index_begin: usize, num_items: usize, branching_factor: u16, key: K, _combine_request_threshold: usize, ) -> Result<usize>

pub fn tree_size(num_items: usize) -> usize

pub fn estimate_payload_section_size( num_items: usize, duplicate_percentage: Option<f32>, avg_duplicates_per_key: Option<f32>, ) -> usize

Estimate the total size of the payload section based on tree characteristics.

This method provides an estimate of how large the payload section might be based on the number of items in the tree and an estimated percentage of items with duplicate keys.

Arguments

• num_items - Number of items in the tree
• duplicate_percentage - Estimated percentage of items with duplicate keys (0.0-1.0)
• avg_duplicates_per_key - Average number of duplicates per duplicate key

Returns

The estimated size of the payload section in bytes

pub fn index_size( num_items: usize, branching_factor: u16, payload_size: usize, ) -> usize

pub fn payload_size(&self) -> usize

pub fn num_leaf_items(&self) -> usize

pub fn num_items(&self) -> usize

pub fn branching_factor(&self) -> u16

pub fn stream_write<W: Write>(&self, out: &mut W) -> Result<usize>

Write all index nodes and any payload data

pub async fn http_stream_find_range<T: AsyncHttpRangeClient>( client: &mut AsyncBufferedHttpRangeClient<T>, index_begin: usize, feature_begin: usize, num_items: usize, branching_factor: u16, lower: K, upper: K, combine_request_threshold: usize, ) -> Result<Vec<HttpSearchResultItem>>

pub async fn http_stream_find_range_strict<T: AsyncHttpRangeClient>( client: &mut AsyncBufferedHttpRangeClient<T>, index_begin: usize, feature_begin: usize, num_items: usize, branching_factor: u16, lower: K, lower_strict: bool, upper: K, upper_strict: bool, combine_request_threshold: usize, ) -> Result<Vec<HttpSearchResultItem>>

HTTP counterpart of Stree::find_range_strict: each bound is independently strict (exclusive) or inclusive, so Gt/Lt/Ne need no unsound subtraction on feature offsets.

Trait Implementations

impl<K: Clone + Key> Clone for Stree<K>

fn clone(&self) -> Stree<K>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug + Key> Debug for Stree<K>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.