Skip to main content

LayerKey

fxfs::lsm_tree::types

Trait LayerKey 

Source 
pub trait LayerKey: Clone {
    // Required method
    fn overlaps(&self, other: &Self) -> bool;

    // Provided methods
    fn merge_type(&self) -> MergeType { ... }
    fn next_key(&self) -> Option<Self> { ... }
    fn search_key(&self) -> Option<Self> { ... }
    fn is_search_key(&self) -> bool { ... }
}
Expand description

Determines how to iterate forward from the current key, and how many older layers to include when merging. See the different variants of MergeKeyType for more details.

Required Methods§

Source

fn overlaps(&self, other: &Self) -> bool

Returns true if the keys are overlapping or equal.

Provided Methods§

Source

fn merge_type(&self) -> MergeType

Called to determine how to perform merge behaviours while advancing through a layer set.

Source

fn next_key(&self) -> Option<Self>

The next_key() call allows for an optimisation which allows the merger to avoid querying a layer if it knows it has found the next possible key. It only makes sense for this to return Some() when merge_type() returns OptimizedMerge. Consider the following example showing two layers with range based keys.

 +----------+------------+

0 | 0..100 | 100..200 | +–––––+————+ 1 | 100..200 | +————+

If you search and find the 0..100 key, then only layer 0 will be touched. If you then want to advance to the 100..200 record, you can find it in layer 0 but unless you know that it immediately follows the 0..100 key i.e. that there is no possible key, K, such that 0..100 < K < 100..200, the merger has to consult all other layers to check. next_key should return a search key for an extent that immediately follows. In practice, for extents, this should be 0..end + 1.

This is purely an optimisation; the default None will be correct but not performant.

Source

fn search_key(&self) -> Option<Self>

Returns the search key (S) for this key (K), such that when when searching for S in a layer file, it returns the earliest possible key that might be relevant to K. Searching in a layer file is done using cmp_upper_bound and the iterator will be positioned on a key that is greater than or equal to S. Returning None here is the right thing to do for non-ranged based keys, in which case K is used to search for the key. In practice, the implementation should return Some(0..start + 1) for range based keys and None for everything else. As an example, if the tree has extents 50..150 and 150..200 and we wish to search for 100..200, search_key would return 0..101 which would position the iterator on 50..150. If this method is overridden, is_search_key below should also be overridden.

Source

fn is_search_key(&self) -> bool

If you override search_key you should override is_search_key.

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§