0

I have a class that looks something like this:

class Entity
{
    public string Id { get; set; }
    public List<Entity> Children { get; set; }
    
    public void DoStuff(Data data)
    {
        // stuff
        
        foreach (var child in Children)
        {
            child.DoStuff(data);
        }
    }
}

And I need to persist this in a database. Available options: MongoDB, SQL server or PostgreSQL.

I was wondering what is the best approach for storing this kind of tree data considering these conditions:

  • Read performance is most important when the whole tree is queried - parent with all of its descendants.
  • Usually only one child will be present per Entity in the Children list. But the depth of the tree could be 50-100.
  • Once the parent is created I need to be able to add/delete children. But the speed of this operation is not that important.

In JSON data looks like this:

{
    "id": "xyz_0",
    "children": [
        {
            "id": "xyz_1",
            "children": [
                {
                    "id": "xyz_2",
                    "children": [

                    ]
                },
                {
                    "id": "xyz_3",
                    "children": [

                    ]
                }
            ]
        }
    ]
}

At the moment I'm using MongoDB and storing a single tree per JSON document. And the application code looks something like this:

var entity = mongoCollection
    .Find(Builders<Entity>
        .Filter
        .Eq(o => o.Id, parentId))
    .SingleOrDefault();

foreach (var data in GetData(10000))
{
    entity.DoStuff(data);
}

But reading a couple of previous posts here and here mentions that it's not such a great idea to store big documents. So I'm looking for alternatives.

  • What have your benchmarks shown? How does your application perform when using big documents versus many small documents? And what about range selection? ... Can you put identifiers or sort keys on documents that necessary put them "under" their ancestors. 1 -> 1.1 -> 1.1.1 ... 1 -> 1.9 -> 1.9.9 ... select * from table where sort_key >= 1 and sort_key < 2? – svidgen Dec 16 '20 at 16:08
  • There is an algorithm for this in relational but i can't recall the name :/ the basic idea is that you assign anumber to every entity. Non-leaf entities also get two more fields: a child_min and child_max. You set the fields such that the numbers of all children are between their parent's child_min and child_max. To query a (sub)-tree you do SELECT * FROM entity parent JOIN entity child ON child.number BETWEEN parent.child_min AND parent.child_max. You have to build the actual tree structure in-memory then, but that's certainly quick with only 100-200 entities in a tree. – marstato Dec 16 '20 at 16:12
  • In general, to facilitate retrieval, trees are stored in depth-first order. Example. However, when it comes to databases, the main concern is the need for tree rebalancing (tree rotation), the frequency and the workload where such long operations must be performed, and how much write amplification may result from such operations. – rwong Dec 16 '20 at 16:43
  • If each tree is seldom (never) modified after initial creation, there may be a way to preprocess it into a form that facilitates traversal. If modification happens quite a few times, it may be necessary to consider the performance of modifications. – rwong Dec 16 '20 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.