Proposal: Make the tree model more performant

[michaelspiss]

The current tree model negates all performance benefits of the tree data structure by defining the relationships the opposite way (the "parent" attribute on the child instead of a "children" array attribute on the parent). This requires going through every node on every render to check if something changed. This is a huge performance hit. I recommend going the opposite way:

[
  { "id": 0, "children": [1,3], ... },
  { "id": 1, "children": [2], ... },
  { "id": 2, "children": [], ... },
  { "id": 3, "children": [], ... }
]

This allows the tree to stop looking for changes if for example node 1 is closed. It wouldn't matter what nodes are inside. To make it even more performant, one could add the id as a key to allow for lookups in O(1) instead of O(n):

{
  0: { "id": 0, "children": [1,3], ... },
  1: { "id": 1, "children": [2], ... },
  2: { "id": 2, "children": [], ... },
  3: { "id": 3, "children": [], ... }
}

[minop1205]

@michaelspiss

Thanks for the suggestion. I will consider it carefully as it will require major modifications and disruptive changes. I will release v2 soon, but at least v3 or later.

Note that in the current tree model, child nodes are first searched from the parent node, and descendant nodes are traversed recursively only if the parent is open and the child exists. So, if the parent is closed, the children are not rendered, but is that enough of a problem?

I also want to consider which model is easier for users to handle.

[michaelspiss]

Sure - I saw that you are working on a v2 so I wanted to leave this suggestion here.

Finding a child node requires going through the whole dataset for each rendered node - that's what's worried me.

This is merely a suggestion for better performance, especially on low end devices. It is not required (works fine for 1000 nodes on my machine).

[kimgysen]

In order to simply verify whether a node has children (eg in order to show a caret if there are child nodes), it seems easy with the above proposed model. Needs custom calculation / adding a prop children yourself with the current implementation. Great library otherwise.

[FullstackJack]

1. Seems to me the most performant data structure for the node tree is an Object or Map. O(1) lookup vs O(n) lookup seems pretty straight forward in terms of which data structure should be chosen. Are there any operations that require the tree be traversed in insertion order? If so, there are iterators for Object and Map that could be accessed. If you want to build a tree from an Object/Map, you could store a rootId or hardcode a hidden node like node0.
2. Also, I tried switching the id and parent fields to strings and now nothing shows up. It would be great if we could control provide our own data structures and getter methods for getting a hold of those fields. For instance, I might have a data structure with a parentId instead of parent.

Great library, unfortunately, I'm considering having to roll my own to meet the performance requirements.