mongoDB 中的迭代树

Question

我有这样一组数据（例如）：

{
    name : "john" ,
    _id : "0"
},
{
    name : "Richard" ,
    parent_id : "0" ,
    _id : "1"
},
{
    name : "Kevin" ,
    parent_id : "0" ,
    _id : "2"
},
{
    name : "William" ,
    parent_id : "1" ,
    _id : "3"
},
{
    name : "George" ,
    parent_id : "3" ,
    _id : "4"
}

我正在尝试编写一个函数来接收此节点任何深度的 _id 和 return 所有子节点，例如 _id = 0 我需要这样的东西：

[
    {
        name : "Richard" ,
        parent_id : "0" ,
        depth : "1" ,
        _id : "1"
    },
    {
        name : "Kevin" ,
        parent_id : "0" ,
        depth : "1" ,
        _id : "2"
    },
    {
        name : "William" ,
        parent_id : "1" ,
        depth : "2" ,
        _id : "3"
    },
    {
        name : "George" ,
        parent_id : "3" ,
        depth : "3" ,
        _id : "4"
    }
]

我编写了几个递归函数来迭代我的 mongodb 文档，但主要问题是我无法处理回调（异步）并且不知道何时以及如何结束递归函数。

如何使用 mongodb 和 node.js 执行此操作？任何想法都可能有用，谢谢。

Answer 1

您可以使用 2 个著名的算法来实现您的目标
BFS(Breath First search) and DFS(Depth First Search).
对于这个问题，BFS 比 DFS 好，因为你可以在 O(logn) 中跟踪你的树您也可以使用 DFS，但您必须以递归方式实现它并且运行时间将是 O(n) 并且因为您在 node js 中编码所以您必须实现它在异步中，实现它可能有点困难。
为了实现 BFS 算法，你必须使用异步 while 循环，因为你必须在你的 while 循环中有 mongo 查询，如果你使用正常的 javascript 你的 BFS 将无法工作，因为我们正在谈论 节点js不是php！！！
所以首先这是我在 BFS 代码中使用的异步 while 循环

function asyncLoop(iterations, func, callback ,foo) {
        var done = false;
        var loop = {
            next: function() {
                if (done) {
                    return;
                }

                if (iterations) {
                    func(loop);

                } else {
                    done = true;
                    if(callback) callback(foo);
                }
            },

            isEnd : function(){
                return done ;
            } ,

            refresh : function(it){
                iterations = it ;
            },

            break: function() {
                done = true;
                callback();
            }
        };
        loop.next();
        return loop;
    }

这是BFS算法节点js代码：

function bfs (_id ,callback){
    _id = String(_id);
    var q = [] ,res = [] ;

    db.tasks.findOne({ _id : _id }).lean().exec(function(err,root){
        root.depth = 0 ;
        q.push(root);

        asyncLoop(q.length ,function(loop){
            res.push(q[0]);
            db.tasks.find({ _parent : q[0]._id }).lean().exec(function(err,new_nodes){
                if(err) console.log(err);
                else {
                    var d = q[0].depth ;
                    q.shift();
                    loop.refresh(new_nodes.length + q.length);
                    if(new_nodes.length > 0){
                        new_nodes.forEach(function(new_node){
                            new_node.depth = d+1 ;
                            q.push(new_node);
                        });
                    }
                    loop.next();
                }
            });

        },function(){ callback(res) });
    });
}

注意：我还保存了每个查询的深度，因此您可以了解每个查询的深度并知道该查询在树中的位置。

mongoDB 中的迭代树

iterating tree in mongoDB

javascript

tree

mongodb

node.js