Module fixed_len_nibble_trie 

Fixed-Length Nibble Trie — a fixed-fanout radix trie with fixed-length key slots.

Like [NibbleTrie], each node has 16 child slots (one per nibble value 0–15). The key difference is that keys are stored in fixed-length slots in buf, eliminating the need for a separate index vector and the offset field per node.

Key Storage

Each key occupies exactly max_len bytes in buf, zero-padded on the right. The key index i maps directly to buf[i * max_len .. (i + 1) * max_len]. Actual key lengths are stored in a lens: Vec<u16> alongside buf, giving O(1) key retrieval without an index vector. This adds only 2 bytes/key overhead (vs NibbleTrie’s ~10 bytes/key for (usize, LEN) on 64-bit).

Key Index

Leaf key indices are 0-based (unlike NibbleTrie’s 1-based scheme). The sentinel value for empty child slots is PTR::max_value() (instead of 0). This gives a max entry count of PTR::max_value() - 1.

Offset Elimination

The offset field in NibbleTrie’s Node is replaced by computing leaf.as_usize() * max_len on demand. The terminal flag is stored in a flags: u8 field (bit 0).

Optimization

[optimize()] rewrites buf and values in DFS-sorted order and remaps leaf indices. Called automatically after each insert when values.len() is a power of two (amortized O(1) per insert).

Structs

FixedLenIter

FixedLenNibbleTrie

A fixed-length nibble trie map.

FixedLenNode

A single node in the fixed-length nibble trie arena.