شجرة B x

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

في علوم الحاسوب ، شجرة B x هي استعلام يستخدم لتحديث هياكل الفهرسة الفعالة القائمة على شجرة B+ لنقل الكائنات.

بنية الفهرس

تعتمد بنية شجرة Bx الأساسية على شجرة B+، حيث تعمل العقد الداخلية كدليل، ويحتوي كل منها على مؤشر إلى العقدة الشقيقة اليمنى. في الإصدار السابق من شجرة Bx ، [ 1 ] احتوت العقد الطرفية على مواقع الكائنات المتحركة التي يتم فهرستها ووقت الفهرسة المقابل. أما في الإصدار المُحسَّن، [ 2 ] فيحتوي كل مدخل في العقدة الطرفية على معرّف الكائن وسرعته وقيمة التعيين أحادي البعد ووقت آخر تحديث له. وقد تم زيادة عدد الفروع عن طريق عدم تخزين مواقع الكائنات المتحركة، إذ يمكن استنتاجها من قيم التعيين .

استخدام شجرة B+ لتحريك الكائنات

مثال على شجرة B x حيث عدد أقسام الفهرس يساوي 2 ضمن فترة تحديث قصوى واحدة tmu. في هذا المثال، يوجد ثلاثة أقسام كحد أقصى في الوقت نفسه. بعد عملية التخطيط الخطي، تُفهرس مواقع الكائنات المُدرجة عند الزمن 0 في القسم 0 مع الطابع الزمني 0.5 tmu، وتُفهرس مواقع الكائنات المُحدثة خلال الفترة من 0 إلى 0.5 tmu في القسم 1 مع الطابع الزمني tmu، وهكذا (كما هو موضح بالأسهم). مع مرور الوقت، تنتهي صلاحية النطاق الأول (المنطقة المظللة) بشكل متكرر، ويُضاف نطاق جديد (الخط المتقطع).

كما هو الحال مع العديد من مؤشرات الأجسام المتحركة الأخرى، يُنمذج الجسم المتحرك ثنائي الأبعاد كدالة خطية على النحو التالي: O = ((x, y), (vx, vy), t)، حيث يمثل (x, y) و(vx, vy) موقع وسرعة الجسم عند لحظة زمنية معينة t ، أي وقت آخر تحديث. شجرة B+ هي بنية لفهرسة البيانات أحادية البعد. ولاعتماد شجرة B+ كمؤشر للأجسام المتحركة، تستخدم شجرة Bx تقنية التخطيط الخطي التي تساعد على دمج موقع الأجسام عند الزمن t في قيمة أحادية البعد. تحديدًا، تُقسّم الأجسام أولًا وفقًا لوقت تحديثها. بالنسبة للأجسام داخل نفس القسم، تخزن شجرة Bx مواقعها عند وقت معين، والتي تُقدّر بواسطة الاستيفاء الخطي . وبذلك، تحافظ شجرة Bx على رؤية متسقة لجميع الأجسام داخل نفس القسم دون تخزين وقت تحديث كل جسم.

ثانيًا، يتم تقسيم المساحة بواسطة شبكة ويتم تحديد موقع الكائن بشكل خطي داخل الأقسام وفقًا لمنحنى ملء الفراغ، على سبيل المثال، منحنيات بيانو أو هيلبرت .

وأخيرًا، من خلال الجمع بين رقم القسم (معلومات الوقت) والترتيب الخطي (معلومات الموقع)، يتم فهرسة الكائن في شجرة B x باستخدام مفتاح فهرس أحادي البعد B x value:

بx قيمة(يا،ت)=[قسم الفهرس]2+[xrep]2{\displaystyle B^{x}{\text{ value}}\left(O,t\right)=\left[{\text{index partition}}\right]_{2}+\left[{\text{xrep}}\right]_{2}}

هنا، يمثل index-partition تقسيم الفهرس المحدد بواسطة وقت التحديث، وxrep هي قيمة منحنى ملء الفراغ لموضع الكائن في الوقت المفهرس.[X]2{\displaystyle \left[X\right]_{2}}يشير إلى القيمة الثنائية لـ x، و"+" تعني الربط.

بالنظر إلى كائن O ((7, 2), (-0.1,0.05), 10), tmu = 120، يمكن حساب قيمة B x لـ O على النحو التالي:

  1. تم فهرسة O في القسم 0 كما ذكرنا. لذلك، فإن فهرسة القسم = (00) 2 .
  2. موقع O عند الطابع الزمني للعلامة للقسم 0 هو (1,5).
  3. باستخدام منحنى Z مع الرتبة = 3، فإن قيمة Z لـ O، أي xrep هي (010011) 2 .
  4. بدمج indexpartition و xrep، B x value (00010011) 2 =19.
  5. مثال: O ((0,6), (0.2, -0.3),10) و tmu=120، إذن موضع O عند الطابع الزمني للعلامة للقسم:  ???

الإضافة والتحديث والحذف

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

استفسارات

استعلام النطاق

