لطفا به نکات زیر در هنگام خرید دانلود فایل پاورپوینت آشنايي با ايندکسهاي چند سطحي و درختواره اي توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود فایل پاورپوینت آشنايي با ايندکسهاي چند سطحي و درختواره اي قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 4 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

— پاورپوینت شامل تصاویر میباشد —-

اسلاید ۱ :

آشنايي با ايندکسهاي چند سطحي و درختواره اي
 
 
)Multi le el indexing & B-Trees)

نگاهداري ايندکس هاي ساده روي ديسک چه مشکلاتي بهمراه دارد؟

انواع درخت هاي دودويي کدامند؟                       (Binary Trees)

 

ايندکس چند سطحي چگونه است؟            (multi le el indexing)

 

ايندکس  B-Tree  چيست؟           (Balanced Trees)                      

اسلاید ۲ :

  نگاهداري ايندکس هاي ساده روي ديسک چه مشکلاتي بهمراه دارد؟

عمل جستجوي دودويي روي ديسک تعداد زيادي I/O احتياج دارد.          ( چرا؟ )

عمليات مربوط به ايجاد و حذف کليدها گران تمام مي شود.                       ( چرا؟ )

 

ايندکس بايد دائما بطور مرتب شده نگهداري شود.                                 ( چرا؟ )

                                      (راه حل چيست؟)

اسلاید ۳ :

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

   

  انواع درخت هاي دودويي کدامند؟                     (Binary Trees)

  

درخت دودويي ساده چيست؟ (Simple Binary Tree)                                  

درخت دودويي Adel’son el’skiiLandis چيست؟                ( (A L Tree  

 

درخت دودويي صفحه اي چيست؟                            (Paged Binary Tree )

 

اسلاید ۴ :

  انواع درخت هاي دودويي کدامند؟

  درخت دودويي ساده چيست؟(Simple Binary Tree)                                   

نوعي نمايش درختواره اي کليدها ميباشد.

بطوريکه آرايش اوليه کليدها امکان جستجوي دودوئي را فراهم ميسازد.

ولي هنگام حذف يا ايجاد کليدهاي جديد، مرتب سازي مجدد انجام نميشود.

در اينصورت با ايجاد و حذف کليدهاي بعدي توازن درخت ميتواند بهم بخورد.

در حالت توازن، هزينه جستجو مانند جستجوي دودوئي ميباشد.                         (چرا؟)

مثال:

يک ليست مرتب شده از کليدها را در نظر ميگيريم:

AX, CL, DE, FB, FT, HN, JD, KF, NR, PA, RF, SD, TK, WS, YJ

آرايش اوليه کليدها:

اسلاید ۵ :

    انواع درخت هاي دودويي کدامند؟         

  

  درخت  A L Tree چِيست؟

 

نوعي درخت دودويي با ارتفاع متوازن ( Height Balanced Tree ).

 

که در آن  تفاوت بين کوتاه ترين شاخه و بلندترين شاخه بيش از يک سطح نمي باشد.

 

هنگام جستجوي کليد تعداد I/O در بدترين حالت ۱٫۴۴ * log2(n+2)  مي باشد.

 

مثال:

براي جستجوي يک کليد در فايلي با ۱۰۰۰۰۰۰ رکورد چند I/O لازم است؟

 

در بدترين حالت بايد تعداد ۲۹ جستجو (I/O) انجام داد!

 

اين تعداد I/O هنوز زياد است!

                                                     (راه حل چيست؟)

اسلاید ۶ :

    انواع درخت هاي دودويي کدامند؟         

 

درخت  Paged Binary Tree چِيست؟

نوعي درخت دودويي است.

 

که هر گره (Node) آن شامل چندين گره درخت دودويي ساده ميباشد.                     (چرا؟)

 

درچنين ايندکسي چندين کليد در يک صفحه (Page) نگهداري ميشوند.

 

در اينصورت هنگام جستجوي کليد تعداد  I/Oبه طرز قابل ملاحظه اي پايين مي آيد.  (چرا؟)

 

اگر تعداد  کليد در صفحه k باشد، تعداد جستجو بين n  کليد چقدرخواهد بود؟

 

در بدترين حالت: logk+1(n+1)

 

اسلاید ۷ :

    درخت  Paged Binary Tree چِيست؟

مثال:

يک درخت دودويي ساده با تعداد n=134,217,727 کليد در نظر ميگيريم،

 

تعداد جستجوي لازم براي يافتن يک کليد چقدر ميشود؟

در بدترين حالت:   ۲۷

اگر اين درخت  با k=511  کليد در يک گره باشد،

 

تعداد جستجوي لازم براي يافتن يک کليد چقدر ميشود؟

در بدترين حالت:   ۳

 

اين نتيجه خوبي ميباشد!

ولي حالا مشکل اصلي، نگهداري يک paged binary tree مي باشد.

يعني پيدا نمودن الگوريتم بهينه جهت ايجاد وحذف کليدها با حفظ توازن درخت.

اسلاید ۸ :

   راه حل ايندکس چند سطحي چگونه است؟                         (multi le el indexing)

فايلي با  ۸۰۰۰۰۰۰ رکورد و کليد ۱۰ بايتي در نظر ميگيريم.

اندازه فايل ايندکس آن  ۸۰ مگا بايت ميشود.

با قرار دادن ۱۰۰ کليد در يک صفحه (page) يا رکورد، تعداد رکوردها ۸۰۰۰۰ ميشود.

جستجوي يک کليد در اين ايندکس به ۱۶ دسترسي به ديسک نياز خواهد داشت.            (چرا؟)

ايندکس سطح دوم چيست؟   (Second Le el Index)

حال ميتوانيم يک ايندکس سطح دوم براي تسهيل دسترسي به ايندکس اول تعريف کنيم.

بطوريکه هر رکورد آن ۱۰۰ کليد و هر کليد به يکي از رکوردهاي ايندکس اول اشاره کند.

تعداد رکوردهاي اين ايندکس ۸۰۰ خواهد بود.

جستجوي يک کليد در ايندکس دوم به ۸ دسترسي به ديسک نياز خواهد داشت.             (چرا؟)

اسلاید ۹ :

  ايندکس سطح سوم چيست؟     (Third Le el Index)

حال ميتوانيم يک ايندکس سطح سوم براي تسهيل دسترسي به ايندکس دوم تعريف کنيم.

بطوريکه هر رکورد آن ۱۰۰ کليد و هر کليد به يکي از رکوردهاي ايندکس دوم اشاره کند.

تعداد رکوردهاي اين ايندکس ۸ خواهد بود.                                             (چرا؟)

 ايندکس سطح چهارم چيست؟   (Fourth Le el Index)

در سطح چهارم فقط يک رکورد حاوي ۸ کليد خواهيم داشت.

اسلاید ۱۰ :

   چند نکته مهم:

 

با اين ساختار ايندکس تعداد دسترسي به ديسک براي يافتن يک کليد محدود به ۴ ميشود. 

 

فضاي اضافي براي نگهداري رکوردهاي ايندکس فقط %۱ اندازه ايندکس اوليه ميباشد.

 

(در اين مثال ۸۰۹ رکورد)

 

همين ساختار ( تا ۴ سطح ) ظرفيت نگهداري تا ۱۲ برابراين تعداد رکوردها را خواهد داشت.

 

( يعني ۱۰۰ ميليون رکورد )