Войти
В информатике танцующее дерево - это древовидная структура данных, аналогичная деревьям B +. Он был изобретен Гансом Рейзером для использования в файловой системе Reiser4. В отличие от самобалансирующихся двоичных деревьев поиска, которые пытаются постоянно поддерживать баланс своих узлов, танцующие деревья балансируют свои узлы только при сбросе данных на диск (либо из-за ограничений памяти, либо из-за завершения транзакции
Смысл этого состоит в том, чтобы ускорить операции файловой системы за счет задержки оптимизации дерева и записи на диск только при необходимости, поскольку запись на диск в тысячи раз медленнее, чем запись в память. Кроме того, поскольку эта оптимизация выполняется реже, чем с другими древовидными структурами данных, оптимизация может быть более обширной.
В некотором смысле это можно рассматривать как самобалансирующееся двоичное дерево поиска, которое оптимизировано для хранения на медленном носителе, поскольку дисковая форма всегда будет сбалансированной, но не получит середины. транзакция пишет; это облегчает (в то время) сложность добавления и удаления узлов и вместо этого выполняет эти (медленные) операции перебалансировки одновременно с (гораздо более медленной) записью на носитель.
Однако (отрицательный) побочный эффект такого поведения наблюдается в случаях неожиданного завершения работы, неполной записи данных и других событий, которые могут помешать завершению финальной (сбалансированной) транзакции. Как правило, «танцующие» деревья представляют большую трудность для восстановления данных из незавершенных транзакций, чем обычное дерево; хотя это можно решить, либо добавив дополнительные журналы транзакций, либо разработав алгоритм для поиска данных на диске, которые ранее не присутствовали, а затем еще раз выполнив оптимизацию, прежде чем продолжить любые другие ожидающие операции / транзакции.
