5

由于以下内容有点长：这是 tl;dr; 版本：是否存在用于快速键和值查找的键/值最佳实践，例如具有持久索引的基于哈希的集合？

我对键值数据库的世界很感兴趣，但到目前为止还没有弄清楚如何有效地实现以下用例：

假设我们想要序列化一些数据并通过一个持久的、唯一的整数索引在其他地方引用它们。因此例如：Key = unsigned int，Value = MyData。

数据库应具有快速键查找并确保 MyData 是唯一的。

现在，当我在我的数据库中插入一个新值时，我可以为其分配一个新的索引键，例如数据库的当前大小或防止删除项目后发生冲突，我可以在外部保留一些计数器。

但是我如何确保我不会将相同的 MyData 值插入到我的数据库中？到目前为止，在我看来，键值数据库似乎无法有效地实现这一点 - 这是正确的吗？即我不想迭代整个数据库只是为了确保 MyData 值不在那里......

那么，实现这一点的最佳做法是什么？

背景：我在 KDevelop 上工作，我们使用上面的代码分析缓存。我们实际上有上述用例1的自定义实现。如果您对内部结构感兴趣，请搜索 Bucket 和 ItemRepository，有关 ItemRepository 的示例性用法，请参见2。

但是您可能会同意，这段代码很难理解，因此也很难维护。我想将其性能与可能导致代码更简单的替代解决方案进行比较——但前提是它不会导致严重的性能损失。考虑到围绕 OpenLDAP MDB、Kyoto Cabinet 和 LevelDB 等键值存储性能的炒作，这就是我想开始的地方。

我们在 KDevelop 中所拥有的——据我所知——基本上是一种混合的磁盘/内存哈希映射，它会定期保存到磁盘（这当然会在崩溃等情况下导致重大数据损坏）。 ）。项目根据它们的散列值存储在一个位置，只要散列函数速度快，这当然也允许相对快速的值查找。增加的转折是您还可以获得某种持久性数据库索引，可用于非常有效地查找项目。

所以——长话短说——如何用一个键/值数据库来做到这一点，比如 LevelDB、Kyoto Cabinet、OpenLDAP MDB——你说的吗？

4

3 回答 3

3

除非我在这里遗漏了一些东西——通常你的哈希算法是一致的，并且会为相同的数据提供相同的密钥。因此，您应该只需要查找密钥以查看它是否已经存在，或者处理数据库返回给您的（可能重复的密钥）错误。

afaik 键/值数据库可以并且将为您强制执行唯一的值约束，即如果您尝试保存已经存在的值，您将收到错误消息。

于 2012-12-26T19:24:33.330 回答
3

听起来您想做 OpenLDAP 对其平等索引所做的事情。也许这和OrientDB的例子一样，我没看过。

主表由一个单调递增的整数键（称为 entryID）索引，并存储数据值。相等索引由值的散列索引，并存储与散列匹配的 entryID 列表。由于散列可能有冲突，仅相等索引中的条目的存在并不能证明唯一性或重复性。您仍然需要检查实际值。

如果您使用 MDB、BDB 或其他支持重复键的数据库，一种更快/更简单的方法是只保留一个表，使用哈希作为键。在 MDB 和 BDB 中都有一个 GET_BOTH 请求，它匹配键和数据以执行提取。如果成功，那么您肯定知道该值已经存在。否则，它允许您保存任何数据值，而不必担心是否存在哈希冲突。

这里需要注意的是，在使用重复键的 MDB 中，值的大小限制为小于磁盘页面的一半。

于 2013-01-17T17:25:16.840 回答
0

你的价值字符串有多大？

我只是将它们存储在一个密钥中，让数据库完成所有工作。

适用于大多数 KV 存储的典型 LevelDB 样式是使用一对键，前缀表示类型

例如：

Key = 'i' + ID 
Value = valueString

Key = 'v' + valueString
Value = ID

在需要允许多个相同 valueStrings 的系统中，您可以将 ID 移动到第二个键的尾部

Key = 'v' + valueString + ID
Value = empty
于 2013-10-08T13:51:26.860 回答