پاورپوینت آشنايي با ايندکسهاي چند سطحي و درختواره اي

دانلود پاورپوینت با موضوع آشنايي با ايندکسهاي چند سطحي و درختواره اي،

در قالب ppt و در 13 اسلاید، قابل ویرایش.

آشنايي با ايندکسهاي چند سطحي و درختواره اي
انواع درخت هاي دودويي کدامند؟        
درخت  Paged Binary Tree چِيست؟
نوعي درخت دودويي است.
که هر گره (Node) آن شامل چندين گره درخت دودويي ساده ميباشد.                     (چرا؟)
درچنين ايندکسي چندين کليد در يک صفحه (Page) نگهداري ميشوند.
در اينصورت هنگام جستجوي کليد تعداد  I/Oبه طرز قابل ملاحظه اي پايين مي آيد.  (چرا؟)
اگر تعداد  کليد در صفحه k باشد، تعداد جستجو بين n  کليد چقدرخواهد بود؟
در بدترين حالت: logk+1(n+1)درخت  Paged Binary Tree چِيست؟
مثال:
يک درخت دودويي ساده با تعداد n=134,217,727 کليد در نظر ميگيريم،
تعداد جستجوي لازم براي يافتن يک کليد چقدر ميشود؟
در بدترين حالت:   27
اگر اين درخت  با k=511  کليد در يک گره باشد،
تعداد جستجوي لازم براي يافتن يک کليد چقدر ميشود؟
در بدترين حالت:   3
اين نتيجه خوبي ميباشد!
 ولي حالا مشکل اصلي، نگهداري يک paged binary tree مي باشد.
يعني پيدا نمودن الگوريتم بهينه جهت ايجاد وحذف کليدها با حفظ توازن درخت.
   راه حل ايندکس چند سطحي چگونه است؟                           (multi level indexing)
فايلي با  8000000 رکورد و کليد 10 بايتي در نظر ميگيريم.
اندازه فايل ايندکس آن  80 مگا بايت ميشود.
با قرار دادن 100 کليد در يک صفحه (page) يا رکورد، تعداد رکوردها 80000 ميشود.
جستجوي يک کليد در اين ايندکس به 16 دسترسي به ديسک نياز خواهد داشت.            (چرا؟)
ايندکس سطح دوم چيست؟                 (Second Level Index)
حال ميتوانيم يک ايندکس سطح دوم براي تسهيل دسترسي به ايندکس اول تعريف کنيم.
بطوريکه هر رکورد آن 100 کليد و هر کليد به يکي از رکوردهاي ايندکس اول اشاره کند.
تعداد رکوردهاي اين ايندکس 800 خواهد بود.
جستجوي يک کليد در ايندکس دوم به 8 دسترسي به ديسک نياز خواهد داشت.             (چرا؟)