Module skiplist 

MemtableSkipList: lock-free sorted map keyed by encoded InternalKey bytes.

We use crossbeam_skiplist::SkipMap<bytes::Bytes, EntryValue>. Keys are the raw wire bytes of InternalKey, which sort correctly via bytes::Bytes’s lexicographic Ord implementation (guaranteed by the InternalKey encoding — see merutable-types/src/key.rs).

Point lookup algorithm

Given user_key_bytes (the PK-encoded portion, without tag) and read_seq:

1. Build a seek_bytes = user_key_bytes ++ seek_tag(SEQNUM_MAX). This is the lexicographically smallest InternalKey for that PK (tag = 0x0000000000000001).
2. map.lower_bound(Included(&seek_bytes)) → first entry ≥ seek key.
3. Verify entry’s PK prefix matches user_key_bytes.
4. Decode seq from the entry’s tag; reject if seq > read_seq.
5. Return Some(entry.value()) or None.

Structs

EntryValue

Value stored in the skip list.

MemtableSkipList

Functions

decode_op_type_from_key

Decode the OpType from a fully encoded InternalKey bytes slice.

decode_seq_from_key

Decode the sequence number from a fully encoded InternalKey bytes slice. The tag occupies the last 8 bytes in big-endian: (inverted_seq << 8) | op_type.

user_key_of

Extract user-key (PK) bytes from a fully encoded InternalKey bytes slice.