The idea is a combination of the following:
- A hash map of the first element to the second element (or a list of them)
- A hash map of the second element to the first element (or a list of them)
Hash maps give expected O(1) lookup.
I don't believe databases typically use hash maps though, more typically b-trees as far as I know (giving O(log n) performance).