Дансинг стабло
У информатици, дансинг стабло (енгл. Dancing tree) је тип стабла сличан Б+ стаблима. Изумео га је Ханс Реисер и Reiser4 фајл систем користи ову технологију. За разлику од cамобалансирајућих бинарних стабала претраге која покушавају да задрже своје чворове избалансиране стално, дансинг стабла само балансирају своје чворове приликом писања података на диск (било због ограничења меморије, или зато што је трансакција завршена).[1]
Основна идеја је да се убрзају фајл системске операције одлагањем оптимизације стабла и писање на диск се врши само када је то неопходно ,јер је писање на диск хиљадама пута спорије од писања у меморију. Осим тога, пошто се оптимизација врши ређе него у другим стаблима, добитак може бити још већи.
У неком смислу, ово се може сматрати cамобалансирајућим бинарним стаблом претраге које је оптимизовано за складиштење на спором медијуму , тако ће стабло са подацима увек бити уравнотежено али се писање неће вршити средином трансакције ; чинећи то, олакшавају се потешкоће са додавањем и уклањањем чворова и уместо тога обављају се ове (споре) ребалансирајуће операције истовремено као и (много спорије) писање на медијум за складиштење.
Међутим ,(негативни) споредни ефекат овог понашања се појављује у случају неочекиваног искључивања система , непотпуног уписивања података , и друге појаве које могу да ометају завршетак трансакције. У принципу, повратак података из непотпуних трансакција је доста тежи у случају дансинг стабла у односу на нормална стабла, мада овај проблем може да се реши додавањем додатних дневника трансакција или развити алгоритам за проналажење претходно постојећих података на диску ,a затим се иде кроз оптимизацију још једном пре него што се настави са било којим другим незавршиним операцијама/трансакцијама.
Референце
[уреди | уреди извор]- ^ Hans Reiser. „Reiser4 release notes - Dancing Tree”. Archive.org, as Namesys.com is no longer accessible. Архивирано из оригинала 24. 10. 2007. г. Приступљено 22. 7. 2009.