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

Question

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

1. 键和值都是长度为 256 和 1024 的文本字符串 分别。任何键通常看起来像 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. 查找 [最频繁的操作]：典型的签名看起来像char *lookup(void *ds, char *key);
7. 迭代 [最频繁的操作]：此操作基于前缀。它分配一个迭代器，即迭代整个 DS 并返回与prefix_key匹配的键值列表(例如"k1k2k3.*"，k(i) 如上所述)。每次迭代都迭代这个迭代器(列表)。释放迭代器会释放列表。通常期望迭代器在 400 MB DS (100KB：400 MB ：： 1：4000) 中返回 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

由于内存效率对您很重要，因此当叶块已满时，如果可能，您应该在多个块之间重新分配密钥，以确保块始终>= 85% 已满。 块大小应该足够大，以至于内部节点的开销只有几%。

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

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

Answer 2

我会将其实现为用于查找的哈希表，以及用于迭代的单独倒排索引。我认为试图将这些单独的键段转换为整数，正如您在将特殊目的字符串转换为整数的方法中要求的那样，这是一堆不必要的工作。

已经有很多好的 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=[键列表]"的 k1k2 缓存。

Answer 3

我会使用五个并行哈希表，对应于人们可能搜索的五个可能的前缀。每个哈希表槽将包含零个或多个引用，每个引用包含该特定键值对的前缀长度、该键前缀的哈希以及指向实际键和数据结构的指针。

对于删除，实际的键和数据结构将包含所有五个前缀长度和相应的哈希，以及键和值的字符数据。

例如：

#define  PARTS  5
struct hashitem {
size_t            hash[PARTS];
size_t            hlen[PARTS];
char             *data;
char              key[];
};
struct hashref {
size_t            hash;
size_t            hlen;
struct hashitem  *item;
};
struct hashrefs {
size_t            size;
size_t            used;
struct hashref    ref[];
};
struct hashtable {
size_t            size[PARTS];
struct hashrefs **slot[PARTS];
};

在struct hashitem中，如果key是k1k2k3k4k5，则hlen[0]=2、hash[0]=hash("k1")、hlen[1]=4、hash[1]=hash("k1k2")等等，直到hlen[4]=10，hash[4]=hash("k1k2k3k4k5")。

当插入一个新的键值对时，首先会找出前缀长度(hlen[])和它们对应的哈希(hash[])，然后按照以下几行调用一个辅助函数

static int insert_pair(struct hashtable *ht,
const char       *key,
const size_t      hash[PARTS],
const size_t      hlen[PARTS],
const char       *data,
const size_t      datalen)
{
struct hashitem *item;
size_t           p, i;
/* Verify the key is not already in the
hash table. */
/* Allocate 'item', and copy 'key', 'data',
'hash', and 'hlen' to it. */
for (p = 0; p < PARTS; p++) {
i = hash[p] % ht->size[p];
if (!ht->entry[i]) {
/* Allocate a new hashrefs array,
with size=1 or greater, initialize
used=0 */
} else
if (ht->entry[i].used >= ht->entry[i].size) {
/* Reallocate ht->entry[i] with
size=used+1 or greater */
}
ht->entry[i].ref[ht->entry[i].used].hash = hash[p];
ht->entry[i].ref[ht->entry[i].used].hlen = plen[p];
ht->entry[i].ref[ht->entry[i].used].item = item;
ht->entry[i].used++;
}
return 0; /* Success, no errors */
}

前缀查找与使用完整键的哈希表查找相同：

int lookup_filter(struct hashtable *ht,
const size_t      hash,
const size_t      hashlen,
const size_t      parts, /* 0 to PARTS-1 */
const char       *key,
int (*func)(struct hashitem *, void *),
void             *custom)
{
const struct hashrefs *refs = ht->entry[parts][hash % ht->size[parts]];
int                    retval = -1; /* None found */
size_t                 i;
if (!refs)
return retval;
for (i = 0; i < refs->used; i++)
if (refs->ref[i].hash == hash &&
refs->ref[i].hlen == hashlen &&
!strncmp(refs->ref[i].item->key, key, hashlen)) {
if (func) {
retval = func(refs->ref[i].item, custom);
if (retval)
return retval;
} else
retval = 0;
}
return retval;
}

请注意使用的回调样式，以允许单个查找匹配所有前缀。 假设唯一键的完整键匹配会稍微简单一些：

struct hashitem *lookup(struct hashtable *ht,
const size_t      hash,
const size_t      hashlen,
const char       *key)
{
const struct hashrefs *refs = ht->entry[PARTS-1][hash % ht->size[PARTS-1]];
size_t                 i;
if (!refs)
return NULL;
for (i = 0; i < refs->used; i++)
if (refs->ref[i].hash == hash &&
refs->ref[i].hlen == hashlen &&
!strncmp(refs->ref[i].item->key, key, hashlen))
return refs->ref[i].item;
return NULL;
}

删除将利用查找，除了可以通过将匹配条目替换为同一引用数组中的最后一项来删除匹配项;或者如果该项是引用数组中唯一的项，则完全释放整个数组。

使用引用数组(每个哈希表条目多个数据项)是可以接受的原因是，当前处理器将数据缓存在块中(缓存行是缓存的最小块)。由于每个哈希表槽都包含一个或多个匹配项，并且具有代码的完整哈希和哈希长度，因此需要逐字节比较以确定实际匹配的实际冲突对于快速简单的哈希函数来说也非常罕见。(我希望每个匹配条目有 1.05 到 1.10 个字符串比较，即使像 DJB2 哈希这样简单的东西也是如此。

换句话说，此方法尝试最小化访问的缓存行数以查找所需的对。

由于初始部分将具有大量重复哈希(相对较少的唯一前缀哈希)和哈希长度，因此使其哈希表更小可能更有效。(引用数组将更大。 由于哈希和哈希长度不会更改，因此可以随时调整任何哈希表的大小，而无需重新计算任何哈希。

请注意，由于除PARTS-1哈希表之外的所有哈希表都用于扫描项目集，因此它们的引用数组可能会变得很长并不是一件坏事：无论如何，这些数组将几乎只包含人们正在查找的项目！(换句话说，如果一个参考数组增长到10,000个条目长，如果它被用来找到所需的9,750个条目左右，这不是问题。

我个人也确实考虑过某种表格，例如，每个关键部分都是表格中的一个附加级别。但是，查找具有给定前缀的条目集涉及表遍历和相当分散的内存访问。我相信，但尚未验证(使用比较这两种方法的微基准测试)，每个插槽具有潜在大型参考数组的哈希表在运行时更有效。