Inom datavetenskap är ett dansande träd en trädliknande datalagringsstruktur som liknar B+träd . Den designades av Hans Reiser för användning i Reiser4 -filsystemet . Jämfört med balanserade binära träd, som försöker hålla sina noder balanserade hela tiden, håller dansande träd bara balans mellan noder när data skrivs till disk, antingen på grund av minnesbegränsningar eller för att en transaktion har slutförts. [ett]
Tanken är att påskynda filsystemets operationer genom att inte optimera trädet, och bara skriva till disk när det behövs, eftersom skrivning till disk är tusentals gånger långsammare än att skriva till minne. Dessutom, eftersom denna optimering är mindre frekvent än med andra träddatastrukturer, kan vinsterna bli ännu större.
Men bieffekten av detta beteende uppträder i händelse av en oväntad systemavstängning, ofullständig dataskrivning och andra fenomen som kan förhindra slutförandet av den slutliga (balanserade) transaktionen. I allmänhet gör dansträd det svårare att återställa data från väntande operationer än vanliga träd, även om detta problem kan lösas genom att lägga till ytterligare transaktionsloggar eller utveckla en algoritm för att hitta tidigare obefintlig data på disken, sedan utföra optimeringar och återuppta operationer .
| Träd (datastruktur) | |
|---|---|
| Binära träd | |
| Självbalanserande binära träd |
|
| B-träd | |
| prefix träd |
|
| Binär uppdelning av utrymme | |
| Icke-binära träd |
|
| Bryter upp utrymmet |
|
| Andra träd |
|
| Algoritmer | |