شجرة UB

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
الموسوعة الحرة

شجرة UB ، المعروفة أيضًا باسم شجرة B العالمية ، [ 1 ] التي اقترحها رودولف باير وفولكر ماركل، هي شجرة متوازنة لتخزين واسترجاع البيانات متعددة الأبعاد بكفاءة . وكما هو الحال في شجرة B+ ، تُخزَّن المعلومات في الأوراق فقط. تُخزَّن السجلات وفقًا لترتيب Z ، المعروف أيضًا بترتيب مورتون. يُحسب ترتيب Z عن طريق التداخل الثنائي للمفاتيح.

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

كانت الخوارزمية الأصلية لحل هذه المشكلة الرئيسية تعتمد على دالة أسية مع الأبعاد، وبالتالي لم تكن قابلة للتطبيق [ 2 ] ("الحصول على عنوان Z التالي"). وقد تم وصف حل لهذا "الجزء الحاسم من استعلام نطاق شجرة UB" لاحقًا [ 3 ] . وقد سبق وصف هذه الطريقة في ورقة بحثية سابقة [ 4 ] حيث تم اقتراح استخدام ترتيب Z مع أشجار البحث لأول مرة.

مراجع

  1. ↑ باير، رودولف (سبتمبر 1996). شجرة B العالمية للفهرسة متعددة الأبعاد .
  2. ↑ ماركل، ف. (1999). "ميسترال: معالجة الاستعلامات العلائقية باستخدام تقنية الوصول متعدد الأبعاد". CiteSeerX 10.1.1.32.6487 . 
  3. ↑ رامساك، فرانك؛ ماركل، فولكر؛ فينك، روبرت؛ زيركل، مارتن؛ إلهاردت، كلاوس؛ باير، رودولف (10-14 سبتمبر 2000). دمج شجرة UB في نواة نظام قاعدة البيانات (ملف PDF) . المؤتمر الدولي السادس والعشرون لقواعد البيانات الضخمة جدًا . الصفحات 263-272 . 
  4. ↑ تروبف، هـ.؛ هيرتسوغ، هـ. "البحث عن النطاق متعدد الأبعاد في الأشجار المتوازنة ديناميكيًا" (ملف PDF) . Angewandte Informatik (المعلوماتية التطبيقية) (2/1981): 71– 77. ISSN 0013-5704 .