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