File Structure
Lecture 13 آشنایی با ایندکسهای چند سطحی و درختواره ای )Multi level indexing & B-Trees) (Sections 9.1-9.6)
In the Name of God
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای )Multi level indexing & B-Trees)
نگاهداری ایندکس های ساده روی دیسک چه مشکلاتی بهمراه دارد؟
انواع درخت های دودویی کدامند؟ (Binary Trees)
ایندکس چند سطحی چگونه است؟ (multi level indexing)
ایندکس B-Tree چیست؟ (Balanced Trees)
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای )Multi level indexing & B-Trees)
نگاهداری ایندکس های ساده روی دیسک چه مشکلاتی بهمراه دارد؟
عمل جستجوی دودویی روی دیسک تعداد زیادی I/O احتیاج دارد. ( چرا؟ )
عملیات مربوط به ایجاد و حذف کلیدها گران تمام می شود. ( چرا؟ )
ایندکس باید دائما بطور مرتب شده نگهداری شود. ( چرا؟ )
(راه حل چیست؟)
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای
انواع درخت های دودویی کدامند؟ (Binary Trees)
درخت دودویی ساده چیست؟ (Simple Binary Tree)
درخت دودویی Adel’son-Vel’skii-Landis چیست؟ ( (AVL Tree
درخت دودویی صفحه ای چیست؟ (Paged Binary Tree )
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای
انواع درخت های دودویی کدامند؟
درخت دودویی ساده چیست؟(Simple Binary Tree)
نوعی نمایش درختواره ای کلیدها میباشد.
بطوریکه آرایش اولیه کلیدها امکان جستجوی دودوئی را فراهم میسازد.
ولی هنگام حذف یا ایجاد کلیدهای جدید، مرتب سازی مجدد انجام نمیشود.
در اینصورت با ایجاد و حذف کلیدهای بعدی توازن درخت میتواند بهم بخورد.
در حالت توازن، هزینه جستجو مانند جستجوی دودوئی میباشد. (چرا؟)
مثال:
یک لیست مرتب شده از کلیدها را در نظر میگیریم:
AX, CL, DE, FB, FT, HN, JD, KF, NR, PA, RF, SD, TK, WS, YJ
آرایش اولیه کلیدها:
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای
انواع درخت های دودویی کدامند؟
درخت AVL Tree چِیست؟
نوعی درخت دودویی با ارتفاع متوازن ( Height Balanced Tree ).
که در آن تفاوت بین کوتاه ترین شاخه و بلندترین شاخه بیش از یک سطح نمی باشد.
هنگام جستجوی کلید تعداد I/O در بدترین حالت 1.44 * log2(n+2) می باشد.
مثال:
برای جستجوی یک کلید در فایلی با 1000000 رکورد چند I/O لازم است؟
در بدترین حالت باید تعداد 29 جستجو (I/O) انجام داد!
این تعداد I/O هنوز زیاد است!
(راه حل چیست؟)
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای
درخت AVL Tree چِیست؟
مثال:
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای
انواع درخت های دودویی کدامند؟
درخت Paged Binary Tree چِیست؟
نوعی درخت دودویی است.
که هر گره (Node) آن شامل چندین گره درخت دودویی ساده میباشد. (چرا؟)
درچنین ایندکسی چندین کلید در یک صفحه (Page) نگهداری میشوند.
در اینصورت هنگام جستجوی کلید تعداد I/Oبه طرز قابل ملاحظه ای پایین می آید. (چرا؟)
اگر تعداد کلید در صفحه k باشد، تعداد جستجو بین n کلید چقدرخواهد بود؟
در بدترین حالت: logk+1(n+1)
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای
درخت Paged Binary Tree چِیست؟
مثال:
یک درخت دودویی ساده با تعداد n=134,217,727 کلید در نظر میگیریم،
تعداد جستجوی لازم برای یافتن یک کلید چقدر میشود؟
در بدترین حالت: 27
اگر این درخت با k=511 کلید در یک گره باشد،
تعداد جستجوی لازم برای یافتن یک کلید چقدر میشود؟
در بدترین حالت: 3
این نتیجه خوبی میباشد!
ولی حالا مشکل اصلی، نگهداری یک paged binary tree می باشد.
یعنی پیدا نمودن الگوریتم بهینه جهت ایجاد وحذف کلیدها با حفظ توازن درخت.
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای
راه حل ایندکس چند سطحی چگونه است؟ (multi level indexing)
فایلی با 8000000 رکورد و کلید 10 بایتی در نظر میگیریم.
اندازه فایل ایندکس آن 80 مگا بایت میشود.
با قرار دادن 100 کلید در یک صفحه (page) یا رکورد، تعداد رکوردها 80000 میشود.
جستجوی یک کلید در این ایندکس به 16 دسترسی به دیسک نیاز خواهد داشت. (چرا؟)
ایندکس سطح دوم چیست؟ (Second Level Index)
حال میتوانیم یک ایندکس سطح دوم برای تسهیل دسترسی به ایندکس اول تعریف کنیم.
بطوریکه هر رکورد آن 100 کلید و هر کلید به یکی از رکوردهای ایندکس اول اشاره کند.
تعداد رکوردهای این ایندکس 800 خواهد بود.
جستجوی یک کلید در ایندکس دوم به 8 دسترسی به دیسک نیاز خواهد داشت. (چرا؟)
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای
ایندکس سطح سوم چیست؟ (Third Level Index)
حال میتوانیم یک ایندکس سطح سوم برای تسهیل دسترسی به ایندکس دوم تعریف کنیم.
بطوریکه هر رکورد آن 100 کلید و هر کلید به یکی از رکوردهای ایندکس دوم اشاره کند.
تعداد رکوردهای این ایندکس 8 خواهد بود. (چرا؟)
ایندکس سطح چهارم چیست؟ (Fourth Level Index)
در سطح چهارم فقط یک رکورد حاوی 8 کلید خواهیم داشت.
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای
چند نکته مهم:
با این ساختار ایندکس تعداد دسترسی به دیسک برای یافتن یک کلید محدود به 4 میشود.
فضای اضافی برای نگهداری رکوردهای ایندکس فقط %1 اندازه ایندکس اولیه میباشد.
(در این مثال 809 رکورد)
همین ساختار ( تا 4 سطح ) ظرفیت نگهداری تا 12 برابراین تعداد رکوردها را خواهد داشت.
( یعنی 100 میلیون رکورد )
File Structure
آشنایی با ایندکسهای چند سطحی و درختواره ای
ایندکس B-Tree چیست؟ (Balanced Trees)
یک نوع ایندکس چند سطحی (multi level index ) با ساختاری شبیه مثال قبل میباشد.
که با یک الگوریتم ابداعی bottom up ساخته میشود،
تا هزینه ایجاد و حذف کلیدها ثابت و پایین بماند.
در این روش هر کلید جدید در یکی از گره های سطح 1 وارد شده،
و سپس در صورت لزوم سطوح دوم تا ریشه (root) به روز میشوند.