الشجرة الراقصة

في علم الحاسوب ، تُعدّ الشجرة الراقصة بنية بيانات شجرية تُشبه أشجار B+ . وقد ابتكرها هانز رايزر لاستخدامها في نظام ملفات رايزر 4. وعلى عكس أشجار البحث الثنائية ذاتية التوازن التي تسعى للحفاظ على توازن عُقدها باستمرار، فإن الأشجار الراقصة لا تُوازن عُقدها إلا عند كتابة البيانات إلى القرص (إما بسبب قيود الذاكرة أو عند اكتمال عملية ما). ^{[ 1 ]}

تكمن الفكرة وراء ذلك في تسريع عمليات نظام الملفات عن طريق تأخير تحسين بنية البيانات الشجرية، والكتابة إلى القرص فقط عند الضرورة، لأن الكتابة إلى القرص أبطأ بآلاف المرات من الكتابة إلى الذاكرة. كما أن هذا التحسين، نظرًا لأنه يُجرى بوتيرة أقل مقارنةً ببنى البيانات الشجرية الأخرى، يمكن أن يكون أكثر شمولًا.

يمكن اعتبار هذا، من بعض النواحي، شجرة بحث ثنائية متوازنة ذاتيًا مُحسَّنة للتخزين على وسائط تخزين بطيئة، حيث يكون شكلها على القرص متوازنًا دائمًا، لكنها لا تخضع للكتابة أثناء العملية؛ مما يُسهِّل إضافة العقد وإزالتها خلال العملية. وبدلًا من ذلك، تُنفَّذ عمليات إعادة التوازن البطيئة هذه بالتزامن مع عملية الكتابة الأبطأ بكثير إلى وسيط التخزين.

مع ذلك، يظهر أثر جانبي سلبي لهذا السلوك في حالات الإغلاق غير المتوقع، وكتابة البيانات غير المكتملة، وغيرها من الأحداث التي قد تمنع إتمام المعاملة المتوازنة النهائية. وبشكل عام، تُشكل الأشجار الراقصة صعوبة أكبر من الأشجار التقليدية في استعادة البيانات من المعاملات غير المكتملة، على الرغم من إمكانية معالجة ذلك من خلال حساب البيانات المُعاملة بدقة أكبر.

• مبادئ تصميم Reiser4 القائمة على هندسة البرمجيات
• وصف الشجرة الداخلية لـ Reiser4