Reading the boost::multi_index reference, I discovered that the iterator_to method has constant order. How is that possible? I mean, if an iterator is a different object than the value_type it represents, how is possible the container finds their corresponding internal node without searching on the index?
The only solution I can think of is that the address of the container's "internal node" (or whatever it is) is the same as the value_type it holds (for example, putting the node header just below the value_type or something). If the passed argument is a reference to an interal value_type, the corresponding iterator can be construct easily through the argument's address to get the red-black node.
But!! What about the C++ standard restricction that there's cannot be two objects with same address? What about alignment, padding, fill or any of those things that can happen at memory level?
Your intuition is correct: the value is part of a larger node structure (as explained for instance here) and iterator_to merely calculates the address of the node from the address of the value_type subobject. Now, the pointer arithmetics involved rely on the fact that the node (or the base class where the value is stored) is standard-layout, which guarantees that a pointer to first subobject (the value) can be cast to a pointer to the structure (the node): the relevant code can be looked at here.