مرجع دانلود پاورپوینت های درسی

حجم فایل : 97.5 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 14
بنام خدا File Structure 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) مي باشد.

مثال:
براي جستجوي...