Module spacetimedb_table::btree_index

BTree indexes with specialized key types.

Indexes could be implemented as MultiMap<AlgebraicValue, RowPointer> (and once were), but that results in wasted memory and spurious comparisons and branches because the keys must always be homogeneous at a more specific type than AlgebraicValue.

As an optimization, we hoist the enum out of the keys to the index itself. This is a sizeable improvement for integer keys, as e.g. u64::cmp is much faster than AlgebraicValue::cmp.

This results in some pretty ugly code, where types that would be structs are instead enums with similar-looking variants for each specialized key type, and methods that interact with those enums have matches with similar-looking arms. Some day we may devise a better solution, but this is good enough for now.

Structs

• BTreeIndex
  A B-Tree based index on a set of [ColId]s of a table.
• BTreeIndexRangeIter
  An iterator over rows matching a certain AlgebraicValue on the BTreeIndex.