title: Data structure for partial multi-keys mapping?
body: <p>I have data consists of keys mapped to values, like this:</p>
  
  <pre><code>---------------------
  Key          | Value
  ---------------------
  (0, 0, 0, 0) | a
  (0, 0, 0, 1) | b
  (0, 1, 0, 1) | c
  (0, 1, 1, 0) | d
  ....
  </code></pre>
  
  <p>I am looking for a data structure the can efficiently perform search queries over keys, where the queries could be complete or partial specification the key. For example:</p>
  
  <pre><code>(0, 0, 0, 1) -&gt; a
  (0, *, *, *) -&gt; [a, b, c, d]
  (0, 1, *, *) -&gt; [c, d]
  </code></pre>
  
  <p>The idea that I've right now is to implement this using a regular tree, similar to this:
  <img src="https://i.imgur.com/vIBK3Qa.png" alt="tree">
  Leaves nodes represent the values and non-leaves nodes are parts of the key (i.e. w,x,y and z nodes are first, second, third and forth part of the key, respectively.). A simple BFS algorithm could be used to answer any query. But the problem is that this tree is growing exponentially with each new part of the key. </p>
  
  <p>What data structure/algorithm is more appropriate to solve this problem? Note that the key parts can be numbers or strings.</p>