PH-tree
پی ایچ ٹری ایک ٹری ڈیٹا ڈھانچہ ہے جو کثیر جہتی ڈیٹا (چابیاں) جیسے جغرافیائی نقاط، پوائنٹس، فیچر ویکٹر، مستطیل یا باؤنڈنگ باکسز کی مقامی انڈیکسنگ کے لیے استعمال ہوتا ہے۔ پی ایچ ٹری خلائی تقسیم کرنے والا اشاریہ ہے جس کی ساخت کواڈٹری یا آکٹری سے ملتی جلتی ہے۔ تاہم، کواڈٹریز کے برعکس، یہ ٹرائٹس پر مبنی تقسیم کی پالیسی کا استعمال کرتا ہے اور کریٹ بٹ ٹریز سے ملتا جلتا ہے جو چابیاں کی بٹ نمائندگی پر مبنی ہے۔ بٹ پر مبنی تقسیم کی پالیسی، جب نوڈس کے لیے مختلف اندرونی نمائندگی کے استعمال کے ساتھ مل جاتی ہے، تو اعلی جہتی ڈیٹا کے ساتھ اسکیل ایبلٹی فراہم کرتی ہے۔ بٹ کی نمائندگی کی تقسیم کی پالیسی زیادہ سے زیادہ گہرائی بھی عائد کرتی ہے، اس طرح انحطاط پذیر درختوں اور دوبارہ توازن کی ضرورت سے گریز کیا جاتا ہے۔ جائزہ بنیادی پی ایچ ٹری ایک مقامی اشاریہ ہے جو کلیدوں کا نقشہ بناتا ہے، جو انٹیجرز کے ساتھ-جہتی ویکٹر ہیں، صارف کی متعین اقدار کے مطابق۔ پی ایچ ٹری ایک کریٹ بٹ ٹری کی کثیر جہتی عمومی کاری ہے اس معنی میں کہ ایک کریٹ بٹ ٹری-جہتی چابیاں والے پی ایچ ٹری کے برابر ہے۔ کریٹ بٹ ٹری کی طرح، اور زیادہ تر دیگر مقامی اشاریہ جات کے برعکس، پی ایچ ٹری ملٹی میپ کے بجائے نقشہ ہے۔ ایک جہتی پی ایچ ٹری نوڈس کا ایک درخت ہے جہاں ہر نوڈ پارٹیشن کو کواڈرینٹس میں تقسیم کرکے جگہ بناتا ہے (ذیل میں دیکھیں کہ اعلی جہتی ڈیٹا کے ساتھ ممکنہ طور پر بڑے نوڈس کتنے پیمانے پر ہوتے ہیں)۔ ہر کواڈرینٹ میں زیادہ سے زیادہ ایک اندراج ہوتا ہے، یا تو کلیدی قدر کا جوڑا (لیف کواڈرینٹ) یا کلیدی ذیلی نوڈ کا جوڑا۔ کلیدی ذیلی نوڈ کے جوڑے کے لیے، کلید ذیلی نوڈ کے مرکز کی نمائندگی کرتی ہے۔ کلید ذیلی نوڈ اور اس کے چائلڈ ذیلی نوڈس میں موجود تمام کلیدوں کا مشترکہ سابقہ (بٹ کی نمائندگی) بھی ہے۔ ہر نوڈ میں کم از کم دو اندراجات ہوتے ہیں، بصورت دیگر اسے پیرنٹ نوڈ کے ساتھ ضم کر دیا جاتا ہے۔ پی ایچ درختوں کی کچھ دیگر ساختی خصوصیات یہ ہیں: وہ-ایری درخت ہیں۔ وہ فطری طور پر غیر متوازن ہیں لیکن ان کی گہرائی چابیاں کی بٹ چوڑائی تک محدود ہونے کی وجہ سے عدم توازن محدود ہے، مثال کے طور پر۔ 32 بٹ انٹیجرز والی جہتی کلید کے لیے 32 تک۔ اندراج یا ہٹانے کی کارروائیوں کی وجہ سے بالکل ایک نوڈ میں ترمیم کی جاتی ہے اور ممکنہ طور پر دوسرا نوڈ شامل یا ہٹا دیا جاتا ہے۔ یہ بیک وقت عمل درآمد کے لیے مفید ثابت ہو سکتا ہے۔ اس کا مطلب یہ بھی ہے کہ ترمیم کی لاگت میں بہت کم فرق ہے۔ ان کی ساخت اندراج/ہٹانے کے حکم سے آزاد ہے۔ تقسیم کرنے کی حکمت عملی زیادہ تر کواڈٹریز کی طرح، پی ایچ ٹری نوڈس کا ایک درجہ بندی ہے جہاں ہر نوڈ تمام جہتوں میں جگہ کو تقسیم کرتا ہے۔ اس طرح، ایک نوڈ میں سب نوڈس ہو سکتے ہیں، ہر کواڈرینٹ کے لیے ایک۔ کواڈرینٹ نمبرنگ پی ایچ ٹری میں ان کی پوزیشن کا تعین کرنے کے لیے کثیر جہتی کلیدوں کے ٹکڑوں کا استعمال کرتا ہے۔ تمام چابیاں جن میں ایک جیسے لیڈنگ بٹس ہوتے ہیں وہ درخت کی ایک ہی شاخ میں محفوظ ہوتے ہیں۔ مثال کے طور پر، سطح پر ایک نوڈ میں، کواڈرینٹ کا تعین کرنے کے لیے جہاں ایک کلید داخل کی جانی چاہیے (یا ہٹا دی جانی چاہیے یا اوپر دیکھا جانا چاہیے)، یہ کلید کے ہر طول و عرض کے s بٹ کو دیکھتا ہے۔ 8 کواڈرینٹ والے تھری ڈی نوڈ کے لیے (مکعب کی تشکیل) کلید کے پہلے طول و عرض کا 's بٹ اس بات کا تعین کرتا ہے کہ آیا ہدف کواڈرینٹ مکعب کے بائیں یا دائیں طرف ہے، دوسرے طول و عرض کا' s بٹ اس بات کا تعین کرتا ہے کہ آیا یہ سامنے ہے یا پیچھے، اور تیسرے طول و عرض کا 's بٹ نیچے بمقابلہ اوپر کا تعین کرتا ہے، تصویر دیکھیں۔ 1 ڈی مثال 8 بٹ اقدار کے ساتھ تین 1 ڈی چابیاں کے ساتھ مثال:، اور۔ ایک خالی درخت میں جوڑنے اور اس کے نتیجے میں ایک نوڈ بنتا ہے۔ دونوں چابیاں پہلے اپنے چھٹے بٹ میں مختلف ہوتی ہیں لہذا نوڈ کی ایک سطح ہوتی ہے (0 سے شروع ہوتی ہے)۔ نوڈ میں 5 بٹ کا سابقہ ہوتا ہے جو دونوں کلیدوں کے عام 5 بٹس کی نمائندگی کرتا ہے۔ نوڈ میں دو کواڈرینٹ ہوتے ہیں، ہر کلید کو ایک کواڈرینٹ میں محفوظ کیا جاتا ہے۔ ایک اضافی نوڈ میں تیسری کلیدی کو شامل کرنے کے نتیجے میں ایک کواڈرینٹ جس میں اصل نوڈ سب نوڈ کے طور پر ہوتا ہے اور دوسرا کواڈرینٹ جس میں نئی کلید ہوتی ہے۔ 2 ڈی مثال 2 ڈی چابیاں کے ساتھ ہر نوڈ میں کواڈرینٹ ہوتے ہیں۔ کواڈرینٹ کی پوزیشن جہاں ایک کلید ذخیرہ کی جاتی ہے، کلیدوں کے متعلقہ بٹس سے نکالی جاتی ہے، ہر جہت سے ایک بٹ۔ نوڈ کے چار کواڈرینٹ 2 ڈی ہائپر کیوب بناتے ہیں (کواڈرینٹ خالی ہو سکتے ہیں)۔ چابیاں سے نکالی گئی بٹس ہائپر کیوب ایڈریس بناتی ہیں، کے لیے اور کے لیے۔ مؤثر طریقے سے نوڈ کے ہائپر کیوب میں کواڈرینٹ کی پوزیشن ہے۔ نوڈ ڈھانچہ نوڈ میں اندراجات کی ترتیب ہمیشہ زیڈ آرڈر کی پیروی کرتی ہے۔ مثال کے طور پر، نوڈ میں اندراجات کو سائز کی مقررہ سائز کی صفوں میں محفوظ کیا جا سکتا ہے۔ اس کے بعد مؤثر طریقے سے ایک کواڈرینٹ کا ایرے انڈیکس ہے۔ یہ تلاش کرنے، داخل کرنے اور ہٹانے کی اجازت دیتا ہے اور اسے ذخیرہ کرنے کی ضرورت نہیں ہے۔ خلائی پیچیدگی تاہم فی نوڈ ہے، لہذا یہ اعلی جہتی ڈیٹا کے لیے کم موزوں ہے۔ ایک اور حل یہ ہے کہ اندراجات کو ترتیب شدہ مجموعہ میں محفوظ کیا جائے، جیسے کہ متحرک صف اور/یا بی-درخت۔ یہ تلاش کی کارروائیوں کو سست کر دیتا ہے لیکن میموری کی کھپت کو کم کر دیتا ہے۔ اصل نفاذ کا مقصد کم سے کم میموری کی کھپت کے لیے فکسڈ اور ڈائنامک ایرے کی نمائندگی کے درمیان تبدیل کرنا ہے جس پر منحصر ہے کہ کم میموری استعمال ہوتی ہے۔ دیگر نفاذ متحرک طور پر تبدیل نہیں ہوتے ہیں لیکن اعلی جہتی ڈیٹا کے لیے فکسڈ صفوں، متحرک صفوں اور بی درختوں کا استعمال کرتے ہیں۔ آپریشنز لک اپ، انسرشن اور ہٹانے کی کارروائیاں سبھی ایک جیسے کام کرتی ہیں: صحیح نوڈ تلاش کریں، پھر نوڈ پر آپریشن انجام دیں۔ ونڈو کے سوالات اور قریبی پڑوسی کی تلاش زیادہ پیچیدہ ہیں۔ لک اپ آپریشن اس بات کا تعین کرتا ہے کہ درخت میں کوئی کلید موجود ہے یا نہیں۔ یہ درخت سے نیچے چلتا ہے اور ہر نوڈ کی جانچ کرتا ہے کہ آیا اس میں کوئی امیدوار ذیلی نوڈ ہے یا صارف کی قیمت جو کلید سے میل کھاتی ہے۔ فنکشن تلاش (کلید) اندراج ہے۔ اگر ٹری خالی نہیں ہے تو جڑ اندراج میں جڑ نوڈ ہوتا ہے جبکہ اندراج! = NIL & & & entry.is_subnode () ڈو نوڈ → entry.get_node () اندراج node.get_entry (کلید) ریپیٹ ریٹرن اندراج// اندراج NIL فنکشن ہو سکتا ہے۔ آپریشن لک اپ فنکشن کی طرح ٹری کو عبور کرتا ہے اور پھر کلید کو نوڈ میں داخل کرتا ہے۔ غور کرنے کے لیے کئی معاملات ہیں: کواڈرینٹ خالی ہے اور ہم صرف کواڈرینٹ میں ایک نیا اندراج داخل کر سکتے ہیں اور واپس آ سکتے ہیں۔ کواڈرینٹ میں ایک کلید کے ساتھ صارف کا اندراج ہوتا ہے جو نئے اندراج سے ملتا جلتا ہے۔ اس طرح کے تصادم سے نمٹنے کا ایک طریقہ یہ ہے کہ ایسا جھنڈا واپس کیا جائے جو ناکام اندراج کی نشاندہی کرتا ہو۔ اگر ٹری کو نوڈ کے اندراج کے طور پر مجموعہ کے ساتھ ملٹی میپ کے طور پر لاگو کیا جاتا ہے، تو اس مجموعہ میں نئی قیمت شامل کی جاتی ہے۔ کواڈرینٹ میں ایک مختلف کلید کے ساتھ ایک اندراج (صارف اندراج یا ذیلی نوڈ اندراج) ہوتا ہے۔ اس معاملے میں موجودہ اندراج کو ایک نئے ذیلی نوڈ کے ساتھ تبدیل کرنے کی ضرورت ہوتی ہے جس میں پرانی اور نئی اندراج ہوتی ہے۔ فنکشن انسرٹ (نوڈ، کلید، ویلیو) لیول کے لیے node.get_level ()// لیول 0 ہے۔ اگر اندراج = = NIL تو// کیس 1۔ انٹری _ نیو _ کریئٹ _ انٹری (کلید، ویلیو) node.set_entry (ایچ، انٹری _ نیو) ورنہ اگر! entry.is_subnode () & & entry.get_key () = = کلید تب// کیس 2۔ تصادم، پہلے سے ہی ایک انٹری ریٹرن ہے جس میں موجودہ اندراج اور نئے اندراج کے ساتھ تخلیق _ اندراج (کلید، entry.get_key ())/نیا ذیلی نوڈ، ذیلی نوڈ، تخلیق _ نوڈ (سطح _ تفریق، اندراج، اندراج _ نیا)، node.set_entry (h، ذیلی نوڈ، نیا) ختم ہوتا ہے اگر واپسی ہٹانا اندراج کے الٹا کام کرتا ہے، اس اضافی رکاوٹ کے ساتھ کہ اگر دو سے کم اندراجات باقی رہیں تو کسی بھی ذیلی نوڈ کو ہٹانا پڑتا ہے۔ بقیہ اندراج کو پیرنٹ نوڈ میں منتقل کر دیا جاتا ہے۔ ونڈو کے سوالات ونڈوز کے سوالات وہ سوالات ہیں جو آئتاکار محور سے منسلک ہائپر باکس کے اندر موجود تمام چابیاں واپس کرتے ہیں۔ ان کی تعریف دو جہتی نکات کے طور پر کی جا سکتی ہے اور جو استفسار خانے کے "نچلے بائیں" اور "اوپری دائیں" کونوں کی نمائندگی کرتے ہیں۔ ایک معمولی نفاذ نوڈ میں تمام اندراجات کو عبور کرتا ہے (جڑ نوڈ سے شروع ہوتا ہے) اور اگر کوئی اندراج اس سے میل کھاتا ہے تو اسے یا تو نتیجہ کی فہرست میں شامل کرتا ہے (اگر یہ صارف کا اندراج ہے) یا اسے بار بار منتقل کرتا ہے (اگر یہ ذیلی نوڈ ہے)۔ فنکشن کوری (نوڈ، منٹ، میکس، رزلٹ _ لسٹ) فورچ انٹری ہے۔ اگر entry.is_subnode () تو کریں اگر entry.get_prefix () = منٹ اور entry.get_prefix () <= میکس تو کوری (entry.get_subnode ()، منٹ، میکس، رزلٹ _ لسٹ) ختم ہو جاتی ہے اگر نہیں تو اگر entry.get_key ()> = منٹ اور entry.get_key () <= میکس تو result_list.add (انٹری) ختم ہو جاتی ہے اگر ختم ہو جاتی ہے اگر دہرایا جائے تو استفسار کے وقت کی پیچیدگی کا درست اندازہ لگانے کے لیے تجزیہ میں جہت کو شامل کرنے کی ضرورت ہوتی ہے۔ نوڈ میں تمام اندراجات کو تلاش کرنے اور ان کا موازنہ کرنے میں وقت کی پیچیدگی ہوتی ہے کیونکہ-جہتی کلید کے ساتھ ہر موازنہ میں وقت لگتا ہے۔ چونکہ نوڈس میں اندراجات تک ہو سکتے ہیں، اس لیے یہ طول و عرض میں اضافے کے ساتھ اچھی طرح سے پیمائش نہیں کرتا ہے۔ ہائپر کیوب ایڈریس کا استعمال کرکے اس نقطہ نظر کو بہتر بنانے کے مختلف طریقے ہیں۔ کم سے کم اور زیادہ سے زیادہ خیال یہ ہے کہ کواڈرینٹ کے پتے کے لیے کم سے کم اور زیادہ سے زیادہ اقدار تلاش کی جائیں تاکہ تلاش کچھ کواڈرینٹ سے بچ سکے جو استفسار خانے کے ساتھ اوورلیپ نہ ہوں۔ آئیے نوڈ کا مرکز بنیں (یہ نوڈ کے سابقہ کے برابر ہے) اور ہر ایک بٹس کے ساتھ دو بٹ تار بنیں۔ اس کے علاوہ، سبسکرپٹ کو 's' کے تھوڑا سا اور 'th طول و عرض، اور کی نشاندہی کرنے دیں۔ لیٹ اینڈ۔ پھر ہر جہت کے لیے "" ہوتا ہے جہاں نوڈ کا "نچلا" نصف اور اس میں موجود تمام کواڈرینٹ استفسار خانے کے ساتھ اوورلیپ نہیں ہوتے ہیں۔ اسی طرح، ہر جہت کے لیے "a" ہے جہاں "اوپری" نصف استفسار خانے کے ساتھ اوورلیپ نہیں ہوتا ہے۔ اور پھر ایک نوڈ میں سب سے کم اور سب سے زیادہ پیش کریں جسے عبور کرنے کی ضرورت ہے۔ استفسار خانے کے ساتھ یا اس کے ساتھ متصل نہ ہونے والے کواڈرینٹ۔ ایک ثبوت دستیاب ہے۔ اس کے ساتھ، مندرجہ بالا استفسار فنکشن کو بہتر بنایا جا سکتا ہے: فنکشن استفسار (نوڈ، کم از کم، زیادہ سے زیادہ، نتیجہ _ فہرست) h _ min ہے۔ نوڈ میں قبضہ شدہ کواڈرینٹس کی تقسیم پر منحصر ہے کہ یہ نقطہ نظر کہیں بھی نہیں سے لے کر تقریبا تمام کلیدی موازنہ سے بچنے کی اجازت دے گا۔ اس سے اوسط سفر کا وقت کم ہو جاتا ہے لیکن اس کے نتیجے میں پیدا ہونے والی پیچیدگی برقرار رہتی ہے۔ کواڈرینٹس کو کوری باکس کے ساتھ اوورلیپ کرنے کے لیے چیک کریں بیچ اور پھر بھی ایسے کواڈرینٹس ہو سکتے ہیں جو کوری باکس کے ساتھ اوورلیپ نہیں ہوتے ہیں۔ آئیڈیا: اور ہر ایک میں ہر طول و عرض کے لیے ایک بٹ ہوتا ہے جو اس بات کی نشاندہی کرتا ہے کہ آیا استفسار خانہ اس طول و عرض میں نوڈ کے نچلے/اوپری نصف کے ساتھ اوورلیپ ہوتا ہے۔ یہ فوری طور پر چیک کرنے کے لیے استعمال کیا جا سکتا ہے کہ آیا کوئی کواڈرینٹ-جہتی چابیاں کا موازنہ کیے بغیر استفسار خانے کے ساتھ اوورلیپ ہوتا ہے: ایک کواڈرینٹ استفسار خانے کے ساتھ اوورلیپ ہوتا ہے اگر اس میں موجود ہر "بٹ" کے لیے ایک متعلقہ "بٹ" ہے اور اس میں موجود ہر "بٹ" کے لیے ایک متعلقہ "بٹ" ہے۔ 64 بٹ رجسٹروں والے سی پی یو پر اس طرح ممکن ہے کہ اس میں-جہتی چابیاں کے اوورلیپ کی جانچ کی جائے۔ فنکشن ہے _ اوورلیپ (ایچ، ایچ _ منٹ، ایچ _ میکس) واپسی ہے (ایچ۔ ایچ _ منٹ) اور ایچ _ میکس = = ایچ// کا اندازہ 'سچ' پر ہوتا ہے اگر کواڈرینٹ اور استفسار اوورلیپ ہوتے ہیں۔ فنکشن استفسار (نوڈ، کم از کم، زیادہ سے زیادہ، نتیجہ _ فہرست) h _ min ہے کہ h _ min کا حساب لگائیں h _ mx کا حساب لگائیں ہر اندراج کے لیے h _ mx کا حساب لگائیں node.get_entries_range (h _ min، h _ mx) h entry.get_h کریں ؛ اگر (h | h _ min) & h _ mx = = h تو// 'سچ' کا اندازہ کرتا ہے اگر کواڈرینٹ اور استفسار اوورلیپ ہوتا ہے۔ [.] اختتام اگر بار بار واپسی کے نتیجے میں وقت کی پیچیدگی کا موازنہ مکمل تکرار سے کیا جاتا ہے۔ ٹریورس کواڈرینٹس جو استفسار خانے کے ساتھ اوورلیپ ہوتے ہیں بڑے نوڈس کے ساتھ اعلی طول و عرض کے لیے یہ بھی ممکن ہے کہ سب کے ذریعے تکرار سے بچا جائے اور اس کے بجائے براہ راست اگلے اعلی کا حساب لگائیں جو استفسار خانے کے ساتھ اوورلیپ ہوتا ہے۔ پہلا مرحلہ "-بٹس" کو ان تمام کواڈرینٹس کے لیے دیا گیا ہے جن کا استفسار خانے کے ساتھ کوئی اوورلیپ نہیں ہے۔ دوسرا مرحلہ موافقت شدہ اور اضافی "-بٹس" میں اضافہ کرتا ہے جو ایک اوور فلو کو متحرک کرتا ہے تاکہ غیر اوور لیپنگ کواڈرینٹس کو چھوڑ دیا جائے۔ آخری مرحلہ اوور فلو کو متحرک کرنے کے لیے استعمال ہونے والے تمام ناپسندیدہ ٹکڑوں کو ہٹا دیتا ہے۔ منطق کو تفصیل سے بیان کیا گیا ہے۔ حساب کتاب مندرجہ ذیل کام کرتا ہے: فنکشن انکریمنٹ _ ایچ (ایچ _ ان پٹ، ایچ _ منٹ، ایچ _ میکس) ایچ _ آؤٹ = ایچ _ ان پٹ۔ (~ ایچ _ میکس)// پری-ماسک ایچ _ آؤٹ + = 1// انکریمنٹ ایچ _ آؤٹ = (ایچ _ آؤٹ اور ایچ _ میکس)۔ ایچ _ منٹ// پوسٹ-ماسک ریٹرن ایچ _ آؤٹ پھر، اس کے لیے زیادہ تر سی پی یوز پر کیا جا سکتا ہے۔ نوڈ کو عبور کرنے کے نتیجے میں وقت کی پیچیدگی ہے۔ یہ سب سے بہتر کام کرتا ہے اگر استفسار خانے کے ساتھ اوورلیپ ہونے والے زیادہ تر کواڈرینٹ اندراج کے ساتھ موجود ہوں۔ - قریب ترین پڑوسیوں کے قریب ترین پڑوسیوں کی تلاش کو معیاری الگورتھم کا استعمال کرتے ہوئے لاگو کیا جا سکتا ہے۔ فلوٹنگ پوائنٹ کیز پی ایچ ٹری صرف انٹیجر ویلیوز کو اسٹور کر سکتا ہے۔ فلوٹنگ پوائنٹ ویلیوز کو معمولی طور پر انٹیجرز کے طور پر محفوظ کیا جا سکتا ہے جو انہیں ایک انٹیجر کاسٹ کرتے ہیں۔ تاہم، کے مصنفین بھی درستگی کے نقصان کے بغیر ایک نقطہ نظر کی تجویز کرتے ہیں۔ بغیر کسی نقصان کے فلوٹنگ پوائنٹ ویلیو کو بغیر کسی نقصان کے انٹیجر ویلیو (اور بیک) میں تبدیل کرنا اگر درستگی صرف فلوٹنگ پوائنٹ ویلیو کے 32 یا 64 بٹس کو انٹیجر (32 یا 64 بٹس کے ساتھ) کے طور پر سمجھ کر حاصل کی جا سکتی ہے۔ جس طرح سے IEEE 754 فلوٹنگ پوائنٹ ویلیوز کو انکوڈ کرتا ہے، اس کے نتیجے میں آنے والی انٹیجر ویلیوز کم از کم مثبت ویلیوز کے لیے اصل فلوٹنگ پوائنٹ ویلیوز کی طرح ہی ترتیب رکھتی ہیں۔ منفی اقدار کے لیے آرڈر غیر سائن بٹس کو الٹ کر حاصل کیا جا سکتا ہے۔ جاوا میں نفاذ کی مثالیں: لمبا انکوڈ (ڈبل ویلیو) {لمبا r = Double.doubleToRawLongBits (ویلیو) ؛ واپسی (r> = 0)؟ r: r ^ 0x7ffffffffffffffFLFFL ؛} C + + میں مثالی نفاذ: std:: int64 _ t انکوڈ (ڈبل ویلیو) {std:: int64 _ t r ؛ memcpy (& r، & ویلیو، سائز (r)) ؛ واپسی r> = 0؟ r: r ^ 0x7ffffffffffffffffffFFFFFL ؛} انکوڈنگ (اور الٹا ڈیکوڈنگ) تمام فلوٹنگ پوائنٹ ویلیوز کے لیے نقصان سے پاک ہے۔ آرڈر عملی طور پر اچھی طرح سے کام کرتا ہے، بشمول اور۔ تاہم، عدد کی نمائندگی بھی ایک عام موازنہ قدر (انفینیٹی سے چھوٹی) میں بدل جاتی ہے، انفینیٹیز ایک دوسرے سے موازنہ کرتی ہیں اور ان سے بڑی ہوتی ہیں۔ اس کا مطلب یہ ہے کہ، مثال کے طور پر، استفسار کی حد کی قدر سے میل نہیں کھائے گی۔ استفسار کی حد سے ملنے کے لیے ہونا ضروری ہے۔ ہائپر باکس چابیاں حجم (محور سے منسلک ہائپر باکسز) کو چابیاں کے طور پر ذخیرہ کرنے کے لیے، نفاذ عام طور پر کونے کی نمائندگی کا استعمال کرتے ہیں جو باکس کے دو جہتی کم از کم اور زیادہ سے زیادہ کونوں کو طول و عرض کے ساتھ ایک کلید میں تبدیل کرتا ہے، مثال کے طور پر ان کو آپس میں جوڑ کر: یہ تلاش کرنے، داخل کرنے اور ہٹانے کے کاموں کے لیے معمولی طور پر کام کرتا ہے۔ ونڈو کے سوالات کو جہتی ویکٹر سے جہتی ویکٹر میں تبدیل کرنے کی ضرورت ہے۔ مثال کے طور پر، ایک ونڈو استفسار کے لیے جو استفسار خانے کے اندر مکمل طور پر موجود تمام خانوں سے میل کھاتا ہے، استفسار کلیدیں یہ ہیں: ونڈو استفسار آپریشن کے لیے جو استفسار خانے کے ساتھ ملنے والے تمام خانوں سے میل کھاتا ہے، استفسار کلیدیں یہ ہیں: اسکیل ایبلٹی اعلی جہتوں میں اندراجات سے کم کے ساتھ، ایک پی ایچ ٹری میں صرف ایک نوڈ ہو سکتا ہے، جو مؤثر طریقے سے زیڈ آرڈر وکر کے ساتھ بی-ٹری میں "انحطاط" کر سکتا ہے۔ ایڈ/ہٹائیں/تلاش کی کارروائیاں باقی ہیں اور ونڈو کے سوالات کواڈرینٹ فلٹرز کا استعمال کر سکتے ہیں۔ تاہم، یہ طول و عرض کی لعنت سے بچ نہیں سکتا، کیونکہ پی ایچ ٹری کے ساتھ اعلی جہتی ڈیٹا مکمل اسکین سے صرف معمولی طور پر بہتر ہے۔ یوزز ریسرچ نے بڑے اور تیزی سے بدلتے ہوئے ڈیٹا سیٹس کے ساتھ تیز رفتار ایڈ/ہٹانے/عین مطابق میچ آپریشنز کی اطلاع دی ہے۔ ونڈو کے سوالات کو خاص طور پر چھوٹی ونڈوز یا بڑے ڈیٹا سیٹ کے لیے اچھی طرح سے کام کرنے کے لیے دکھایا گیا ہے۔ پی ایچ ٹری بنیادی طور پر میموری کے استعمال کے لیے موزوں ہے۔ نوڈس کا سائز (اندراجات کی تعداد) طے کیا جاتا ہے جبکہ مستقل اسٹوریج ڈسک پر صفحہ کے سائز کے ساتھ نوڈ کے سائز کو سیدھ میں لانے کے لیے ترتیب دینے کے قابل نوڈ سائز والے انڈیکس سے فائدہ اٹھاتا ہے۔ یہ دیگر مقامی اشاریہ جات، جیسے کہ آر-ٹریز کے ساتھ آسان ہے۔ نفاذ جاوا: اصل موجد سی + + کا گٹ ہب ذخیرہ: اصل موجد سی + + کا گٹ ہب ذخیرہ: گٹ ہب ذخیرہ سی + +: گٹ ہب ذخیرہ یہ بھی دیکھیں بائنری اسپیس پارٹیشننگ بائنری ٹائلنگ کے-ڈی ٹری آکٹری کواڈٹری آر-ٹری یو بی-ٹری اسپاٹیل ڈیٹا بیس بیرونی لنکس پی ایچ ٹری ویب سائٹ تفصیلی وضاحت، مثالوں اور کارکردگی کے موازنہ کے ساتھ حوالہ جات درخت (ڈیٹا ڈھانچے) ڈیٹا بیس انڈیکس تکنیک جیومیٹرک ڈیٹا ڈھانچے