如何从lmdb键值数据库反向重建树结构及调整键排序规则

反向重建原树结构的方案 #

你当前的键设计采用了点分隔的路径格式，本身已经完整携带了树的层级关系，不需要修改存储逻辑就可以直接完成重建，步骤如下：

• 先全量读取LMDB中的所有键值对，反序列化后存入临时映射表node_map，键为路径字符串，值为对应的node对象，同时给所有node对象新增children属性用来存储子节点
• 将所有节点按level字段升序排序（也可以按路径按点拆分后的长度排序），保证父节点永远比子节点先被处理
• 遍历排序后的节点，根节点（路径中不含点）直接作为树根，其他节点拆分路径得到父节点路径，从映射表中取出父节点后将当前节点加入父节点的子节点列表即可

参考实现代码：

import lmdb
import pickle

class node:
    def __init__(self, info, level = 0):
        self._info = info
        self.level = level
        self.children = [] # 新增子节点存储字段

# 读取LMDB所有数据
env = lmdb.open("test.lmdb")
txn = env.begin()
cursor = txn.cursor()

node_map = {}
for k, v in cursor:
    key_str = pickle.loads(k)
    curr_node = pickle.loads(v)
    curr_node.children = []
    node_map[key_str] = curr_node

root = None
for key_str, curr_node in node_map.items():
    # 处理根节点
    if '.' not in key_str:
        root = curr_node
        continue
    # 拼接父节点路径
    parent_key = '.'.join(key_str.split('.')[:-1])
    # 将当前节点加入父节点的子节点列表
    node_map[parent_key].children.append(curr_node)

处理完成后，root变量就是原树的根节点，可直接按需求遍历使用。

原树结构参考：

LMDB键排序特性说明 #

LMDB是基于B+树实现的持久化键值存储，键的排序是其核心设计，不支持关闭字典序排序特性，也无法原生保留写入顺序。
不过你的场景完全不需要依赖写入顺序，上述重建方法和LMDB默认的字典序排序完全兼容，甚至LMDB的前缀排序特性还可以帮你更高效地遍历单个子树：比如要遍历A节点下的所有后代节点，直接用A.作为前缀遍历即可，性能远高于全量遍历。
如果确实有需要按写入顺序遍历的场景，可自行在键前增加固定长度的自增序号前缀，例如000001:A、000002:A.B，此时按字典序遍历即可得到写入顺序，但你的需求不需要用到该方案。

内容的提问来源于stack exchange，提问作者Dibyendu Dey