Дерек құрылымдары: «Билейтін ағаш» – Reiser4 жүйесі үшін жасалған, жадтан дискіге жазғанда ғана тепе-теңдікке келтіретін B+ ағаштарына ұқсас технология. Жылдамдық пен тиімділік!
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы 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.