A many-to-many mapping data structure
Use two indices: the first index allows you to map a key value to the corresponding tuples that contain that key value; the second index allows you to map a data value to the tuples that contain that data value.  Each index can be implemented as a hash table, binary tree, or any other data structure you like that provides fast lookups.

For instance, databases implement ideas like this to enable fast lookups and searches.