Bx-tree
کمپیوٹر سائنس میں، بی ایکس ٹری ایک استفسار ہے جو حرکت پذیر اشیاء کے لیے موثر بی + ٹری پر مبنی انڈیکس ڈھانچے کو اپ ڈیٹ کرنے کے لیے استعمال ہوتا ہے۔ انڈیکس ڈھانچہ بی ایکس ٹری کا بنیادی ڈھانچہ ایک بی + ٹری ہے جس میں اندرونی نوڈس ایک ڈائرکٹری کے طور پر کام کرتے ہیں، ہر ایک میں اپنے دائیں بہن بھائی کے لیے ایک پوائنٹر ہوتا ہے۔ بی ایکس ٹری کے پہلے ورژن میں، لیف نوڈس میں حرکت پذیر آبجیکٹ کے مقامات کو انڈیکس کیا جا رہا تھا اور اسی انڈیکس کا وقت تھا۔ مرضی کے مطابق ورژن میں، ہر لیف نوڈ اندراج میں آئی ڈی، رفتار، واحد جہتی نقشہ سازی کی قیمت اور آبجیکٹ کا تازہ ترین اپ ڈیٹ ٹائم ہوتا ہے۔ حرکت پذیر اشیاء کے مقامات کو ذخیرہ نہ کرنے سے فین آؤٹ میں اضافہ ہوتا ہے، کیونکہ یہ نقشہ سازی کی اقدار سے حاصل کیے جا سکتے ہیں۔ حرکت پذیر اشیاء کے لیے B + درخت کا استعمال جیسا کہ بہت سی دوسری حرکت پذیر اشیاء کے اشاریہ جات کے لیے، ایک دو جہتی حرکت پذیر شے کو O = ((x, y)، (vx, vy)، t) کے طور پر لکیری فنکشن کے طور پر ماڈل کیا جاتا ہے، جہاں (x, y) اور (vx, vy) کسی دیئے گئے وقت کی مثال t، یعنی آخری اپ ڈیٹ کا وقت پر شے کا مقام اور رفتار ہیں۔ بی + ٹری ایک جہتی ڈیٹا کو انڈیکس کرنے کے لیے ایک ڈھانچہ ہے۔ B + درخت کو حرکت پذیر آبجیکٹ انڈیکس کے طور پر اپنانے کے لیے، Bx-درخت ایک لکیریائزیشن تکنیک کا استعمال کرتا ہے جو وقت t پر اشیاء کے مقام کو یک جہتی قدر میں ضم کرنے میں مدد کرتا ہے۔ خاص طور پر، اشیاء کو پہلے ان کے اپ ڈیٹ کے وقت کے مطابق تقسیم کیا جاتا ہے۔ ایک ہی پارٹیشن کے اندر موجود اشیاء کے لیے، بی ایکس ٹری ایک مقررہ وقت پر اپنے مقامات کو محفوظ کرتا ہے جس کا تخمینہ لکیری انٹرپولیشن کے ذریعے لگایا جاتا ہے۔ ایسا کرنے سے، بی ایکس ٹری ہر شے کے اپ ڈیٹ ٹائم کو محفوظ کیے بغیر ایک ہی پارٹیشن کے اندر تمام اشیاء کا مستقل نظارہ رکھتا ہے۔ دوم، جگہ کو گرڈ کے ذریعے تقسیم کیا جاتا ہے اور کسی شے کا مقام جگہ بھرنے والے منحنی خطوط کے مطابق تقسیم کے اندر لکیری شکل میں ہوتا ہے، مثال کے طور پر، پیانو یا ہلبرٹ منحنی خطوط۔ آخر میں، پارٹیشن نمبر (وقت کی معلومات) اور لکیری آرڈر (محل وقوع کی معلومات) کے امتزاج کے ساتھ، ایک شے کو ایک جہتی انڈیکس کلید بی ایکس ویلیو کے ساتھ بی ایکس ٹری میں انڈیکس کیا جاتا ہے: یہاں انڈیکس پارٹیشن ایک انڈیکس پارٹیشن ہے جس کا تعین اپ ڈیٹ کے وقت سے ہوتا ہے اور ایکس ریپ انڈیکس شدہ وقت پر آبجیکٹ پوزیشن کی اسپیس فلنگ وکر ویلیو ہے، جو ایکس کی بائنری ویلیو کو ظاہر کرتی ہے، اور "+" کا مطلب کنکیٹیشن ہے۔ کسی شے O ((7، 2)، (-0.1,0.05)، 10)، tmu = 120 کو دیکھتے ہوئے، O کے لیے Bx ویلیو کا حساب مندرجہ ذیل طریقے سے لگایا جا سکتا ہے۔ O کو تقسیم 0 میں انڈیکس کیا گیا ہے جیسا کہ ذکر کیا گیا ہے۔ لہذا، انڈیکس پارٹیشن = (00) 2۔ پارٹیشن 0 کے لیبل ٹائم اسٹیمپ پر O کی پوزیشن (1,5) ہے۔ آرڈر = 3 کے ساتھ Z-منحنی خطوط کا استعمال کرتے ہوئے، O کی Z-ویلیو، یعنی xrep (090011) 2 ہے۔ کنکیٹینٹنگ انڈیکس پارٹیشن اور ایکس آر ای پی، بی ایکس ویلیو (00010011) 2 = 19۔ مثال O ((0,6)، (0.2،-0.3)، 10) اور tmu = 120 پھر پارٹیشن کے لیبل ٹائم اسٹیمپ پر O کی پوزیشن:؟ ؟؟؟ اندراج، اپ ڈیٹ اور حذف کرنا ایک نئی شے کو دیکھتے ہوئے، اس کی انڈیکس کلید کا حساب لگایا جاتا ہے اور پھر شے کو Bx-درخت میں داخل کیا جاتا ہے جیسا کہ B + درخت میں ہوتا ہے۔ اپ ڈیٹ ایک حذف کرنے کے بعد داخل کرنے پر مشتمل ہوتا ہے۔ ہر انڈیکس کی تازہ ترین کلید کو رکھنے کے لیے ایک معاون ڈھانچہ استعمال کیا جاتا ہے تاکہ کلید کو تلاش کر کے کسی شے کو حذف کیا جا سکے۔ ٹری کو متاثر کرنے سے پہلے انڈیکسنگ کلید کا حساب لگایا جاتا ہے۔ اس طرح، بی ایکس ٹری براہ راست بی + ٹری کی اچھی خصوصیات کو وراثت میں حاصل کرتا ہے، اور موثر اپ ڈیٹ کارکردگی حاصل کرتا ہے۔ سوالات رینج استفسار ایک رینج استفسار ان تمام اشیاء کو بازیافت کرتا ہے جن کا مقام موجودہ وقت سے پہلے کے وقت آئتاکار رینج کے اندر آتا ہے۔ بی ایکس ٹری سوالات کے جوابات کے لیے استفسار ونڈو بڑھانے کی تکنیک کا استعمال کرتا ہے۔ چونکہ بی ایکس ٹری کسی شے کے مقام کو اس کے اپ ڈیٹ ہونے کے وقت کے کچھ عرصے بعد ذخیرہ کرتا ہے، اس لیے توسیع میں دو معاملات شامل ہوتے ہیں: کسی مقام کو یا تو پہلے کے وقت پر واپس لایا جانا چاہیے یا بعد کے وقت پر آگے بڑھایا جانا چاہیے۔ بنیادی خیال استفسار ونڈو کو بڑا کرنا ہے تاکہ یہ ان تمام اشیاء کو منسلک کرے جن کی پوزیشنیں اس کے لیبل ٹائم اسٹیمپ پر استفسار ونڈو کے اندر نہ ہوں لیکن استفسار ٹائم اسٹیمپ پر استفسار ونڈو میں داخل ہوں۔ توسیع کے بعد، وسیع استفسار ونڈو میں گرنے والی اشیاء کو تلاش کرنے کے لیے بی ایکس ٹری کی پارٹیشنوں کو عبور کرنے کی ضرورت ہے۔ ہر پارٹیشن میں، جگہ بھرنے والے منحنی خطوط کے استعمال کا مطلب یہ ہے کہ مقامی، دو جہتی جگہ میں ایک رینج استفسار تبدیل شدہ، ایک جہتی جگہ میں رینج استفساروں کا ایک مجموعہ بن جاتا ہے۔ سکویڈ ڈیٹا سیٹس میں توسیع کے بعد ضرورت سے زیادہ بڑے استفسار کے علاقے سے بچنے کے لیے، استفسار الگورتھم کی اصلاح موجود ہے، جو غیر ضروری استفسار کی توسیع سے گریز کرکے استفسار کی کارکردگی کو بہتر بناتا ہے۔ K قریب ترین پڑوسی استفسار K قریب ترین پڑوسی استفسار کا حساب K جوابات حاصل ہونے تک بڑھتے ہوئے سرچ ریجن کے ساتھ بار بار رینج کے سوالات انجام دے کر کیا جاتا ہے۔ ایک اور امکان یہ ہے کہ اسی طرح کے استفسار کے خیالات کو آئی ڈسٹنس تکنیک میں استعمال کیا جائے۔ دیگر سوالات رینج استفسار اور کے نیئرسٹ نیبر استفسار الگورتھم کو وقفے کے سوالات، مسلسل سوالات وغیرہ کی حمایت کے لیے آسانی سے بڑھایا جا سکتا ہے۔ چونکہ بی ایکس ٹری ایک انڈیکس ہے جو بی + ٹری انڈیکس کے اوپر بنایا گیا ہے، اس لیے بی ایکس ٹری میں تمام کارروائیاں، بشمول داخل کرنا، حذف کرنا اور تلاش، وہی ہیں جو بی + ٹری میں ہیں۔ ان کارروائیوں کے نفاذ کو تبدیل کرنے کی کوئی ضرورت نہیں ہے۔ فرق صرف اتنا ہے کہ موجودہ ڈی بی ایم ایس میں ذخیرہ شدہ طریقہ کار کے طور پر انڈیکسنگ کلید حاصل کرنے کے طریقہ کار کو نافذ کرنا ہے۔ لہذا، بی ایکس ٹری کو دانے کو چھوئے بغیر موجودہ ڈی بی ایم ایس میں آسانی سے ضم کیا جا سکتا ہے۔ اسپاڈ ایک مقبول ریلیشنل ڈیٹا بیس سسٹم مائی ایس کیو ایل کے اوپر بنایا گیا آبجیکٹ مینجمنٹ سسٹم ہے، جو آبجیکٹ کو انڈیکس کرنے کے لیے بی ایکس ٹری کا استعمال کرتا ہے۔ نفاذ میں، حرکت پذیر آبجیکٹ ڈیٹا کو تبدیل کیا جاتا ہے اور براہ راست مائی ایس کیو ایل پر محفوظ کیا جاتا ہے، اور سوالات کو معیاری ایس کیو ایل بیانات میں تبدیل کیا جاتا ہے جن پر ریلیشنل انجن میں مؤثر طریقے سے کارروائی کی جاتی ہے۔ سب سے اہم بات یہ ہے کہ یہ سب مائی ایس کیو ایل کور میں دراندازی کیے بغیر صاف ستھرے اور آزادانہ طور پر حاصل کیے جاتے ہیں۔ ڈیٹا سکیو کے ساتھ کارکردگی ٹیوننگ ممکنہ مسئلہ بی ایکس ٹری ایک جہتی کلید میں دو جہتی مقام کی نقشہ سازی کرتے ہوئے خلائی تقسیم کے لیے گرڈ کا استعمال کرتا ہے۔ اس سے اسکیوڈ ڈیٹا سے نمٹنے کے دوران استفسار اور اپ ڈیٹ آپریشن دونوں میں کارکردگی کا انحطاط متعارف ہو سکتا ہے۔ اگر گرڈ سیل زیادہ سائز کا ہے، تو بہت سی اشیاء سیل میں موجود ہوتی ہیں۔ چونکہ سیل میں موجود اشیاء انڈیکس سے الگ نہیں ہیں، اس لیے بنیادی B + ٹری میں کچھ اوور فلو نوڈس ہوں گے۔ اوور فلو پیجز کا موجود ہونا نہ صرف درخت کے توازن کو تباہ کرتا ہے بلکہ اپ ڈیٹ کی لاگت میں بھی اضافہ کرتا ہے۔ جہاں تک سوالات کا تعلق ہے، دیئے گئے استفسار کے علاقے کے لیے، بڑا خلیہ زیادہ غلط مثبت ہوتا ہے اور پروسیسنگ کے وقت میں اضافہ کرتا ہے۔ دوسری طرف، اگر جگہ کو باریک گرڈ کے ساتھ تقسیم کیا گیا ہے، یعنی۔ چھوٹے خلیات، ہر خلیے میں چند اشیاء ہوتی ہیں۔ شاید ہی اوور فلو پیجز ہوں تاکہ اپ ڈیٹ کی لاگت کو کم سے کم کیا جا سکے۔ استفسار میں کم غلط مثبت بازیافت کیے جاتے ہیں۔ تاہم، مزید خلیوں کو تلاش کرنے کی ضرورت ہے۔ تلاش شدہ خلیوں کی تعداد میں اضافہ استفسار کے کام کے بوجھ کو بھی بڑھاتا ہے۔ انڈیکس ٹیوننگ ایس ٹی 2 بی ٹری خلا میں ڈیٹا اسکیو اور وقت کے ساتھ ڈیٹا کی تبدیلی سے نمٹنے کے دوران بی ایکس ٹری کی کارکردگی کو ٹیون کرنے کے لیے ایک سیلف ٹیوننگ فریم ورک متعارف کراتا ہے۔ خلا میں ڈیٹا اسکیو سے نمٹنے کے لیے، ایس ٹی 2 بی-ٹری حوالہ پوائنٹس کے ایک سیٹ کا استعمال کرتے ہوئے پوری جگہ کو مختلف آبجیکٹ ڈینسٹی کے علاقوں میں تقسیم کرتا ہے۔ ہر خطہ ایک انفرادی گرڈ کا استعمال کرتا ہے جس کے خلیے کا سائز اس کے اندر موجود شے کی کثافت سے طے ہوتا ہے۔ بی ایکس ٹری میں مختلف وقت کے وقفوں کے حوالے سے متعدد پارٹیشن ہوتے ہیں۔ جیسے جیسے وقت گزرتا جاتا ہے، ہر تقسیم باری باری بڑھتی اور سکڑتی جاتی ہے۔ ایس ٹی 2 بی-ٹری اس خصوصیت کا استعمال انڈیکس کو آن لائن ٹیون کرنے کے لیے کرتا ہے تاکہ وقت کے ساتھ ڈیٹا میں ہونے والی تبدیلیوں کے مطابق جگہ کی تقسیم کو ایڈجسٹ کیا جا سکے۔ خاص طور پر، جیسے جیسے پارٹیشن خالی ہونے کے لیے سکڑتا ہے اور بڑھنے لگتا ہے، یہ تازہ ترین ڈیٹا ڈینسٹی کے مطابق ہر ریفرنس پوائنٹ کے لیے ریفرنس پوائنٹس کا ایک نیا سیٹ اور نیا گرڈ منتخب کرتا ہے۔ ٹیوننگ ایک مقررہ مدت کے دوران جمع کیے گئے تازہ ترین اعداد و شمار پر مبنی ہے، تاکہ اسپیس پارٹیشننگ کا طریقہ جدید ترین ڈیٹا کی تقسیم میں بہترین فٹ ہو۔ اس طریقے سے، ایس ٹی 2 بی-ٹری سے توقع کی جاتی ہے کہ وہ جگہ میں ڈیٹا سکیو کی وجہ سے ہونے والے اثر کو کم کرے گا اور وقت کے ساتھ ڈیٹا میں تبدیلی آئے گی۔ مزید دیکھیں B + درخت ہلبرٹ وکر Z-آرڈر (وکر) حوالہ جات B-درخت