Multi-indexing is implemented by inserting multiple rows into the index B-Tree. So if your index for a document returns [1, 2], Rethink stores two records into the index BTree -- one keyed by 1, the other keyed by 2.
This is different from hyperdex -- we don't do any algorithmic tricks with spaces to make this more efficient. The model we used fit extremely well into our architecture, so @jdoliner just went ahead and implemented it.
Hope this makes sense -- great questions! (Also, love your username)
We store a secondary index for a shard on the same node where the master for the shard resides. So if you're storing users whose last names are between A-M on node A, all secondary indexes for users with last names between A and M will also be on node A. That means that for any secondary index query we have to contact all nodes that have shards for a table, but we do a number of systems tricks to make this really efficient.
Can you talk about these tricks? I'd love to learn more about it.
This seems somewhat similar to hyperdex's search function. It is implemented through what is called hyperspace hashing. How would you compare yourself to hyperdex?