javascript - 在通用树中查找元素

Question

我有一个 json 嵌套对象，类似于 this .

在我的例子中，我有一个唯一的 id 类型的 int 字段(比如上面的 name)。这不是二叉树，而是更多描述父子关系。我想要一种方法来轻松查找以 id = 121 为根的子树(children)。以蛮力的方式，我可以比较所有节点直到找到一个节点，然后返回 child 。但我想保留 {id, node} 的 map 。例如 {"121": root[1][10]..[1]}。这可能是内存的 super 浪费(除非使用指向数组的指针)。请注意确保有更好的方法。

我可以控制从服务器发送的内容，因此可以扩充上述数据结构。但需要一种快速的方法来根据客户端的节点 ID 获取子树。

编辑:我正在考虑保留另一个数据结构，{id, []ids} 的映射，其中 ids 是从根开始的有序路径。有什么更好的方法吗？

Answer 1

javascript 中的对象是真正的基于指针的对象，这意味着您可以在不使用更多内存的情况下保留对它们的多个引用。为什么不进行一次遍历，将子对象分配给一个新的基于 id 的父对象？除非您的分层对象非常庞大，否则这应该非常快。

根据最佳实践以及如果您正在构建的应用程序扩展到数百万用户会发生什么情况，您可能会重新考虑是否真的希望服务器完成更多工作。客户的电脑就在那里，随时准备免费为您提供远程计算能力。为什么将工作负载转移到服务器以使其每秒处理更少的客户端请求？这可能不是您想要的方向。

Here is a fiddle demonstrating this index-building technique .您运行一次，然后根据需要一遍又一遍地使用索引。建立所述索引只需要 4 或 5 毫秒。没有性能问题!

还有一点要注意:如果您担心带宽，一种简单的方法可以帮助您减少 JSON。不要在对象键名称周围加上引号，使用单字母键名称，并且不要使用空格和换行符。那会让你有很大的进步。对示例 JSON 执行此更改后，它从 11,792 个字符变为 5,770 个，仅为原始大小的 49%!

一个小注意事项是 javascript 中的对象键始终是字符串。当用作键名时，我添加到您的示例 JSON 中的数字 ID 被强制转换为字符串。这应该不会妨碍使用，但这是您可能需要注意的细微差别。