Maintaining multiple field dynamic values This question is posted on behalf of my friend, who is a networks engineer handling massive data (so not a toy problem). He needs to maintain a lookup/insertion/deletion structure storing nodes with multiple attributes. That is, there is a set of $k$ global properties, or key/value fields, where each node may maintain only a subset of them. E.g, $A$ is ($x=1$), $B$ is ($x=1$,$y=4$), $C$ is ($x=1$,$z=5$), where $x$, $y$, and $z$ are attributes. There should be no repetition of nodes, although one may be a subset of another in it's filled values. For example, here node $A$ is a subset of $B$.

The structure would initially be constructed from a large amount of nodes "on disk" (let us call this parameter $n$) in preprocessing and then would go in live query mode. Whenever a new query $Q$ comes in, the query $Q$ will also have between 1 to $k$ of the key/value pairs filled. The structure has to specify ALL matching nodes of the structure (e.g, $A(x=1)$, $B(y=4)$, $C(x=1,y=4)$ all would match $Q(x=1,y=4)$) and if $Q$ does not already exist in the structure, it has to be inserted. Given a query node, $Q$, a matching node $M$ is defined to be such that it's filled key-value pairs are a superset of those of $Q$

Which data structure would produce such a result in optimal insertion/lookup/deletion time, and of course, linear storage? Both amortized and worst case guarantees would be interesting, since this structure will handle a large number of queries. A link to relevant papers or literature would also help.

I thought about posting this on stackoverflow, but in this case the engineer is looking for a sound algorithm, not code, and preferably with theoretical performance guarantees. Apologies if it is fairly trivial for someone well-versed in data structures.
One possibility (that depends on the relative size of the attribute set and the record set) is to use an inverted index, which is a wildly successful structure for use in text searching. Rather than storing the documents and doing a search, you store a list of which documents contain which value of which attribute for each attribute value pair (again, this only works if the number of attribute-value pairs is not large). Then processing a query requires an intersection of the resulting lists.