Формат хранения дерева JSON

Question

Это более концептуальный тип вопроса для хранения и обновления данных для дерева. Давайте возьмем общий пример - виртуальный дом из чего-то вроде React.

Общее хранилище json для дерева, представляющего dom, будет выглядеть примерно так:

{
  nodeId: 'nodeId1',
  ...nodeData,
  childrenNodes: [
    {
      nodeId: 'nodeId2',
      ...nodeData,
      childrenNodes: [...]
    },
    ...
  ]
}

Итак, я смотрю на дерево с BFS или DFS (я думаю, что React делает DFS), чтобы найти конкретный элемент для его изменения.

Другая возможная реализация этого же дерева может быть там, где я храню его, больше похожий на хеш-таблицу в формате:

{
  nodeId1: {...nodeData, childrenNodes: [nodeId2]},
  nodeId2: {...nodeData, childrenNodes: [nodeId3, nodeId4]},
  ...
}

Таким образом, получение определенного узла может быть потенциально O (1), поскольку мы просто хэшируем все идентификаторы узлов, вместо того, чтобы каждый раз обходить дерево.

Для чего-то вроде виртуального домена, где мы могли бы хранить состояние для десятков или даже сотен тысяч возможных элементов, я думаю, что хранение одного пути над другим было бы незначительным, но мы, вероятно, не хотели бы иметь обе структуры в памяти (хотя, может быть, было бы хорошо иметь и то и другое?).

Предполагая, что обеим структурам назначены идентификаторы для каждого узла, добавление и удаление узлов будет достаточно простым в обоих случаях. Можно также предположить, что в обоих случаях каждый дочерний элемент имеет ссылку на свой родительский узел.

Вопрос, который я задаю, состоит в том, какую структуру будет более целесообразно использовать в общем случае, или имеет смысл отслеживать обе структуры, если мы сосредоточены на обновлении узла или набора узлов как можно быстрее ? Если бы я собирался создать основу с нуля, я мог бы увидеть, что оба случая полезны для разных сценариев, но я должен был бы помнить об ограниченных устройствах памяти, таких как старые телефоны.

Answer 1

Никто не ответил, поэтому я просто выскажу свое мнение на основе дополнительных исследований и наблюдений.

Представленное хеш-решение было бы быстрее в некоторых сценариях для доступа к узлу. Однако удобочитаемость и расширение этого решения для других возможных интеграций делает его гораздо более сложной структурой. Если бы я собирался использовать эти массивы идентификаторов, я бы хотел сделать это как отдельную структуру, предназначенную только для поиска, но не для обновления сразу нескольких узлов.

Для большинства сценариев более подробный контур дерева будет иметь смысл и с ним будет легче работать.