How to arrange an javascript object for better performance

Question

I have a data object say -

const data = {
  'root': [
    {
      id: 1,
      name: 'demo',
      children: [
        {
          id: 2,
          name: 'demo2',
          children: [
            {
              id: 3,
              name: 'demo3',
              children: []
            },
            {
              id: 4,
              name: 'demo4',
              children: [
                {
                  id: 5,
                  name: 'demo5',
                  children: []
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

Now my question is if I want to perform an add/edit/delete operation, for an example, I want to edit an object which has the id = 5 then I have to visit root[0].children[0].children[1].children[0], this route and complete the task. I think it would be expensive and the object may have more nested children property.

So is there any other structure by which I can re-arrange my object and perform fast add/edit/delete operations?

"*I think it would be expensive*" two questions: 1. Why? 2. Is it going to be in any way significant? — VLAZ, Jul 21 '19 at 13:09
You could either save this in the form of a flat array with a `parentId` property for each item or use recursion to find the object and update it. — adiga, Jul 21 '19 at 13:13
Question is really too broad and hard to generalize since different structures can be easier to work with depending on use case. Lots of times using structure shown is actually easier — charlietfl, Jul 21 '19 at 13:16
I just want to add/edit/delete content from the object. But if I want to add something at any deep children then I have to visit from the root. I wanted something linear. @charlietfl — Sajeeb Ahamed, Jul 21 '19 at 13:20
@SajeebAhamed something like the array [in this question](https://stackoverflow.com/questions/18017869) — adiga, Jul 21 '19 at 13:20

score 2 · Accepted Answer · answered Jul 21 '19 at 13:23

Since the id values are unique, you can maintain a Map (or object) that directly refers to the entries, regardless of where they are in the parent/child structure. The parent/child structure would simply contain the id of the children rather than the actual child object, for instance:

const data = {
    1: {
        id: 1,
        name: 'demo',
        children: [2]
    },
    2: {
        id: 2,
        name: 'demo2',
        children: [3, 4]
    },
    3: {
        id: 3,
        name: 'demo3',
        children: []
    },
    4: {
        id: 4,
        name: 'demo4',
        children: [5]
    },
    5: {
        id: 5,
        name: 'demo5',
        children: []
    }
};

Accessing by ID is simply data[id].

That example uses an object with numeric string keys (they're written as literal numbers above, but property names are always strings [or Symbols]). But you could use a Map instead:

const data = new Map([
    [1, {
        id: 1,
        name: 'demo',
        children: [2]
    }],
    [2, {
        id: 2,
        name: 'demo2',
        children: [3, 4]
    }],
    [3, {
        id: 3,
        name: 'demo3',
        children: []
    }],
    [4, {
        id: 4,
        name: 'demo4',
        children: [5]
    }],
    [5, {
        id: 5,
        name: 'demo5',
        children: []
    }]
]);

Those map keys are actually numbers. Accessing by ID is simply data.get(id) and data.set(id, newEntry).

You'll want to have functions to operate on this structure (adding, removing, moving). You could use standalone functions that accept the structure, for instance:

function removeEntry(data, id) {
    const entry = data[id];
    for (const childId of entry.children) {
        removeEntry(data, childId);
    }
    delete data[id]; // The object version
    // Or: data.delete(id); // The Map version
}

...or you could bundle all this into a class.

That means it's adding/editing operations are linear (just push it and push the id into the parent's children array) but remove operation needs all the children to remove recursively. — Sajeeb Ahamed, Jul 21 '19 at 13:31
@SajeebAhamed - Adding isn't linear, it's near-constant. Removing is most easily done with recursion, yes. (It *could* be done with a loop, but it's more complicated. Unless you expect nesting so that you recurse more than about 30k times, you don't need to worry about the recursion on modern engines.) — T.J. Crowder, Jul 21 '19 at 13:44

score 1 · Answer 2 · answered Jul 21 '19 at 13:11

It's not that expensive and maybe it's not worth "improving" anything unless you measure and have hard evidence that this part of your program is slow.

If you really wanted to make this faster though, then you could create a second data structure with references to all elements. For example:

const refs = {
  1: data['root'][0],
  2: data['root'][0]['children'][0],
  3: ...
}

and then whenever you wanted the element with id 2 you'd simply do refs[2]. You can of course generate that refs object automatically and not by hand.

score 0 · Answer 3 · answered Jul 21 '19 at 13:18

0

instead of nested structure, define foreign key(fId) like this:

const data = {
      'root': [
        {
            id: 1,
            name: 'demo',
            fId:[]
        },
        {
            id: 2,
            name: 'demo2',
            fId:[1]
        },
        {
            id: 3,
            name: 'demo3',
            fId:[2]
        },
        {
            id: 4,
            name: 'demo4',
            fId:[3]
        },
        {
            id: 5,
            name: 'demo5',
            fId:[4]
        }
      ]
    }

answered Jul 21 '19 at 13:18

Masoud

332
2
9

What if I want to delete a parent node? This needs to find and remove all the children too. – Sajeeb Ahamed Jul 21 '19 at 13:22
Base on work, that's is different, in worst case in delete, must be write a loop to remove parent – Masoud Jul 21 '19 at 13:42

How to arrange an javascript object for better performance

3 Answers3