بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
آشنايي با ايندکسهاي چند سطحي و درختواره اي
)Multi le el indexing & B-Trees)
نگاهداريايندکس هاي ساده روي ديسکچه مشکلاتي بهمراه دارد؟
انواع درخت هاي دودويي کدامند؟ (Binary Trees)
ايندکس چند سطحي چگونه است؟ (multi le el indexing)
ايندکس B-Tree چيست؟ (Balanced Trees)
اسلاید 2 :
نگاهداريايندکس هاي ساده روي ديسک چه مشکلاتي بهمراه دارد؟
عمل جستجويدودويي روي ديسک تعداد زيادي I/O احتياج دارد. ( چرا؟ )
عمليات مربوط به ايجاد و حذف کليدهاگران تمام مي شود. ( چرا؟ )
ايندکس بايد دائما بطور مرتب شده نگهداري شود. ( چرا؟ )
(راه حل چيست؟)
اسلاید 3 :
آشنايي با ايندکسهاي چند سطحي و درختواره اي
انواع درخت هاي دودويي کدامند؟ (Binary Trees)
(1درخت دودوييساده چيست؟ (SimpleBinary Tree)
(2 درخت دودوييAdel’son-el’skii-Landis چيست؟ ( (A L Tree
(3درخت دودوييصفحه اي چيست؟ (Paged Binary Tree)
اسلاید 4 :
انواع درخت هاي دودويي کدامند؟
(1 درخت دودويي ساده چيست؟(SimpleBinary Tree)
نوعينمايش درختواره ايکليدها ميباشد.
بطوريکه آرايش اوليه کليدها امکان جستجوي دودوئي را فراهم ميسازد.
ولي هنگام حذف يا ايجاد کليدهاي جديد، مرتب سازي مجدد انجام نميشود.
در اينصورت با ايجاد و حذف کليدهاي بعدي توازن درخت ميتواند بهم بخورد.
در حالت توازن، هزينه جستجو مانند جستجوي دودوئي ميباشد. (چرا؟)
مثال:
يک ليست مرتب شده از کليدها را در نظر ميگيريم:
AX, CL, DE, FB, FT, HN, JD, KF, NR, PA, RF, SD, TK, WS, YJ
آرايش اوليه کليدها:
اسلاید 5 :
انواع درخت هاي دودويي کدامند؟
(2 درخت A L Tree چِيست؟
نوعي درخت دودويي با ارتفاع متوازن ( Height Balanced Tree ).
که در آن تفاوت بين کوتاه ترين شاخه و بلندترين شاخه بيش از يک سطح نمي باشد.
هنگام جستجوي کليد تعداد I/O در بدترين حالت 1.44 * log2(n+2) مي باشد.
مثال:
براي جستجوي يک کليد در فايلي با 1000000 رکورد چند I/O لازم است؟
در بدترين حالت بايد تعداد 29 جستجو (I/O) انجام داد!
اين تعدادI/O هنوز زياد است!
(راه حل چيست؟)
اسلاید 6 :
انواع درخت هاي دودويي کدامند؟
(3درخت Paged Binary Tree چِيست؟
نوعي درخت دودويي است.
که هر گره (Node) آن شامل چندين گره درخت دودويي ساده ميباشد. (چرا؟)
درچنين ايندکسي چندينکليد در يک صفحه (Page) نگهداري ميشوند.
در اينصورت هنگام جستجوي کليد تعداد I/Oبه طرز قابل ملاحظه اي پايين مي آيد. (چرا؟)
اگر تعداد کليد در صفحه k باشد، تعداد جستجو بين n کليد چقدرخواهد بود؟
در بدترين حالت: logk+1(n+1)
اسلاید 7 :
درخت Paged Binary Tree چِيست؟
مثال:
يک درخت دودويي ساده با تعداد n=134,217,727 کليد در نظر ميگيريم،
تعداد جستجوي لازم براي يافتن يک کليد چقدر ميشود؟
در بدترين حالت: 27
اگر اين درخت با k=511 کليد در يک گره باشد،
تعداد جستجوي لازم براي يافتن يک کليد چقدر ميشود؟
در بدترين حالت: 3
اين نتيجه خوبي ميباشد!
ولي حالا مشکل اصلي، نگهداري يک paged binary tree مي باشد.
يعني پيدا نمودن الگوريتمبهينه جهت ايجاد وحذف کليدها با حفظ توازن درخت.
اسلاید 8 :
راه حلايندکسچند سطحي چگونه است؟ (multi le el indexing)
فايلي با 8000000رکورد و کليد 10بايتي در نظر ميگيريم.
اندازه فايل ايندکس آن 80مگا بايت ميشود.
با قرار دادن 100کليد در يک صفحه (page) يا رکورد، تعداد رکوردها80000 ميشود.
جستجوي يک کليد در اين ايندکس به 16دسترسي به ديسک نياز خواهد داشت. (چرا؟)
ايندکس سطح دوم چيست؟ (Second Le el Index)
حال ميتوانيم يک ايندکس سطحدوم براي تسهيل دسترسي بهايندکساول تعريف کنيم.
بطوريکه هر رکورد آن 100کليد و هر کليد به يکي از رکوردهاي ايندکس اولاشاره کند.
تعدادرکوردهاي اين ايندکس 800 خواهد بود.
جستجوي يک کليد در ايندکسدوم به 8دسترسي به ديسک نياز خواهد داشت. (چرا؟)
اسلاید 9 :
ايندکس سطح سوم چيست؟ (Third Le el Index)
حال ميتوانيم يک ايندکس سطحسوم براي تسهيل دسترسي به ايندکس دوم تعريف کنيم.
بطوريکه هر رکورد آن 100کليد و هر کليد به يکي از رکوردهاي ايندکس دوماشاره کند.
تعداد رکوردهاي اين ايندکس 8 خواهد بود. (چرا؟)
ايندکس سطح چهارم چيست؟ (Fourth Le el Index)
در سطح چهارمفقط يک رکورد حاوي 8کليد خواهيم داشت.
اسلاید 10 :
چند نکته مهم:
با اين ساختار ايندکس تعداد دسترسي به ديسک براي يافتن يک کليد محدود به 4 ميشود.
فضاي اضافي براي نگهداري رکوردهاي ايندکس فقط %1 اندازه ايندکس اوليه ميباشد.
(در اين مثال 809رکورد)
همين ساختار ( تا 4 سطح ) ظرفيت نگهداري تا 12برابراينتعداد رکوردها را خواهد داشت.
( يعني 100 ميليون رکورد )
