title: Best suited data-structure for prefix based searches
body: <p>I have to maintain a in-memory data-structure of Key-Value pair. I have following constraints:</p>
  
  <ol>
  <li>Both key and values are text strings of length 256 and 1024
  respectively. Any key generally looks like k1k2k3k4k5, each k(i) being 4-8 byte string in itself.</li>
  <li>As far as possible, in-memory data-structure should have contiguous memory. I have 400 MB worth of Key-Value pair and am allowed 120% worth of allocation. (Additional 20% for metadata, only if needed.)</li>
  <li>DS will have following operations:</li>
  <li>Add [Infrequent Operation]: Typical signature looks like <code>void add_kv(void *ds, char *key, char *value);</code></li>
  <li>Delete[Infrequent Operation]: Typical signature looks like <code>void del_kv(void *ds, char *key);</code></li>
  <li>LookUp [MOST FREQUENT OPERATION]: Typical signature looks like <code>char *lookup(void *ds, char *key);</code></li>
  <li>Iterate [MOST FREQUENT OPERATION]: This operation is prefix based. It allocates an iterator i.e iterates the whole DS and returns list of key-values that match prefix_key (e.g. "k1k2k3.*", k(i) defined as above). Every iteration iterates on this iterator(list). Freeing the iterator frees the list. Typically expect an Iterator to return 100 KB worth of key-value pair in 400 MB DS (100KB:400 MB :: 1:4000). Typical signature looks like <code>void *iterate(void *ds, char *prefix_key);</code></li>
  <li>Bullet 6 and Bullet 7 being most frequent operation, needs to be optimized for.</li>
  </ol>
  
  <p>My question is what is the best suited data-structure for above constraints?</p>
  
  <p>I have considered hash. Add/delete/lookup could be done in o(1) as I have sufficient memory but it is not optimum for iteration. Hash-of-hash (hash on k1 then on k2 then on k3...) or array of hash could be done but it then violates Bullet 2. What other options do I have?</p>