درخت تی

در علوم کامپیوتر درخت 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 است: زمانی این درخت از تعادل خارج می‌شود که درخت‌های فرزندان گره از نظر ارتفاع حداقل به اندازه دو سطح متفاوت شده باشند. این مسئله زمانی روی می‌دهد که حذف یا اضافه کردن یک گره روی داده باشد. پس از افزودن یا حذف کردن باید درخت را از برگ تا ریشه اسکن کنید. اگر عدم تعادلی مشاهده کردید؛ باید یک چرخش درخت یا یک جفت چرخش انجام دهید تا تعادل کل درخت تضمین گردد.

اگر چرخش ناشی از این باشد که یک گره داخلی دارای تعداد آیتم‌های کمتری از تعداد حداقل مجاز باشد؛ آیتم‌های موجود در گره‌های فرزند جدید به داخل گره داخلی منتقل می‌شوند.

یادداشت ها[ویرایش]

این بخش خالی است. شما می‌توانید برای پر کردن آن کمک کنید.

این موارد را هم بخوانید[ویرایش]

درختان دیگر[ویرایش]

درخت B(درخت 3-2 ؛ درخت 4-3-2 ؛ درخت B+؛ درخت B* ؛ درخت UB)
الگوریتم DSW
درخت رقصنده
درخت ائتلاف
درخت kd
درخت هشت تایی
درخت چهارتایی
درخت R
درخت T
هرم T
درختان تاپ

منابع[ویرایش]

Tobin J. Lehman and Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986

پیوند به بیرون[ویرایش]

Oracle TimesTen FAQ entry on index mentioning T-Trees
Oracle Whitepaper: Oracle TimesTen Products and Technologies
DataBlitz presentation mentioning T-Trees
An Open-source T*-tree Library