Efficient lookup when key is made of multiple elements and elements can be empty
This is the problem of building a data structure for storing rectangles in $m$-dimensional space, so you can answer stabbing queries efficiently.

For instance, if your keys have 4 elements, then we are in $m=4$ dimensions.  The key $(1,5,6,3)$ corresponds to a single point in 4-dimensional space.  The key $(1,?,6,3)$ corresponds to a line in 4-dimensional space.  The key $(2,?,?,?)$ corresponds to an (infinite) box in 4-dimensional space.

So, in general, each key can be thought of as an (axis-aligned) box in $m$-dimensional space.  A query is a point in $m$-dimensional space, and you want to find all boxes that contain that point.  That is sometimes known in the literature as a "stabbing query" (particularly when we're talking about intervals, i.e., $m=1$).

There are many data structures for this problem.  Take a look at R-trees, for example.  You can also look at $m$-dimensional segment trees.  It is known that you can build a $m$-dimensional segment tree in $O(n (\lg n)^m)$ time and $O(n (\lg n)^m)$ space; each lookup can be answered in $O(k + (\lg n)^m)$ time, where $k$ is the number of entries that match the query.  Thus, segment trees will likely be a good representation if the dimension $m$ is small.  (Optimizations: The exponent can be reduced slightly from $m$ to $m-1$.  There are also special algorithms that achieve even better performance in the case of $m=2$, $m=3$, or $m=4$.)

See also Data structure to hold list of rectangles?.