Танцующее дерево

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

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

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

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

Внешние ссылки

• Принципы проектирования Reiser4 на основе программной инженерии
• Описание внутреннего дерева Reiser4