T-tree
کمپیوٹر سائنس میں ٹی-ٹری بائنری ٹری ڈیٹا اسٹرکچر کی ایک قسم ہے جو مین میموری ڈیٹا بیس، جیسے ڈیٹابلیٹز، ایکسٹریم ڈی بی، مائی ایس کیو ایل کلسٹر، اوریکل ٹائم ٹین اور موبائل لائٹ کے ذریعے استعمال ہوتی ہے۔ ٹی-ٹری ایک متوازن انڈیکس ٹری ڈیٹا ڈھانچہ ہے جو ان صورتوں کے لیے بہتر بنایا گیا ہے جہاں انڈیکس اور اصل ڈیٹا دونوں کو مکمل طور پر میموری میں رکھا جاتا ہے، جس طرح بی-ٹری ایک انڈیکس ڈھانچہ ہے جو ہارڈ ڈسک جیسے بلاک پر مبنی ثانوی اسٹوریج ڈیوائسز پر اسٹوریج کے لیے بہتر بنایا گیا ہے۔ ٹی درخت اے وی ایل درختوں جیسے ان میموری ٹری ڈھانچوں کے کارکردگی کے فوائد حاصل کرنے کی کوشش کرتے ہیں جبکہ اسٹوریج کی بڑی جگہ سے گریز کرتے ہیں جو ان کے لیے عام ہے۔ ٹی-ٹری انڈیکسڈ ڈیٹا فیلڈز کی کاپیاں خود انڈیکس ٹری نوڈس کے اندر نہیں رکھتے ہیں۔ اس کے بجائے، وہ اس حقیقت کا فائدہ اٹھاتے ہیں کہ اصل ڈیٹا ہمیشہ انڈیکس کے ساتھ مل کر مین میموری میں ہوتا ہے تاکہ ان میں صرف اصل ڈیٹا فیلڈز کے اشارے موجود ہوں۔ ٹی ٹری میں 'ٹی' اصل کاغذ میں نوڈ ڈیٹا ڈھانچے کی شکل سے مراد ہے جس نے پہلے اس قسم کے انڈیکس کو بیان کیا تھا۔ نوڈ ڈھانچے ایک ٹی-ٹری نوڈ عام طور پر پیرنٹ نوڈ، بائیں اور دائیں چائلڈ نوڈ، ڈیٹا پوائنٹرز کی ایک ترتیب شدہ صف اور کچھ اضافی کنٹرول ڈیٹا پر مشتمل ہوتا ہے۔ دو ذیلی درختوں والے نوڈس کو اندرونی نوڈس کہا جاتا ہے، ذیلی درختوں کے بغیر نوڈس کو لیف نوڈس کہا جاتا ہے اور صرف ایک ذیلی درخت والے نوڈس کو ہاف لیف نوڈس کہا جاتا ہے۔ نوڈ کو کسی ویلیو کے لیے باؤنڈنگ نوڈ کہا جاتا ہے اگر ویلیو نوڈ کی موجودہ کم از کم اور زیادہ سے زیادہ ویلیو کے درمیان ہو۔ ہر اندرونی نوڈ کے لیے، پتی یا نصف پتی کے نوڈس موجود ہوتے ہیں جن میں اس کی سب سے چھوٹی ڈیٹا ویلیو کا پیشرو ہوتا ہے (جسے سب سے بڑا نچلا باؤنڈ کہا جاتا ہے) اور جس میں اس کی سب سے بڑی ڈیٹا ویلیو کا جانشین ہوتا ہے (جسے سب سے کم اوپری باؤنڈ کہا جاتا ہے)۔ لیف اور ہاف لیف نوڈس میں ڈیٹا ایلری کے ایک سے لے کر زیادہ سے زیادہ سائز تک کسی بھی تعداد میں ڈیٹا عناصر شامل ہو سکتے ہیں۔ اندرونی نوڈس عناصر کی پہلے سے طے شدہ کم سے کم اور زیادہ سے زیادہ تعداد کے درمیان اپنا قبضہ رکھتے ہیں الگورتھم تلاش جڑ نوڈ سے شروع ہوتی ہے اگر موجودہ نوڈ سرچ ویلیو کے لیے باؤنڈنگ نوڈ ہے تو اس کے ڈیٹا ایرے کو تلاش کریں۔ اگر ڈیٹا ایرے میں ویلیو نہیں ملتی ہے تو سرچ ناکام ہوجاتی ہے۔ اگر تلاش کی قیمت موجودہ نوڈ کی کم از کم قیمت سے کم ہے تو اس کے بائیں ذیلی درخت میں تلاش جاری رکھیں۔ اگر کوئی لیفٹ سبٹری نہ ہو تو سرچ ناکام ہو جاتی ہے۔ اگر تلاش کی قیمت موجودہ نوڈ کی زیادہ سے زیادہ قیمت سے زیادہ ہے تو اس کے دائیں ذیلی ٹری میں تلاش جاری رکھیں۔ اگر کوئی صحیح ذیلی ٹری نہ ہو تو تلاش ناکام ہو جاتی ہے۔ اندراج نئی قیمت کے لیے باؤنڈنگ نوڈ کی تلاش کریں۔ اگر ایسا نوڈ موجود ہے تو چیک کریں کہ آیا اس کے ڈیٹا ایرے میں ابھی بھی جگہ موجود ہے، اگر ایسا ہے تو نئی ویلیو داخل کریں اور اگر کوئی جگہ دستیاب نہیں ہے تو فنش کریں پھر نوڈ کے ڈیٹا ایرے سے کم از کم ویلیو کو ہٹا دیں اور نئی ویلیو داخل کریں۔ اب نوڈ کے لیے سب سے بڑی نچلی باؤنڈ رکھنے والے نوڈ کی طرف بڑھیں جس میں نئی ویلیو ڈالی گئی تھی۔ اگر ہٹائی گئی کم از کم قیمت اب بھی وہاں فٹ بیٹھتی ہے تو اسے نوڈ کی نئی زیادہ سے زیادہ قیمت کے طور پر شامل کریں، ورنہ اس نوڈ کے لیے ایک نیا دائیں ذیلی نوڈ بنائیں۔ اگر کوئی باؤنڈنگ نوڈ نہیں ملا تو آخری تلاش شدہ نوڈ میں ویلیو داخل کریں اگر یہ اب بھی اس میں فٹ بیٹھتا ہے۔ اس صورت میں نئی قیمت یا تو نئی کم از کم یا زیادہ سے زیادہ قیمت بن جائے گی۔ اگر قیمت اب فٹ نہیں ہوتی ہے تو ایک نیا بائیں یا دائیں ذیلی ٹری بنائیں۔ اگر ایک نیا نوڈ شامل کیا گیا تو درخت کو دوبارہ متوازن کرنے کی ضرورت پڑ سکتی ہے، جیسا کہ ذیل میں بیان کیا گیا ہے۔ حذف کرنے کے لیے ویلیو کے باؤنڈنگ نوڈ کے لیے تلاش کریں۔ اگر کوئی باؤنڈنگ نوڈ نہیں ملتا ہے تو ختم کریں۔ اگر باؤنڈنگ نوڈ میں ویلیو نہیں ہے تو ختم کریں۔ نوڈ کے ڈیٹا ایرے سے ویلیو کو حذف کریں اب ہمیں نوڈ کی قسم سے فرق کرنا ہوگا: اندرونی نوڈ: اگر نوڈ کے ڈیٹا ایرے میں اب عناصر کی کم از کم تعداد سے کم ہے تو اس نوڈ کی سب سے بڑی نچلی باؤنڈ ویلیو کو اس کے ڈیٹا ویلیو میں منتقل کریں۔ نصف پتی یا پتی کے نوڈ کے لیے درج ذیل دو مراحل میں سے ایک کے ساتھ آگے بڑھیں جس سے قیمت کو ہٹا دیا گیا تھا۔ لیف نوڈ: اگر ڈیٹا ایرے میں یہ واحد عنصر تھا تو نوڈ کو حذف کر دیں۔ اگر ضرورت ہو تو درخت کو دوبارہ متوازن کریں۔ ہاف لیف نوڈ: اگر نوڈ کے ڈیٹا ایرے کو اس کے لیف کے ڈیٹا ایرے کے ساتھ اوور فلو کے بغیر ضم کیا جا سکتا ہے تو ایسا کریں اور لیف نوڈ کو ہٹا دیں۔ اگر ضرورت ہو تو درخت کو دوبارہ متوازن کریں۔ گردش اور توازن ایک ٹی ٹری کو ایک بنیادی سیلف بیلنسنگ بائنری سرچ ٹری کے اوپر لاگو کیا جاتا ہے۔ خاص طور پر، لیمن اور کیری کے مضمون میں اے وی ایل درخت کی طرح متوازن ٹی درخت کی وضاحت کی گئی ہے: یہ توازن سے باہر ہو جاتا ہے جب نوڈ کے چائلڈ درخت کم از کم دو سطحوں سے اونچائی میں مختلف ہوتے ہیں۔ یہ نوڈ کے داخل ہونے یا حذف ہونے کے بعد ہو سکتا ہے۔ داخل کرنے یا حذف کرنے کے بعد، درخت کو پتی سے جڑ تک اسکین کیا جاتا ہے۔ اگر کوئی عدم توازن پایا جاتا ہے، تو درخت کی ایک گردش یا جوڑی گردش کی جاتی ہے، جس سے پورے درخت کو متوازن کرنے کی ضمانت ملتی ہے۔ جب گردش کے نتیجے میں اندرونی نوڈ میں اشیاء کی کم سے کم تعداد ہوتی ہے، تو نوڈ کے نئے چائلڈ (رین) سے آئٹمز کو اندرونی نوڈ میں منتقل کر دیا جاتا ہے۔ کارکردگی اور ذخیرہ اگرچہ ایک زمانے میں کارکردگی کے فوائد کی وجہ سے مین میموری ڈیٹا بیس کے لیے ٹی-ٹری بڑے پیمانے پر استعمال ہوتے تھے، لیکن بہت بڑے مین میموری ڈیٹا بیس کے حالیہ رجحانات پروویژننگ لاگت پر زیادہ زور دیتے ہیں۔ جدید این او ایس کیو ایل ڈیٹا بیس سسٹمز کے ساتھ اکثر کھربوں ریکارڈز کو محفوظ کیا جاتا ہے، یہاں تک کہ ایک انڈیکس کو ذخیرہ کرنے کے لیے میموری کی لاگت دسیوں یا سینکڑوں ٹیرابائٹس سے بھی زیادہ ہو سکتی ہے جس میں اصل اقدار شامل ہوں۔ یہ بھی دیکھیں ٹری (گراف تھیوری) ٹری (سیٹ تھیوری) ٹری اسٹرکچر ایکسپونینشیل ٹری دیگر ٹری B-ٹری (2-3 ٹری، 2-3-4 ٹری، B + ٹری، B *-ٹری، UB-ٹری) ڈانسنگ ٹری فیوژن ٹری K-D ٹری آکٹری کواڈٹری R-ٹری ریڈکس ٹری ٹاپ ٹری حوالہ جات بیرونی لنکس اوریکل ٹائمز ٹی-ٹری اوریکل وائٹ پیپر کا ذکر کرنے والے انڈیکس پر دس سوالات اندراج: اوریکل ٹائمز ٹین پروڈکٹس اینڈ ٹیکنالوجیز ڈیٹا بلٹز پریزنٹیشن جس میں ٹی-ٹری کا ذکر ہے ایک اوپن سورس T *-ٹری لائبریری بائنری ٹری سرچ ٹری