Танцующие деревья: структура данных для файловой системы Reiser4
Dancing tree
Танцующее дерево (dancing tree) – структура данных, как B+ дерево, разработанная для Reiser4. Отличается отложеной балансировкой при записи на диск для повышения скорости файловой системы.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В информатике, танцующее дерево — это структура данных дерева, аналогичная B+ деревьям. Оно было изобретено Хансом Райзером для использования в файловой системе Reiser4. В отличие от самобалансирующихся двоичных деревьев поиска, которые стремятся поддерживать баланс своих узлов постоянно, танцующие деревья балансируют свои узлы только при сбросе данных на диск (либо из-за ограничений памяти, либо после завершения транзакции). Эта идея направлена на ускорение операций файловой системы за счет отсрочки оптимизации дерева и записи на диск только при необходимости, поскольку запись на диск в тысячи раз медленнее, чем запись в память. Кроме того, поскольку эта оптимизация выполняется реже, чем в других структурах данных дерева, она может быть более масштабной. В определенном смысле, это можно рассматривать как самобалансирующееся двоичное дерево поиска, оптимизированное для хранения на медленной среде, в том смысле, что его форма на диске всегда будет сбалансированной, но не будет получать промежуточные записи транзакций; это упрощает задачу добавления и удаления узлов во время транзакции. Вместо этого эти медленные операции перебалансировки выполняются одновременно с гораздо более медленной записью на носитель. Однако, негативный побочный эффект этого поведения проявляется в случаях неожиданного отключения питания, неполных записей данных и других ситуациях, которые могут помешать завершению финальной сбалансированной транзакции. В целом, танцующие деревья представляют большую сложность, чем традиционные деревья, при восстановлении данных из незавершенных транзакций, хотя эту проблему можно решить путем более тщательного учета транзакционных данных.
In computer science, a dancing tree is a tree data structure similar to B+ trees. It was invented by Hans Reiser, for use by the Reiser4 file system. As opposed to self balancing binary search trees that attempt to keep their nodes balanced at all times, dancing trees only balance their nodes when flushing data to a disk (either because of memory constraints or because a transaction has completed). The idea behind this is to speed up file system operations by delaying optimization of the tree and only writing to disk when necessary, as writing to disk is thousands of times slower than writing to memory. Also, because this optimization is done less often than with other tree data structures, the optimization can be more extensive. In some sense, this can be considered to be a self balancing binary search tree that is optimized for storage on a slow medium, in that the on disc form will always be balanced but will get no mid transaction writes; doing so eases the difficulty of adding and removing nodes during a transaction. Instead, these slow rebalancing operations are performed at the same time as the much slower write to the storage medium. However, a negative side effect of this behavior manifests in cases of unexpected shutdown, incomplete data writes, and other occurrences that may prevent the final balanced transaction from completing. In general, dancing trees pose greater difficulty than conventional trees for data recovery from incomplete transactions, though this can be addressed by more thoroughly accounting for transacted data.