يسترجع استعلام النطاق جميع الكائنات التي يقع موقعها ضمن النطاق المستطيلq=([qx1،qy1]؛[qx2؛qy2]){\displaystyle q=\left(\left[qx1,qy1\right];\left[qx2;qy2\right]\right)}في ذلك الوقتتq{\displaystyle tq}ليس قبل الوقت الحالي.

تستخدم شجرة Bx تقنية توسيع نافذة الاستعلام للإجابة على الاستعلامات. ولأن شجرة Bx تخزن موقع الكائن بعد وقت تحديثه، فإن التوسيع يشمل حالتين: إما إعادة الموقع إلى وقت سابق أو تقديمه إلى وقت لاحق. الفكرة الأساسية هي توسيع نافذة الاستعلام بحيث تشمل جميع الكائنات التي لا تقع مواقعها ضمن نافذة الاستعلام عند طابعها الزمني، ولكنها ستدخل نافذة الاستعلام عند طابع الاستعلام الزمني.

بعد التوسيع، يجب اجتياز أقسام شجرة B x للعثور على العناصر الواقعة ضمن نافذة الاستعلام الموسعة. في كل قسم، يعني استخدام منحنى ملء الفراغ أن استعلام النطاق في الفضاء الأصلي ثنائي الأبعاد يتحول إلى مجموعة من استعلامات النطاق في الفضاء المحول أحادي البعد. [ 1 ]

لتجنب منطقة استعلام كبيرة بشكل مفرط بعد التوسع في مجموعات البيانات المنحرفة، يوجد تحسين لخوارزمية الاستعلام، [ 3 ] مما يحسن كفاءة الاستعلام عن طريق تجنب التوسع غير الضروري للاستعلام.

استعلام عن أقرب جار K

يتم حساب استعلام أقرب K جار من خلال إجراء استعلامات نطاقية متكررة مع توسيع منطقة البحث تدريجيًا حتى يتم الحصول على k إجابة. وثمة إمكانية أخرى تتمثل في استخدام أفكار استعلام مماثلة في تقنية iDistance .

استفسارات أخرى

يمكن بسهولة توسيع خوارزميات استعلام النطاق واستعلام أقرب جار K لدعم استعلامات الفترات والاستعلامات المستمرة وما إلى ذلك. [ 2 ]

تكييف محركات قواعد البيانات العلائقية لاستيعاب الكائنات المتحركة

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

SpADE [ 4 ] هو نظام لإدارة الكائنات المتحركة مبني على نظام قاعدة البيانات العلائقية الشهير MySQL ، والذي يستخدم شجرة Bx لفهرسة الكائنات. في التطبيق، تُحوّل بيانات الكائنات المتحركة وتُخزّن مباشرةً في MySQL، وتُحوّل الاستعلامات إلى عبارات SQL قياسية تُعالج بكفاءة في محرك قاعدة البيانات العلائقية. والأهم من ذلك، أن كل هذا يتم بسلاسة واستقلالية تامة دون التأثير على جوهر MySQL.

تحسين الأداء

مشكلة محتملة تتعلق بانحراف البيانات

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

ضبط المؤشر

تُقدّم شجرة ST 2 B [ 5 ] إطار عمل ذاتي الضبط لتحسين أداء شجرة B x عند التعامل مع انحراف البيانات المكاني وتغيرها مع الزمن. ولمعالجة انحراف البيانات المكاني، تقسم شجرة ST 2 B الفضاء بأكمله إلى مناطق ذات كثافة كائنات مختلفة باستخدام مجموعة من النقاط المرجعية. وتستخدم كل منطقة شبكة مستقلة، ويُحدد حجم خلاياها بناءً على كثافة الكائنات داخلها.

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

انظر أيضاً

مراجع

  1. 1 2 كريستيان إس. جنسن، دان لين، وبينغ تشين أوي. فهرسة الكائنات المتحركة بكفاءة باستخدام شجرة B+ للاستعلام والتحديث . في وقائع المؤتمر الدولي الثلاثين لقواعد البيانات الضخمة جدًا (VLDB)، الصفحات 768-779، 2004.
  2. 1 2 دان لين. فهرسة واستعلام قواعد بيانات الكائنات المتحركة ، أطروحة دكتوراه، الجامعة الوطنية في سنغافورة، 2006.
  3. ↑ Jensen, CS, D. Tiesyte, N. Tradisauskas, Robust B+-Tree-Based Indexing of Moving Objects, in Proceedings of the Seventh International Conference on Mobile Data Management , Nara, Japan, 9 pages, May 9–12, 2006.
  4. ↑ SpADE مؤرشف في 2009-01-02 في Wayback Machine : محرك قاعدة بيانات مكاني-زماني ذاتي للخدمات التي تراعي الموقع.
  5. ↑ سو تشين، بينغ تشين أوي، كان-لي تان، وماريو أ. ناسيمينتو، ST2B-tree: شجرة B+ مكانية-زمانية ذاتية الضبط للأجسام المتحركة. مؤرشفة بتاريخ 11 يونيو 2011 في Wayback Machine . في وقائع مؤتمر ACM SIGMOD الدولي لإدارة البيانات (SIGMOD)، الصفحات 29-42، 2008.