问最适合基于前缀的搜索的数据结构

EN

我必须在内存中维护键值对的数据结构。我有以下限制：

1. 键和值都是长度分别为256和1024的文本字符串。任何键通常看起来像k1k2k3k4k5，每个k(i)本身都是4-8字节的字符串。
2. 尽可能地，内存中的数据结构应该有连续的内存。我有400MB的键值对，并且允许120%的分配。(仅在需要时，元数据额外增加20%。) operations:
3. Add

DS将具有以下void del_kv(void *ds, char *key);

1. LookUp不频繁操作:典型签名看起来像void add_kv(void *ds, char *key, char *value);
2. DeleteInfrequent操作:典型签名看起来像void del_kv(void *ds, char *key);
3. LookUp最频繁操作:典型签名看起来像char *lookup(void *ds, char *key);
4. Iterate最频繁操作:此操作基于前缀。它分配一个迭代器，即迭代整个DS并返回与prefix_key匹配的键值列表(例如，"k1k2k3.*"，k(i)，如上定义)。每次迭代都会在此迭代器(列表)上迭代。释放迭代器将释放列表。通常期望Iterator在400MB DS (100KB:400MB :：1:4000)中返回100KB的键值对。典型的签名看起来像void *iterate(void *ds, char *prefix_key);
5. Bullet 6和Bullet 7是最频繁的操作，需要针对其进行优化。

我的问题是什么是最适合上述约束的数据结构？

我考虑过哈希。添加/删除/查找可以在o(1)中完成，因为我有足够的内存，但它不是迭代的最佳选择。散列的散列(在k1上散列，然后在k2上散列，然后在k3上散列...)或者散列的数组，但是它违反了第二条，我还有其他选择吗？