بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
روش Hashing قابل توسعه
v مشکلات روش Hashing با فضای ثابت (Static) چيست؟
v
v انواع روشهاي ديگرHashing کدامند؟
vروش Hashing با فضای قابل توسعه (Extendible) چيست؟
v
vروش Hashing با فضای پويا (Dynamic) چيست؟
v
vروش Hashing با توسعه خطي (Linear) چيست؟
اسلاید 2 :
روش Hashingبا فضای قابل توسعه
مشکلات روش Hashing با فضای ثابت (Static) چيست؟
فضاي ايجاد شده در آغاز ممکن است بسيار بيش ازحد نياز باشد. (چرا؟)
ممکن است مرتبا نياز به تجديد ساختار داشته باشد. (چرا؟)
در مقايسه با B-tree برای فايل های داده با اندازه متغير (Dynamic) مناسب نميباشد. (چرا؟)
تعداد زياد عمليات حذف و اضافه کليدها باعث پايين آمدن راندمان ميشود. (چرا؟)
روش Hashing با فضای قابل توسعه (Extendible) چيست؟
در اين روش فضاي رزرو شده برحسب نياز بزرگتر يا کوچکتر ميشود.
تعداد زياد عمليات حذف و اضافه کليدها باعث پايين آمدن راندمان نمي شود. (چرا؟)
برای فايل های داده با اندازه متغير (Dynamic) مناسب تر ميباشد. (درمقايسه با؟)
اسلاید 3 :
ساختارHashing با فضای قابل توسعه چگونه است؟
ترکيبي از روش Hashing با ساختاري به نام Trie ميباشد.
کليدها در تعدادي Bucket قرار مي گيرند.
Bucketها به صورت اجزاء مستقل از يکديگر روي فضاي موجود ديسکها رزرو شده اند.
کليدهايي که آدرس Hash آنها Prefix مشترکي داشته باشد در يک Bucket قرار مي گيرند.
اسلاید 4 :
ساختار Trie
ساختار Trie چيست؟
نوعي ساختار درختواره ای که براي دسته بندی کليدها استفاده ميشود.
اين ساختار را به نام Radix Searching نيز مي شناسند.
شکل زير يک ساختار Trie موسوم به Radix 26 را نشان ميدهد.
در اين مثال هر نود بر مبناي يکي از حروف Prefix کليد، آنرا به يکي از 26 شاخه زيرين خود تخصيص ميدهد.
اسلاید 5 :
ساختار Trie چيست؟
شکل زير نيز يک نوع ساختار Trie به نام Radix 10 را نشان ميدهد.
در اين مثال هر نود بر مبناي يکي از ارقام Prefix کليد، آنرا به يکي از ده شاخه زيرين خود تخصيص مي دهد.
اسلاید 6 :
روش استفاده از ساختار Trie در Hashing
چگونه از ساختار Trie در Hashing استفاده ميشود؟
در روش Hashing از نوعي ساختار Trie به نام Radix 2 استفاده مي کنيم.
در اين ساختار، هر نود بر مبناي يکي از بيتهاي Prefix کليد ، آنرا به يکي از دو شاخه زيرين خود تخصيص مي دهد.
مثال: شکل زير نمونه ای از اين ساختار را نشان مي دهد.
Bucket A شامل کليدهايي خواهد بود که دو بيت اول کليد Hash آنها 00 يا 01 باشد.
Bucket B شامل کليدهايي خواهد بود که دو بيت اول کليد Hash آنها 10 باشد.
Bucket C شامل کليدهايي خواهد بود که دو بيت اول کليد Hash آنها 11 باشد.
اسلاید 7 :
نگهداري ساختار Trie روي ديسک
روش نگهداري يک ساختار Trie رويديسک چگونه است؟
هنگاميکه حجم داده ها بالا برود و فضاي RAM برای کليه نودها کافي نباشد،
بايستي بتوان به هريک از نودهاي اين ساختار مستقيما روي ديسک دسترسي پيدا نمود.
دراينصورت مسائلي مشابه با ساختارهاي B-Tree دوباره مطرح مي گردند و
مکانيزم Hashing مزيت خود را در مقابل B-Tree از دست ميدهد.
اسلاید 8 :
تبديل يک ساختار Trie به Directory چگونه است؟
براي حفظ مزيتهاي مکانيزم Hashing لازم است که ساختار درختواره اي Trie را به يک ساختار مسطح و يکپارچه تبديل کنيم.
در اين صورت کافيست که ساختار Trie را بسط داده تا يک Binary Tree کامل بدست آوريم و سپس آنرا بصورت يک Array پياده سازي نماييم.
اين ساختار جديد (Array) بعنوان يک Directory که به Bucketهاي مختلف اشاره ميکند استفاده خواهد شد.
اسلاید 9 :
در صورت پر شدن يک Bucket چگونه عمل ميشود؟
حالت اول:
فضاي Directory امکان اضافه نمودن يک Bucket جديد برادر (يا Buddy Bucket) در مجاورت Bucket پر شده را ميدهد.
در اينصورت Bucket جديد اضافه گشته و کليدها بين دو Bucket برحسب Prefix مربوطه توزيع ميشوند.
مثال: شکل زير اين حالت را پس از پرشدن Bucket A و ايجاد Bucket D نشان مي دهد.
اسلاید 10 :
در صورت پر شدن يک Bucket چگونه عمل ميشود؟
(2حالت دوم:
امکان ايجاد يک Buddy Bucket وجود ندارد.
بنابراين درصورت Overflow بايستي از روش Splitting استفاده نمود.
مثال: شکل زير اين حالت را پس از پر شدن Bucket B و ايجاد Bucket D نشان ميدهد.
