شجرة R+

شجرة R+ هي طريقة للبحث عن البيانات باستخدام موقع، غالبًا إحداثيات (س، ص) ، وغالبًا ما تكون لمواقع على سطح الأرض . البحث باستخدام رقم واحد يُعدّ مشكلة محلولة؛ أما البحث باستخدام رقمين أو أكثر، وطلب مواقع متقاربة في اتجاهي س و ص، فيتطلب خوارزميات أكثر تعقيدًا.

بشكل أساسي، شجرة R+ هي بنية بيانات شجرية ، وهي نوع من شجرة R ، وتستخدم لفهرسة المعلومات المكانية .

تُعدّ أشجار R+ حلاً وسطاً بين أشجار R وأشجار kd ، إذ تتجنب تداخل العقد الداخلية عن طريق إدراج عنصر في عدة أوراق عند الضرورة. التغطية هي المساحة الكاملة التي تغطي جميع المستطيلات ذات الصلة. التداخل هو المساحة الكاملة التي تقع ضمن عقدتين أو أكثر. ^{[ 1 ]} تقلل التغطية الدنيا من مساحة "المساحة الميتة" (المساحة الفارغة) التي تغطيها عقد شجرة R. كما يقلل التداخل الأدنى من مجموعة مسارات البحث إلى الأوراق (وهو أمر بالغ الأهمية لوقت الوصول أكثر من التغطية الدنيا). يتطلب البحث الفعال تغطية وتداخلاً أدنى.

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

نظرًا لعدم تداخل العقد، تتحسن كفاءة استعلامات النقاط حيث لا تغطي أكثر من عقدة واحدة جميع المناطق المكانية. ويتم اتباع مسار واحد، وبالتالي يتم زيارة عدد أقل من العقد مقارنةً بشجرة R.

بما أن المستطيلات تُكرر، فقد تكون شجرة R+ أكبر من شجرة R مبنية على نفس مجموعة البيانات. يُعد بناء وصيانة أشجار R+ أكثر تعقيدًا من بناء وصيانة أشجار R وغيرها من أنواع أشجار R.

• تي. سيليس، إن. روسوبولوس، وسي. فالوتسوس . شجرة R+: فهرس ديناميكي للكائنات متعددة الأبعاد . في VLDB، 1987.