R+ tree
R + درخت ایک مقام کا استعمال کرتے ہوئے ڈیٹا تلاش کرنے کا ایک طریقہ ہے، اکثر (x، y) نقاط، اور اکثر زمین کی سطح پر مقامات کے لیے۔ ایک نمبر پر تلاش کرنا ایک حل شدہ مسئلہ ہے۔ دو یا دو سے زیادہ پر تلاش کرنا، اور x اور y دونوں سمتوں میں قریبی مقامات کے لیے پوچھنا، کرافٹ الگورتھم کی ضرورت ہے۔ بنیادی طور پر، آر + ٹری ایک ٹری ڈیٹا ڈھانچہ ہے، جو آر ٹری کی ایک قسم ہے، جو مقامی معلومات کو ترتیب دینے کے لیے استعمال ہوتا ہے۔ آر + درختوں اور آر + درختوں کے درمیان فرق آر-درختوں اور کے ڈی-درختوں کے درمیان ایک سمجھوتہ ہے: اگر ضروری ہو تو وہ کسی شے کو متعدد پتوں میں ڈال کر اندرونی نوڈس کے اوور لیپنگ سے بچتے ہیں۔ کوریج تمام متعلقہ مستطیلوں کا احاطہ کرنے کے لیے پورا علاقہ ہے۔ اوور لیپ وہ پورا علاقہ ہے جو دو یا زیادہ نوڈس میں موجود ہوتا ہے۔ کم سے کم کوریج "ڈیڈ اسپیس" (خالی جگہ) کی مقدار کو کم کرتی ہے جو R-درخت کے نوڈس سے ڈھکی ہوتی ہے۔ کم سے کم اوورلیپ پتوں تک تلاش کے راستوں کے سیٹ کو کم کر دیتا ہے (رسائی کے وقت کے لیے کم سے کم کوریج سے بھی زیادہ اہم)۔ موثر تلاش کے لیے کم سے کم کوریج اور اوورلیپ کی ضرورت ہوتی ہے۔ R + درخت اس میں R درختوں سے مختلف ہیں: نوڈس کو کم از کم نصف بھرا ہوا ہونے کی ضمانت نہیں ہے، کسی بھی اندرونی نوڈ کی اندراجات اوورلیپ نہیں ہوتی ہیں، اور ایک آبجیکٹ ID کو ایک سے زیادہ لیف نوڈ میں محفوظ کیا جا سکتا ہے۔ فوائد کیونکہ نوڈس ایک دوسرے کے ساتھ اوورلیپ نہیں ہوتے ہیں، نقطہ استفسار کی کارکردگی کے فوائد کیونکہ تمام مقامی علاقے زیادہ سے زیادہ ایک نوڈ سے ڈھکے ہوتے ہیں۔ ایک واحد راستے کی پیروی کی جاتی ہے اور آر-ٹری کے مقابلے میں کم نوڈس کا دورہ کیا جاتا ہے۔ نقصانات چونکہ مستطیل ڈپلیکیٹ ہوتے ہیں، اس لیے ایک R + ٹری اسی ڈیٹا سیٹ پر بنائے گئے R ٹری سے بڑا ہو سکتا ہے۔ آر + درختوں کی تعمیر اور دیکھ بھال آر درختوں اور آر درخت کی دیگر اقسام کی تعمیر اور دیکھ بھال سے زیادہ پیچیدہ ہے۔ حوالہ جات ٹی۔ سیلیس، این۔ روسیپولوس، اور سی۔ فلوٹس۔ R +-درخت: کثیر جہتی اشیاء کے لیے ایک متحرک اشاریہ۔ وی ایل ڈی بی میں، 1987۔ آر-ٹری ڈیٹا بیس انڈیکس تکنیک ڈی: آر-بوم