پاورپوینت آشنايي با ايندکسهای چند سطحی و درختواره ای (pptx) 13 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 13 اسلاید
قسمتی از متن PowerPoint (.pptx) :
Lecture 13 آشنايي با ايندکسهاي چند سطحي و درختواره اي )Multi level indexing & B-Trees) (Sections 9.1-9.6)
In the Name of God
آشنايي با ايندکسهاي چند سطحي و درختواره اي )Multi level indexing & B-Trees)
نگاهداري ايندکس هاي ساده روي ديسک چه مشکلاتي بهمراه دارد؟
انواع درخت هاي دودويي کدامند؟ (Binary Trees)
ايندکس چند سطحي چگونه است؟ (multi level indexing)
ايندکس B-Tree چيست؟ (Balanced Trees)
آشنايي با ايندکسهاي چند سطحي و درختواره اي )Multi level indexing & B-Trees)
نگاهداري ايندکس هاي ساده روي ديسک چه مشکلاتي بهمراه دارد؟
عمل جستجوي دودويي روي ديسک تعداد زيادي I/O احتياج دارد. ( چرا؟ )
عمليات مربوط به ايجاد و حذف کليدها گران تمام مي شود. ( چرا؟ )
ايندکس بايد دائما بطور مرتب شده نگهداري شود. ( چرا؟ )
(راه حل چيست؟)
آشنايي با ايندکسهاي چند سطحي و درختواره اي
انواع درخت هاي دودويي کدامند؟ (Binary Trees)
درخت دودويي ساده چيست؟ (Simple Binary Tree)
درخت دودويي Adel’son-Vel’skii-Landis چيست؟ ( (AVL Tree
درخت دودويي صفحه اي چيست؟ (Paged Binary Tree )
آشنايي با ايندکسهاي چند سطحي و درختواره اي
انواع درخت هاي دودويي کدامند؟
درخت دودويي ساده چيست؟(Simple Binary Tree)
نوعي نمايش درختواره اي کليدها ميباشد.
بطوريکه آرايش اوليه کليدها امکان جستجوي دودوئي را فراهم ميسازد.
ولي هنگام حذف يا ايجاد کليدهاي جديد، مرتب سازي مجدد انجام نميشود.
در اينصورت با ايجاد و حذف کليدهاي بعدي توازن درخت ميتواند بهم بخورد.
در حالت توازن، هزينه جستجو مانند جستجوي دودوئي ميباشد. (چرا؟)
مثال:
يک ليست مرتب شده از کليدها را در نظر ميگيريم:
AX, CL, DE, FB, FT, HN, JD, KF, NR, PA, RF, SD, TK, WS, YJ
آرايش اوليه کليدها:
آشنايي با ايندکسهاي چند سطحي و درختواره اي
انواع درخت هاي دودويي کدامند؟
درخت AVL Tree چِيست؟
نوعي درخت دودويي با ارتفاع متوازن ( Height Balanced Tree ).
که در آن تفاوت بين کوتاه ترين شاخه و بلندترين شاخه بيش از يک سطح نمي باشد.
هنگام جستجوي کليد تعداد I/O در بدترين حالت 1.44 * log2(n+2) مي باشد.
مثال:
براي جستجوي يک کليد در فايلي با 1000000 رکورد چند I/O لازم است؟
در بدترين حالت بايد تعداد 29 جستجو (I/O) انجام داد!
اين تعداد I/O هنوز زياد است!
(راه حل چيست؟)
آشنايي با ايندکسهاي چند سطحي و درختواره اي
درخت AVL Tree چِيست؟
مثال:
آشنايي با ايندکسهاي چند سطحي و درختواره اي
انواع درخت هاي دودويي کدامند؟
درخت 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 مي باشد.
يعني پيدا نمودن الگوريتم بهينه جهت ايجاد وحذف کليدها با حفظ توازن درخت.
