Struct scc::TreeIndex

pub struct TreeIndex<K, V> where
    K: Clone + Ord + Send + Sync,
    V: Clone + Send + Sync,  { /* fields omitted */ }

A scalable concurrent B+ tree.

scc::TreeIndex is a B+ tree variant that is optimized for read operations. Read operations, such as read, scan, are neither blocked nor interrupted by other threads. Write operations, such as insert, remove, do not block if they do not entail structural changes to the tree.

The key features of scc::TreeIndex

• Write-free read: read operations never modify the shared data.
• Near lock-free write: write operations do not block unless a structural change is required.

The key statistics for scc::TreeIndex

• The maximum number of key-value pairs that a leaf can store: 8.
• The maximum number of leaves or child nodes that a node can point to: 9.
• The size of metadata per key-value pair in a leaf: 3-byte.
• The size of metadata per leaf or node in a node: size_of(K) + 4.

Implementations

impl<K, V> TreeIndex<K, V> where
    K: Clone + Ord + Send + Sync,
    V: Clone + Send + Sync, 

pub fn new() -> TreeIndex<K, V>

Creates an empty TreeIndex instance.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

let result = treeindex.read(&1, |key, value| *value);
assert!(result.is_none());

pub fn insert(&self, key: K, value: V) -> Result<(), (K, V)>

Inserts a key-value pair.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

let result = treeindex.insert(1, 10);
assert!(result.is_ok());

let result = treeindex.insert(1, 11);
assert_eq!(result.err().unwrap(), (1, 11));

let result = treeindex.read(&1, |key, value| *value);
assert_eq!(result.unwrap(), 10);

pub fn remove<Q: ?Sized>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Ord, 

Removes a key-value pair.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

let result = treeindex.remove(&1);
assert!(!result);

let result = treeindex.insert(1, 10);
assert!(result.is_ok());

let result = treeindex.remove(&1);
assert!(result);

pub fn read<Q: ?Sized, R, F: FnOnce(&Q, &V) -> R>(
    &self,
    key: &Q,
    f: F
) -> Option<R> where
    K: Borrow<Q>,
    Q: Ord, 

Reads a key-value pair.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

let result = treeindex.read(&1, |key, value| *value);
assert!(result.is_none());

let result = treeindex.insert(1, 10);
assert!(result.is_ok());

let result = treeindex.read(&1, |key, value| *value);
assert_eq!(result.unwrap(), 10);

pub fn clear(&self)

Clears the TreeIndex.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

for key in 0..16u64 {
    let result = treeindex.insert(key, 10);
    assert!(result.is_ok());
}

treeindex.clear();

let result = treeindex.len();
assert_eq!(result, 0);

pub fn len(&self) -> usize

Returns the size of the TreeIndex.

It internally scans all the leaf nodes, and therefore the time complexity is O(N).

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

for key in 0..16u64 {
    let result = treeindex.insert(key, 10);
    assert!(result.is_ok());
}

let result = treeindex.len();
assert_eq!(result, 16);

pub fn depth(&self) -> usize

Returns the depth of the TreeIndex.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

for key in 0..16u64 {
    let result = treeindex.insert(key, 10);
    assert!(result.is_ok());
}

let result = treeindex.depth();
assert_eq!(result, 1);

pub fn iter(&self) -> Scanner<'_, K, V>

Returns a Scanner.

The returned Scanner starts scanning from the minimum key-value pair.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

let result = treeindex.insert(1, 10);
assert!(result.is_ok());

let result = treeindex.insert(2, 11);
assert!(result.is_ok());

let result = treeindex.insert(3, 13);
assert!(result.is_ok());

let mut scanner = treeindex.iter();
assert_eq!(scanner.next().unwrap(), (&1, &10));
assert_eq!(scanner.next().unwrap(), (&2, &11));
assert_eq!(scanner.next().unwrap(), (&3, &13));
assert!(scanner.next().is_none());

pub fn range<R: RangeBounds<K>>(&self, range: R) -> Range<'_, K, V, R>

Returns a Range that scans keys in the given range.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

for i in 0..10 {
    let result = treeindex.insert(i, 10);
    assert!(result.is_ok());
}

for entry in treeindex.range(1..1) {
    assert!(false);
}

let mut scanned = 0;
for entry in treeindex.range(4..8) {
    assert!(*entry.0 >= 4 && *entry.0 < 8);
    scanned += 1;
}
assert_eq!(scanned, 4);

scanned = 0;
for entry in treeindex.range(4..=8) {
    assert!(*entry.0 >= 4 && *entry.0 <= 8);
    scanned += 1;
}
assert_eq!(scanned, 5);

impl<K, V> TreeIndex<K, V> where
    K: Clone + Display + Ord + Send + Sync,
    V: Clone + Display + Send + Sync, 

pub fn print<T: Write>(&self, output: &mut T) -> Result<()>

Prints the TreeIndex contents to the given output in the DOT language.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

let result = treeindex.insert(1, 10);
assert!(result.is_ok());

treeindex.print(&mut std::io::stdout());

Trait Implementations

impl<K, V> Default for TreeIndex<K, V> where
    K: Clone + Ord + Send + Sync,
    V: Clone + Send + Sync, 

fn default() -> Self

Creates a TreeIndex instance with the default parameters.

Examples

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = Default::default();

let result = treeindex.read(&1, |key, value| *value);
assert!(result.is_none());

impl<K, V> Drop for TreeIndex<K, V> where
    K: Clone + Ord + Send + Sync,
    V: Clone + Send + Sync, 

fn drop(&mut self)

Executes the destructor for this type.