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

Question

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

1. 键和值都是长度为256和1024的文本字符串 分别。任何 key 通常看起来像 k1k2k3k4k5，每个 k(i) 本身都是 4-8 字节的字符串。
2. 内存中的数据结构应尽可能具有连续的内存。我有 400 MB 的键值对，允许 120% 的分配。 (仅在需要时为元数据额外支付 20%。)
3. DS 将具有以下操作:
4. 添加 [不常操作]:典型的签名看起来像 void add_kv(void *ds, char *key, char *value);
5. 删除[不常操作]:典型的签名看起来像void del_kv(void *ds, char *key);
6. LookUp [最频繁的操作]:典型的签名看起来像 char *lookup(void *ds, char *key);
7. 迭代[最频繁的操作]:这个操作是基于前缀的。它分配一个迭代器，即迭代整个 DS 并返回匹配 prefix_key 的键值列表(例如“k1k2k3.*”，k(i) 定义如上)。每次迭代都在此迭代器(列表)上迭代。释放迭代器释放列表。通常期望迭代器在 400 MB DS (100KB:400 MB::1:4000) 中返回值(value) 100 KB 的键值对。典型的签名看起来像 void *iterate(void *ds, char *prefix_key);
8. 第 6 条和第 7 条操作最频繁，需要优化。

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

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

Answer 1

我可能会为此使用 B+ 树之类的东西:https://en.wikipedia.org/wiki/B%2B_tree

由于内存效率对您很重要，当叶 block 变满时，您应该尽可能在多个 block 之间重新分配 key ，以确保 block 总是 >= 85% 满。 block 大小应该足够大，以使内部节点的开销仅为百分之几。

您还可以优化叶 block 中的存储，因为 block 中的大多数键都有一个很长的公共(public)前缀，您可以从更高级别的 block 中找出该前缀。因此，您可以从叶 block 中的键中删除公共(public)前缀的所有副本，并且您的 400MB 键值对占用的 RAM 将大大少于 400MB。这会使插入过程稍微复杂一些。

您还可以做其他事情来进一步压缩此结构，但这会很快变得复杂，而且听起来您并不需要它。