我是键值存储的新手。我想尝试将 LMDB 作为持久关联数组,并希望能够使用长键,例如文件路径或 URL。
LMDB 定义了编译时常量 MDB_MAXKEYSIZE=511,对密钥长度施加了最大值。
我应该使用什么技术在 LMDB 之上实现持久的长密钥字典?某种散列和冲突解决方案?或者使用不同的 MAXKEYSIZE 重新编译,例如 2048?或者 LMDB 对于这项工作来说是一个错误的工具?
我是键值存储的新手。我想尝试将 LMDB 作为持久关联数组,并希望能够使用长键,例如文件路径或 URL。
LMDB 定义了编译时常量 MDB_MAXKEYSIZE=511,对密钥长度施加了最大值。
我应该使用什么技术在 LMDB 之上实现持久的长密钥字典?某种散列和冲突解决方案?或者使用不同的 MAXKEYSIZE 重新编译,例如 2048?或者 LMDB 对于这项工作来说是一个错误的工具?
在我自己的使用中,我通过SHA-256散列任意长度的字符串键来处理类似的情况,为 B+ 树生成一个固定大小的 32 字节摘要键。该策略需要以下两个注意事项:
您确实完全失去了执行前缀字符串查找的能力。对于您描述的用例而言,这通常不是一个重大问题。
如果您需要能够枚举所有原始字符串键,则需要将原始字符串存储在另一个 LMDB 子数据库中,以便您可以基于 SHA-256 摘要执行查找以检索其对应的原始字符串--这将作为键/值对的值存储在子数据库中,因此MDB_MAXKEYSIZE
不受限制。这确实增加了空间需求,为全扫描中的每个游标操作添加了额外的树查找,并且不会产生按字典顺序排列的字符串。如果您可以容忍这些限制,那么这是一种可行的方法。
对于不需要保留密钥顺序的情况,建议使用散列算法生成较短的摘要。然而,在很多情况下,顺序很重要,在这些情况下,LMDB 仍然是一个很棒的选择。
例如,如果您尝试查看公共父目录中以字母“x”开头的所有文件,那么您希望保留键的顺序。在这种情况下,您当然可以使用更大的最大密钥大小来编译 LMDB。但这不是唯一的策略。
您可以利用密钥摘要保留密钥顺序的算法。您不会大幅减少密钥大小,但您可以选择子目录的全部内容作为连续组。
或者您可以将多维结构映射到您的键上。从根 ID 0 开始,每个子目录都被赋予一个唯一的目录 ID,并且文件和子目录条目被分组在一个共同的父目录 ID 内。
[DirID,filename] = null - the null value means it's a file.
[DirID,dirname] = DIRID - the ID means it's a subdirectory.
这有很多好处。密钥长度适用于每个文件和目录名称,而不适用于完整目录路径。所以你不必重新编译 LMDB。它还可以节省内存,因为完整路径不会一遍又一遍地重复。并且文件和目录排序顺序保留在每个父目录 ID 中。此外,它还为您可以在此结构之上构建的许多持久稀疏矩阵功能打开了大门。
但全面披露:也有一个缺点。要获取完整路径或按顺序列出文件,您必须不断递归子目录,并且在此过程中会多次访问磁盘。
所以最后,你要看看你在做什么,未来你想去哪里,为你的具体情况选择最合适的关键设计策略。如果你得到了正确的关键结构,那么你可以避免以后在添加新功能时丢弃所有代码。