739:
22:
151:
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
147:
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.
143:
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,
139:
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).
780:
32:
479:
686:
230:
136:
773:
346:
799:
804:
47:
169:
90:
148:
Instead, these slow rebalancing operations are performed at the same time as the much slower write to the storage medium.
62:
766:
69:
311:
696:
252:
76:
223:
203:
152:
incomplete transactions, though this can be addressed by more thoroughly accounting for transacted data.
58:
390:
239:
380:
335:
494:
270:
120:
350:
661:
620:
446:
436:
315:
555:
256:
216:
750:
746:
646:
112:
809:
590:
340:
83:
543:
538:
421:
355:
793:
691:
671:
514:
403:
330:
265:
651:
615:
431:
426:
408:
196:
173:
701:
666:
656:
570:
504:
499:
489:
398:
247:
128:
21:
711:
681:
641:
484:
413:
360:
280:
716:
676:
523:
451:
441:
738:
605:
295:
124:
721:
595:
575:
548:
533:
285:
706:
610:
585:
528:
375:
305:
300:
275:
208:
132:
625:
600:
580:
565:
474:
365:
290:
469:
370:
325:
39:
461:
212:
15:
754:
43:
198:
634:
513:
460:
389:
246:
774:
224:
8:
48:introducing citations to additional sources
781:
767:
231:
217:
209:
204:Description of the Reiser4 internal tree
144:the optimization can be more extensive.
38:Relevant discussion may be found on the
160:
170:"Reiser4 release notes - Dancing Tree"
7:
735:
733:
753:. You can help Knowledge (XXG) by
137:self-balancing binary search trees
14:
737:
31:relies largely or entirely on a
20:
1:
135:file system. As opposed to
826:
732:
687:Left-child right-sibling
517:data partitioning trees
475:C-trie (compressed ADT)
800:Computer storage stubs
749:-related article is a
805:Computer file systems
127:. It was invented by
697:Log-structured merge
240:Tree data structures
44:improve this article
121:tree data structure
662:Fractal tree index
257:associative arrays
762:
761:
730:
729:
131:, for use by the
109:
108:
94:
817:
783:
776:
769:
747:computer-storage
741:
734:
233:
226:
219:
210:
185:
184:
182:
181:
172:. Archived from
165:
113:computer science
104:
101:
95:
93:
52:
24:
16:
825:
824:
820:
819:
818:
816:
815:
814:
790:
789:
788:
787:
731:
726:
630:
509:
456:
385:
381:Weight-balanced
336:Order statistic
250:
242:
237:
193:
188:
179:
177:
167:
166:
162:
158:
105:
99:
96:
53:
51:
37:
25:
12:
11:
5:
823:
821:
813:
812:
807:
802:
792:
791:
786:
785:
778:
771:
763:
760:
759:
742:
728:
727:
725:
724:
719:
714:
709:
704:
699:
694:
689:
684:
679:
674:
669:
664:
659:
654:
649:
644:
638:
636:
632:
631:
629:
628:
623:
618:
613:
608:
603:
598:
593:
588:
583:
578:
573:
568:
563:
546:
541:
536:
531:
526:
520:
518:
511:
510:
508:
507:
502:
497:
495:Ternary search
492:
487:
482:
477:
472:
466:
464:
458:
457:
455:
454:
449:
444:
439:
434:
429:
424:
419:
411:
406:
401:
395:
393:
387:
386:
384:
383:
378:
373:
368:
363:
358:
353:
343:
338:
333:
328:
323:
318:
308:
303:
298:
293:
288:
283:
278:
273:
268:
262:
260:
244:
243:
238:
236:
235:
228:
221:
213:
207:
206:
201:
192:
191:External links
189:
187:
186:
159:
157:
154:
107:
106:
59:"Dancing tree"
42:. Please help
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
822:
811:
808:
806:
803:
801:
798:
797:
795:
784:
779:
777:
772:
770:
765:
764:
758:
756:
752:
748:
743:
740:
736:
723:
720:
718:
715:
713:
710:
708:
705:
703:
700:
698:
695:
693:
690:
688:
685:
683:
680:
678:
675:
673:
672:Hash calendar
670:
668:
665:
663:
660:
658:
655:
653:
650:
648:
645:
643:
640:
639:
637:
633:
627:
624:
622:
619:
617:
614:
612:
609:
607:
604:
602:
599:
597:
594:
592:
589:
587:
584:
582:
579:
577:
574:
572:
569:
567:
564:
561:
559:
553:
551:
547:
545:
542:
540:
537:
535:
532:
530:
527:
525:
522:
521:
519:
516:
512:
506:
503:
501:
498:
496:
493:
491:
488:
486:
483:
481:
478:
476:
473:
471:
468:
467:
465:
463:
459:
453:
450:
448:
447:van Emde Boas
445:
443:
440:
438:
437:Skew binomial
435:
433:
430:
428:
425:
423:
420:
418:
416:
412:
410:
407:
405:
402:
400:
397:
396:
394:
392:
388:
382:
379:
377:
374:
372:
369:
367:
364:
362:
359:
357:
354:
352:
348:
344:
342:
339:
337:
334:
332:
329:
327:
324:
322:
319:
317:
316:Binary search
313:
309:
307:
304:
302:
299:
297:
294:
292:
289:
287:
284:
282:
279:
277:
274:
272:
269:
267:
264:
263:
261:
258:
254:
249:
245:
241:
234:
229:
227:
222:
220:
215:
214:
211:
205:
202:
200:
199:
195:
194:
190:
176:on 2007-10-24
175:
171:
168:Hans Reiser.
164:
161:
155:
153:
149:
145:
141:
138:
134:
130:
126:
122:
118:
114:
103:
92:
89:
85:
82:
78:
75:
71:
68:
64:
61: –
60:
56:
55:Find sources:
49:
45:
41:
35:
34:
33:single source
29:This article
27:
23:
18:
17:
755:expanding it
744:
557:
549:
414:
347:Left-leaning
320:
253:dynamic sets
248:Search trees
197:
178:. Retrieved
174:the original
163:
150:
146:
142:
117:dancing tree
116:
110:
97:
87:
80:
73:
66:
54:
30:
647:Exponential
635:Other trees
129:Hans Reiser
123:similar to
794:Categories
591:Priority R
341:Palindrome
180:2009-07-22
156:References
100:March 2021
70:newspapers
677:iDistance
556:implicit
544:Hilbert R
539:Cartesian
422:Fibonacci
356:Scapegoat
351:Red–black
40:talk page
692:Link/cut
404:Binomial
331:Interval
125:B+ trees
652:Fenwick
616:Segment
515:Spatial
432:Pairing
427:Leftist
349:)
321:Dancing
314:)
312:Optimal
133:Reiser4
84:scholar
810:B-tree
702:Merkle
667:Fusion
657:Finger
581:Octree
571:Metric
505:Y-fast
500:X-fast
490:Suffix
409:Brodal
399:Binary
86:
79:
72:
65:
57:
745:This
712:Range
682:K-ary
642:Cover
485:Radix
470:Ctrie
462:Tries
391:Heaps
371:Treap
361:Splay
326:HTree
281:(a,b)
271:2–3–4
119:is a
91:JSTOR
77:books
751:stub
717:SPQR
596:Quad
524:Ball
480:Hash
452:Weak
442:Skew
417:-ary
115:, a
63:news
722:Top
576:MVP
534:BSP
286:AVL
266:2–3
111:In
46:by
796::
707:PQ
621:VP
611:R*
606:R+
586:PH
560:-d
552:-d
529:BK
376:UB
301:B*
296:B+
276:AA
782:e
775:t
768:v
757:.
626:X
601:R
566:M
562:)
558:k
554:(
550:k
415:d
366:T
345:(
310:(
306:B
291:B
259:)
255:/
251:(
232:e
225:t
218:v
183:.
102:)
98:(
88:·
81:·
74:·
67:·
50:.
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
