如何使用JQ高效为带父节点引用的JSON对象添加root_id属性

这是个典型的树形结构溯源问题，用JQ处理确实是最优选择之一，而且我们可以通过路径压缩的技巧来保证计算效率，避免重复遍历父节点带来的开销。

核心思路 #

要实现最高效的处理，关键在于两点：

• 先把所有节点存入哈希表（JQ里用对象实现），这样查找任意节点的时间复杂度都是O(1)
• 查找根节点时使用路径压缩：找到根节点后，把路径上所有节点的root_id都缓存起来，后续再访问这些节点时直接用缓存值，无需重复递归

完整JQ脚本 #

把下面的代码保存为add_root_id.jq：

# 第一步：将所有输入节点收集到以id为键的对象中
reduce inputs as $item ({};
  .[$item.id] = $item
) as $node_map
# 第二步：遍历每个节点，计算并添加root_id
| to_entries[]
| .value
| (
  # 定义递归函数：查找根节点，同时做路径压缩
  def find_root($current; $map):
    if $current.parent_id then
      # 先检查父节点是否已经有缓存的root_id
      if $map[$current.parent_id].root_id then
        $map[$current.parent_id].root_id
      else
        # 递归查找父节点的根，同时把父节点的root_id缓存下来（路径压缩）
        ($map[$current.parent_id] | find_root(.; $map)) as $root
        | ($map[$current.parent_id] |= . + {root_id: $root})
        | $root
      end
    else
      # 没有父节点，自己就是根节点
      $current.id
    end;
  # 调用函数获取当前节点的根ID
  find_root(.; $node_map) as $root_id
  # 为当前节点添加root_id属性
  | . + {root_id: $root_id}
)

使用方法 #

假设你的输入JSON流存在input.json文件中，运行以下命令：

jq -n -f add_root_id.jq input.json

测试效果 #

输入： #

{ "id": "123456789012345", "parent_id": "123456789012344" }
{ "id": "123456789012346", "parent_id": "123456789012345" }
{ "id": "123456789012344" }

输出： #

{"id":"123456789012345","parent_id":"123456789012344","root_id":"123456789012344"}
{"id":"123456789012346","parent_id":"123456789012345","root_id":"123456789012344"}
{"id":"123456789012344","root_id":"123456789012344"}

效率说明 #

这个方案的 amortized（均摊）时间复杂度接近O(n)：

• 第一阶段收集节点是O(n)
• 第二阶段的路径压缩确保每个节点最多被递归遍历一次，后续访问直接用缓存，避免了重复计算，尤其适合深度较大的树形结构

额外优化（可选） #

如果担心存在parent_id指向不存在节点的情况，可以在find_root函数里添加判断，避免报错：

def find_root($current; $map):
  if $current.parent_id and $map[$current.parent_id] then
    # 原逻辑不变
    if $map[$current.parent_id].root_id then
      $map[$current.parent_id].root_id
    else
      ($map[$current.parent_id] | find_root(.; $map)) as $root
      | ($map[$current.parent_id] |= . + {root_id: $root})
      | $root
    end
  else
    $current.id
  end;

内容的提问来源于stack exchange，提问作者wass rubleff