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

Question

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

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上散列...)或者散列的数组，但是它违反了第二条，我还有其他选择吗？

Answer 1

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

由于内存效率对您很重要，因此当一个叶块变满时，您应该尽可能在多个块之间重新分配密钥，以确保块总是>= 85%已满。块大小应该足够大，使得来自内部节点的开销只有几个%。

您还可以优化叶块中的存储，因为块中的大多数键都有一个长的公共前缀，您可以从较高级别的块中找出该前缀。因此，您可以从叶块中的键中删除公共前缀的所有副本，400MB的键值对占用的RAM将大大少于400MB。这将在一定程度上使插入过程复杂化。

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

Answer 2

我会将其实现为一个用于查找的哈希表，以及一个用于迭代的单独inverted index。我认为尝试将这些独立的关键片段转换为整数，就像您在Ways to convert special-purpoes-strings to Integers中要求的那样，是一堆不必要的工作。

对于C语言，已经有很多不错的哈希表实现，所以我不再赘述。

要为迭代创建倒排索引，请创建N个哈希表，其中N是键段的数量。然后，对于每个键，将其分成单独的段，并将该值的条目添加到适当的哈希表中。因此，如果您有密钥"abcxyzqgx"，其中：

k1 = abc
k2 = xyz
k3 = qgx

然后在k1哈希表中添加一个条目"abc=abcxyzqgx“。在k2哈希表中添加一个条目"xyz=abcxyzqgx“。在k3哈希表中添加"qgx=abcxyzqgx“。(当然，值不是字符串键本身，而是对字符串键的引用。否则，您将有O(nk)个256个字符的字符串。)

完成后，每个哈希表都有唯一的段值作为键，这些值是那些段所在的键的列表。

当您想要查找所有包含k1=abc和k3=qgx的键时，可以查询k1哈希表中包含abc的键的列表，查询k3哈希表中包含qgx的键的列表。然后对这两个列表进行交集，以获得结果。

构建单个哈希表的一次性成本为O(nk)，其中n是关键字的总数，k是关键字段的数量。内存需求也是O(nk)。诚然，这有点贵，但总共只有160万个密钥。

迭代的情况是O(m*x)，其中m是单个键段引用的平均键数，x是查询中的键段数。

一个明显的优化是将LRU缓存放在这个查找之前，以便从缓存中为频繁的查询提供服务。

另一种可能的优化是创建组合键的附加索引。例如，如果查询经常请求k1和k2，并且可能的组合相当小，那么使用组合的k1k2缓存是有意义的。因此，如果有人搜索k1=abc和k2=xyz，您就有了一个包含"abcxyz=list of keys“的关键字缓存。