Храните иерархии таким образом, чтобы она была устойчивой к коррупции

Question

Сегодня я думал о наилучшем способе хранения иерархического набора узлов, например,

_{(источник: www2002.org )}

Наиболее очевидный способ представить это (по крайней мере, мне) для каждого узла иметь указатели nextSibling и childNode, каждый из которых может быть нулевым.

Имеет следующие свойства:

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

Другой метод, который вы можете использовать, - это создать систему координат, например, 1.1, 1.2, 1.2.1, 1.2.2. 1.2.3 будет 3-м узлом на 3-м уровне, а 2-й узел на предыдущем уровне будет его родителем. Непредвиденная потеря узла не повлияет на способность разрешать любые другие узлы. Однако добавление узла где-либо может привести к изменению координат для большого числа других узлов.

Какими способами вы могли бы хранить иерархию узлов, которая требует нескольких изменений для добавления или удаления узла и устойчива к повреждению нескольких узлов? (не зависит от реализации)

Answer 1

Типичным способом хранения иерархии является наличие свойства / поля ParentNode в каждом узле. Для root ParentNode имеет значение null, для всех остальных узлов он имеет значение. Это означает, что дерево может потерять целые ветви, но в памяти это кажется маловероятным, и в БД вы можете защититься от этого, используя ограничения.

Этот подход напрямую не поддерживает поиск всех братьев и сестер, если это требование, я бы добавил другое свойство / поле для глубины, корень имеет глубину 0, все узлы ниже корня имеют глубину 1 и так далее. Все узлы с одинаковой глубиной являются братьями и сестрами.

Answer 2

Когда вы говорите о повреждении, вы говорите об оперативной памяти или каком-либо другом хранилище? Возможно, во время передачи по некоторой среде?

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

Когда вы говорите о потере узла, первое, что вы должны выяснить, это «как узнать, что я потерял узел?», Это обнаружение ошибок.

Что касается проблемы защиты данных от повреждения, практически единственный способ сделать это с избыточностью. Степень избыточности определяется тем, какой предел вы хотите наложить на уровень коррупции, который вы хотели бы восстановить. Вы не можете реально защитить себя от этого с помощью продуманной структуры, так как вы, скорее всего, будете страдать от коррупции в критической «умной» части вашей структуры :)

Википедия всегда полезна: Обнаружение и исправление ошибок

Answer 3

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

Другой интересный вариант - хранить информацию об иерархии в виде таблицы потомков (транзитивного замыкания). Таким образом, для узла 1.2.3 вы должны иметь следующие отношения:

1., 1.2.3. - корневой узел является восходящим из 1.2.3.

1.2., 1.2.3. - 1.2. узел является восходящим 1.2.3.

1., 1.2. - корневой узел является восходящим из 1.2. и т.д ...

Эта таблица может быть более устойчивой к ошибкам, поскольку содержит некоторую избыточную информацию.

Goran

Answer 4

Сегодня я думал о лучшем способе хранения иерархического набора узлов

Так вы пишете файловую систему? ; -)

Самый очевидный способ представить это (по крайней мере, мне) для каждого узла иметь указатели nextSibling и childNode

Почему? Информация о сестре присутствует на родительском узле, поэтому все, что вам нужно, это указатель на родительский узел. Дважды связанный список, так сказать.

Каким образом вы можете хранить иерархию узлов, которая требует нескольких изменений для добавления или удаления узла и устойчива к повреждению нескольких узлов?

Здесь на самом деле есть два разных вопроса.

• Данные повреждены?
• Как исправить поврежденные данные (также известные как системы самовосстановления)?

Ответы на эти два вопроса определят точную природу решения.

Повреждение данных

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

Самовосстанавливающиеся структуры

Любая самоизлечивающаяся структура будет нуждаться в следующей информации:

• Есть ли коррупция? (См. Выше)
• Где коррупция?
• Можно ли это исцелить?

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

Я полагаю, что есть некоторая возможность сузить ваш вопрос до такой степени, чтобы мы могли начать обсуждение отдельных кусочков головоломки.