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

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

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

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

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

использованная литература

  1. ^ Ганс Райзер. «Примечания к выпуску Reiser4 - Танцующее дерево». Archive.org, поскольку Namesys.com больше не доступен. Архивировано из оригинал на 2007-10-24. Получено 2009-07-22.

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