Dancing tree (original) (raw)
Le terme anglais Dancing Tree (que l'on peut traduire par arbre dansant) est le nom d'une technologie utilisée par le système de fichiers Reiser4 et qui rend obsolète[Quand ?] l'ancienne technologie appelée B-trees (ou arbres B en français). Cette technologie permet de gérer des fichiers de taille importante.
| Property | Value |
|---|---|
| dbo:abstract | 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. (en) Le terme anglais Dancing Tree (que l'on peut traduire par arbre dansant) est le nom d'une technologie utilisée par le système de fichiers Reiser4 et qui rend obsolète[Quand ?] l'ancienne technologie appelée B-trees (ou arbres B en français). Cette technologie permet de gérer des fichiers de taille importante. (fr) В информатике танцующее дерево (англ. Dancing tree) — древовидная структура хранения данных, которая похожа на B+trees. Она придумана Хансом Рейзером для использования в файловой системе Reiser4. По сравнению со сбалансированными бинарными деревьями, которые пытаются сохранить свои узлы сбалансированными постоянно, танцующие деревья сохраняют баланс между узлами только при записи данных на диск: либо из-за ограничений памяти, или потому, что транзакция завершена. Идея заключается в том, чтобы ускорить операции с файловой системой, отказавшись от оптимизации дерева, а писать на диск только когда это необходимо, так как запись на диск в тысячи раз медленнее, чем запись в память. Кроме того, поскольку такая оптимизация проводится реже, чем у других древовидных структур данных, выигрыш может быть ещё больше. Тем не менее, побочный эффект такого поведения появляется в случае неожиданной остановки системы, записи неполных данных и других явлений, которые могут помешать завершению окончательной (сбалансированной) транзакции. В целом танцующие деревья создают бо́льшие трудности для восстановления данных из незавершённых операций, чем нормальные деревья, хотя эту проблему можно решить путём добавления дополнительных журналов транзакций или разработки алгоритма для поиска ранее не существовавших данных на диске с последующим выполнением оптимизаций и возобновлением операций. (ru) |
| dbo:wikiPageExternalLink | http://nikitadanilov.blogspot.com/2006/03/reiser4-1-internal-tree.html http://www.namesys.com/v4/v4.html%23dancing_tree |
| dbo:wikiPageID | 1605712 (xsd:integer) |
| dbo:wikiPageLength | 2302 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1086538563 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Reiser4 dbc:Computer_file_systems dbr:Tree_data_structure dbr:Computer_science dbr:B+_tree dbc:B-tree dbr:Hans_Reiser dbr:Self-balancing_binary_search_tree |
| dbp:wikiPageUsesTemplate | dbt:Compu-storage-stub dbt:CS-Trees dbt:One_source |
| dct:subject | dbc:Computer_file_systems dbc:B-tree |
| gold:hypernym | dbr:Structure |
| rdf:type | yago:WikicatComputerFileSystems yago:Abstraction100002137 yago:Arrangement105726596 yago:ClassificationSystem105727220 yago:Cognition100023271 yago:FileSystem105732614 yago:PsychologicalFeature100023100 dbo:Building yago:Structure105726345 |
| rdfs:comment | Le terme anglais Dancing Tree (que l'on peut traduire par arbre dansant) est le nom d'une technologie utilisée par le système de fichiers Reiser4 et qui rend obsolète[Quand ?] l'ancienne technologie appelée B-trees (ou arbres B en français). Cette technologie permet de gérer des fichiers de taille importante. (fr) 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). (en) В информатике танцующее дерево (англ. Dancing tree) — древовидная структура хранения данных, которая похожа на B+trees. Она придумана Хансом Рейзером для использования в файловой системе Reiser4. По сравнению со сбалансированными бинарными деревьями, которые пытаются сохранить свои узлы сбалансированными постоянно, танцующие деревья сохраняют баланс между узлами только при записи данных на диск: либо из-за ограничений памяти, или потому, что транзакция завершена. (ru) |
| rdfs:label | Dancing tree (en) Dancing tree (fr) Танцующее дерево (ru) |
| owl:sameAs | freebase:Dancing tree yago-res:Dancing tree wikidata:Dancing tree dbpedia-fr:Dancing tree http://lt.dbpedia.org/resource/Šokantis_medis dbpedia-ru:Dancing tree dbpedia-sr:Dancing tree https://global.dbpedia.org/id/ykQZ |
| prov:wasDerivedFrom | wikipedia-en:Dancing_tree?oldid=1086538563&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Dancing_tree |
| is dbo:wikiPageRedirects of | dbr:Dancing_trees dbr:Ddancing_trees |
| is dbo:wikiPageWikiLink of | dbr:List_of_data_structures dbr:Reiser4 dbr:T-tree dbr:Tree_structure dbr:Dancing_trees dbr:Ddancing_trees |
| is dbp:directoryStruct of | dbr:Reiser4 |
| is foaf:primaryTopic of | wikipedia-en:Dancing_tree |