在 LMDB 之上实现持久关联数组
Implementing persistent associative array on top of LMDB
我是键值存储的新手。我想尝试将 LMDB 作为持久关联数组，并希望能够使用长键，例如文件路径或 URL。
LMDB 定义编译时常量 MDB_MAXKEYSIZE=511 强加密钥长度的最大值。
我应该使用什么技术在 LMDB 上实现持久的长键字典？某种散列和冲突解决方案？或者用不同的 MAXKEYSIZE 重新编译，例如 2048？或者 LMDB 是这项工作的错误工具？
在我自己的使用中，我通过 SHA-256 散列任意长度的字符串键来处理类似的情况，从而为 B+ 树生成固定大小的 32 字节摘要键。该策略需要以下两个注意事项：
您完全失去了执行前缀字符串查找的能力。对于您所描述的用例，这通常不是什么大问题。
如果您需要能够枚举所有原始字符串键，则需要将原始字符串存储在另一个 LMDB 子数据库中，以便您可以根据SHA-256 摘要检索其对应的原始字符串——该字符串将作为 key/value 对的值存储在子数据库中，因此不受 MDB_MAXKEYSIZE 限制。这确实增加了 space 要求，为完整扫描中的每个游标操作添加了额外的树查找，并且不会按字典顺序生成字符串。如果您可以忍受这些限制，这是一种可行的方法。
对于不需要保留密钥顺序的情况，使用哈希算法生成较短摘要的建议非常有用。然而，在很多情况下顺序很重要，在这些情况下 LMDB 仍然是一个不错的选择。
例如，如果您试图查看公共父目录中以字母 "x" 开头的所有文件，那么您希望保留键的顺序。在这种情况下，您当然可以使用更大的最大密钥大小编译 LMDB。但这不是唯一的策略。
您可以使用密钥摘要保留密钥顺序的算法。您不会在密钥大小上有那么大的减少，但您可以 select 子目录的全部内容作为一个连续的组。
或者您可以将多维结构映射到您的键上。从根 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 中。此外，它为您可以在此结构之上构建的许多持久稀疏矩阵功能打开了大门。
但完全公开：也有缺点。要获得完整路径或按顺序列出文件，您必须不断递归遍历子目录，并且在此过程中需要多次访问磁盘。
所以最后还是要看自己在做什么，未来想去哪里，针对自己的具体情况选择最合适的关键设计策略。如果你的关键结构是正确的，那么你就可以避免在以后添加新功能时不得不丢弃所有代码。
我是键值存储的新手。我想尝试将 LMDB 作为持久关联数组，并希望能够使用长键，例如文件路径或 URL。
LMDB 定义编译时常量 MDB_MAXKEYSIZE=511 强加密钥长度的最大值。
我应该使用什么技术在 LMDB 上实现持久的长键字典？某种散列和冲突解决方案？或者用不同的 MAXKEYSIZE 重新编译，例如 2048？或者 LMDB 是这项工作的错误工具？
在我自己的使用中，我通过 SHA-256 散列任意长度的字符串键来处理类似的情况，从而为 B+ 树生成固定大小的 32 字节摘要键。该策略需要以下两个注意事项：
您完全失去了执行前缀字符串查找的能力。对于您所描述的用例，这通常不是什么大问题。
如果您需要能够枚举所有原始字符串键，则需要将原始字符串存储在另一个 LMDB 子数据库中，以便您可以根据SHA-256 摘要检索其对应的原始字符串——该字符串将作为 key/value 对的值存储在子数据库中，因此不受
MDB_MAXKEYSIZE限制。这确实增加了 space 要求，为完整扫描中的每个游标操作添加了额外的树查找，并且不会按字典顺序生成字符串。如果您可以忍受这些限制，这是一种可行的方法。
对于不需要保留密钥顺序的情况，使用哈希算法生成较短摘要的建议非常有用。然而，在很多情况下顺序很重要，在这些情况下 LMDB 仍然是一个不错的选择。
例如，如果您试图查看公共父目录中以字母 "x" 开头的所有文件，那么您希望保留键的顺序。在这种情况下，您当然可以使用更大的最大密钥大小编译 LMDB。但这不是唯一的策略。
您可以使用密钥摘要保留密钥顺序的算法。您不会在密钥大小上有那么大的减少，但您可以 select 子目录的全部内容作为一个连续的组。
或者您可以将多维结构映射到您的键上。从根 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 中。此外，它为您可以在此结构之上构建的许多持久稀疏矩阵功能打开了大门。
但完全公开：也有缺点。要获得完整路径或按顺序列出文件，您必须不断递归遍历子目录，并且在此过程中需要多次访问磁盘。
所以最后还是要看自己在做什么，未来想去哪里，针对自己的具体情况选择最合适的关键设计策略。如果你的关键结构是正确的，那么你就可以避免在以后添加新功能时不得不丢弃所有代码。