Интернет магазин китайских планшетных компьютеров

Компьютеры - Танцующее дерево

В информатике танцующее дерево — это древовидная структура хранения данных, которая похожа на B+trees. Она придумана Гансом Рейзером для использования в файловой системе Reiser4. По сравнению со сбалансированными бинарными деревьями, которые пытаются сохранить свои узлы сбалансированными постоянно, танцующие деревья сохраняют только баланс между узлами при записи данных на диск.

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

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