در علوم کامپیوتر درخت T یک نوع ساختار دادههای درختی باینری است که اصولاً توسط پایگاه دادههای حافظه اصلی مثل datablitx, EXtremeDB, MySQL Cluster, Oracle Times Ten & MobileLite استفاده میشود.
یک درخت T عبارتست از یک ساختار دادههای درختی به صورت فهرست متعادل بهینهسازی شده که در آن میتوان هم فهرست و هم دادههای واقعی را بهطور کامل در حافظه نگهداری کرد؛ همانطور که درخت B یک ساختار شاخص بهینهسازی شده برای ذخیره بر روی دستگاههای ذخیره ساز ثانویه مثل هارد دیسک میباشد. درخت T در جستجوی مزایای عملکرد در ساختارهای درختی موجود در حافظه میباشد مثل درختهای AVL اما در عین حال از فضاهای عظیم ذخیرهسازی در بالای سر ؛ که در این نوع درختان بسیار رایج است ؛ هم اجتناب میکند.
درختان T نسخه برداری از زمینههای دادههای نمایه شده در گرههای درخت شاخص را انجام نمیدهند. بلکه آنها از این واقعیت سود می برند که دادههای واقعی همیشه به همراه فهرست داخل حافظه اصلی وجود دارند بنابراین آنها فقط دارای اشاره گرهایی برای اشاره به رشتههای دادههای واقعی هستند.
حرف “T” در درخت T به شکل ساختار گره دادهها اشاره دارد که در مقاله اصلی و برای اولین بار به این نوع شاخص اشاره شدهاست.
اگرچه به نظر میرسد که درختان T در پایگاههای دادههای حافظه اصلی کاربردهای فراوانی دارند اما تحقیقات اخیر نشان دادهاند که آنها بهتر از درختان B در سخت افزارهای مدرن عمل نمیکنند:
مقاله (Rao, Jun; Kenneth A. Ross 1999)؛ با نام "مخزن نمایهسازی آگاهانه برای پشتیبانی از تصمیمگیری در حافظه اصلی". مجموعه مقالات بیست و پنجمین کنفرانس بینالمللی در زمینه پایگاههای دادههای بسیار بزرگ (VLDB 1999) . مورگان کافمان؛ صفحات 78 تا 89.
مقاله (Kim, Kyungwha; Junho Shim & Ig-hoon Lee 2007)؛ با عنوان مخزن درختان آگاهانه: آنها چگونه در ریزپردازندههای کالای فعلی کار میکنند؟ از مجموعه مقالات پنجمین کنفرانس بینالمللی علوم محاسبات و کاربردهای آن (ICCSA 2007). اسپرینگر؛ صفحات 189 تا 200. DOI: 10.1007/978-3-540-74472-6_15 .
به نظر میرسد که علت اصلی فرضیات سنتی در خصوص منابع حافظه باشد که دارای هزینههای یکنواخت هستند اما فعلاً و با توجه به مسئله شکاف سرعت فعلی بین دسترسی به مخزن و دسترسی به حافظه اصلی معتبر شناخته نمیشوند.
یک درخت T دارای گرههایی است که معمولاً شامل یک اشاره گر به گره والد؛ گرههای چپ و راست فرزند هستند و همچنین یک آرایه منظم از اشاره گرهای دادهها و همچنین کنترل دادههای اضافی در اختیار دارند. گرههایی که دارای دو درخت فرعی باشند به نام گرههای داخلی شناخته شده و گرههایی که دارای درختان فرعی نباشند را گرههای برگ می نامند. گرههایی که فقط یک درخت فرعی داشته باشند را گرههای نیم برگ می نامند. گرهی را گره محدود به یک ارزش می نامند که آن ارزش بین ارزشهای حداقل و حداکثر آن گره قرار داشته باشد.
ارزشهای محدود شده هر گره داخلی میتواند دارای گرههای برگ یا نیم برگ باشد که شامل سلف ارزشهای دادههای کوچکتر هستند (به نام بزرگترین کران پائین) یا میتواند شامل جانشین با ارزشهای دادههای بزرگتر از خودش باشد (به نام حداقل کران بالا). گرههای برگ و نیم برگ میتوانند شامل تعدادی از عناصر دادهها باشد که از 1 تا حداکثر سایز آرایه دادهها باشد. گرههای داخلی تلاش میکنند تا فضای اشغال شده آنها بین اعداد حداقل و حداکثر از عناصر باقی بماند.
این بخش نیاز به گسترش دارد (ژوئن 2008)
هر زمان که یک گره جدیدی افزوده میشود؛ درخت باید دوباره تنظیم گردد؛ به شرح ذیل.
اکنون باید نوع گره را تشخیص بدهیم:
اگر آرایه کنونی دادههای گره کمتر از تعداد عناصر حداقل باشد؛ پس ارزش بزرگترین حد پائینی این گره به ارزش دادههای آن منتقل میشود. در ادامه یکی از دو مرحله ذیل برای گره برگ یا نیم برگ که ارزش آن برداشته شده باشد انجام می دهیم.
اگر این ارزش تنها عنصر موجود در آرایه دادهها باشد؛ پس گره بهطور کامل حذف میشود. در صورت لزوم باید درخت را دوباره تنظیم کنید.
اگر آرایه دادههای گره را بتوان با آرایههای دادههای برگهایش ادغام کرد بهصورتی که هیچ مازادی مشاهده نشود؛ این کار را انجام داده و گره برگ را بر می دارید. در صورت لزوم باید درخت را دوباره تنظیم کنید.
این بخش نیاز به توسعه دارد (ژوئن 2008) یک درخت T بر روی یک درخت جستجوی باینری با تعادل خودبخودی اجرا میشود. بهطور خاص؛ مقاله Lehman & Carey توصیفکننده یک درخت T متعادل همانند درخت AVL است: زمانی این درخت از تعادل خارج میشود که درختهای فرزندان گره از نظر ارتفاع حداقل به اندازه دو سطح متفاوت شده باشند. این مسئله زمانی روی میدهد که حذف یا اضافه کردن یک گره روی داده باشد. پس از افزودن یا حذف کردن باید درخت را از برگ تا ریشه اسکن کنید. اگر عدم تعادلی مشاهده کردید؛ باید یک چرخش درخت یا یک جفت چرخش انجام دهید تا تعادل کل درخت تضمین گردد.
اگر چرخش ناشی از این باشد که یک گره داخلی دارای تعداد آیتمهای کمتری از تعداد حداقل مجاز باشد؛ آیتمهای موجود در گرههای فرزند جدید به داخل گره داخلی منتقل میشوند.
این بخش خالی است. شما میتوانید برای پر کردن آن کمک کنید.