Have you considered using this library?

If you need custom ordering, consider AVLTree

This probably calls for a generic Rustler-based Elixir library that bridges various Rust data structures to Elixir code. In your case that’d be Rust’s BTreeMap.

Discord have a sorted set library with bindings to Rust – not a map but still, in case you need this one as well. You can also just take a look at Discord’s libraries in general, they are quite excellent.

A theoretical example

• The main data structure, a gb_tree with:
  [{0, %{user: :a}}, {1, %{user: b}}, {2, %{user: z}}, {3, %{user: a}}
• The index, a Map of lists with:
  %{a: [0, 3], b: [1], c: [2]

You then iterate over the gb_tree until you find something you want to delete/process; then, to find out which other entries you need to delete, you consult the index rather than iterating over all the entries.

Then, once you’ve finished processing that particular group of objects, you can continue iterating where you left of (gb_tree does provide a function for this.)

All that it’s left is to write the bookkeeping code necessarily to ensure the two structures remain consistent with each other for every write.

Yeah everyone speaks well of Rust for native code - I haven’t taken the time to learn it so worried about the cognitive load but I do know C/C++ . Should probably watch Scroggin’s talk again but I’m spending so much time on beam/infrastructure I’ve not much chance to learn a new language. Excuses. Excuses.