data store: change data structure

[oliver-sanders]

The data store contains level of the hierarchy:

• user
  • workflow
    • cycle
      • task
        • job

And additionally, via the familyTree (tree), $namespaces and $edges (indices):

• user
  • workflow
    • cycle
    • family
      • [family...]
        • task
    • namespace
    • edge

Each of these tiers is an array of items which is stored in (natural) alphabetical order so that the views which use this data can iterate over the store without sorting. E.G:

workflows: [
  'aaa',
  'bbb',
  'ccc'
]

This means that we have to insert/remove items from arbitrary positions in the list when nodes are added/removed.

These (splice) operations are O(n) which causes a high load on the data store. The load on the data store is especially critical as it cannot be reduced with optimisations such as virtual scrolling components or filtering.

To avoid this O(n) cost we would have to switch from arrays to a data structure which can perform these operations more efficiently.

• Array List
  • Split / join operations on linked lists are O(1) but locating the index is O(n).
  • An array list resolves this by maintaining a pointer to every nth item in the linked list to allow for faster index access.
• Sorted Binary Tree
  • A binary tree stores nodes in sort order using a fancy tree structure.
  • Insert/remove operations are O(log(n)).
  • Iteration is O(n) (but note each step of the iteration is more expensive, so poor performance for low n).

I had a go at the binary tree solution on this branch - https://github.com/oliver-sanders/cylc-ui/pull/new/data-store-binary-tree

But didn't get the results I wanted.