آموزش سیستم مدیریت پایگاه داده - هشینگ

برای یک ساختار پایگاه داده بزرگ، تقریباً غیرممکن است که تمام مقادیر ایندکس را از طریق تمام سطوح آن جستجو کنیم و سپس به بلوک داده مورد نظر برسیم تا داده مطلوب را بازیابی کنیم. هشینگ یک تکنیک موثر است برای محاسبه مکان مستقیم یک رکورد داده در دیسک بدون استفاده از ساختار ایندکس.

هشینگ از توابع هش با استفاده از کلیدهای جستجو به عنوان پارامترها برای تولید آدرس یک رکورد داده استفاده می‌کند.

سازماندهی هشینگ

• سطل (Bucket) - یک فایل هش داده را در قالب سطل ذخیره می‌کند. سطل واحدی از ذخیره سازی است. به طور معمول، یک سطل یک بلاک دیسک کامل را ذخیره می‌کند که در عوض می‌تواند یک یا چند رکورد را ذخیره کند.

• تابع هش (Hash Function) - یک تابع هش، h، یک تابع نگاشت است که تمام مجموعه کلیدهای جستجو K را به آدرسی که رکوردهای واقعی در آن قرار می‌گیرند، نگاشت می‌کند. این یک تابع از کلیدهای جستجو به آدرس‌های سطل است.

هشینگ استاتیک

در هشینگ استاتیک، هنگامی که یک مقدار کلید جستجو فراهم می‌شود، تابع هش همیشه آدرسی یکسان را محاسبه می‌کند. به عنوان مثال، اگر از تابع هش mod-4 استفاده شود، تنها 5 مقدار تولید خواهد شد. آدرس خروجی برای آن تابع همیشه یکسان خواهد بود. تعداد سطل‌های ارائه شده در همه زمان‌ها ثابت می‌ماند.

عملیات

• درج (Insertion) - وقتی یک رکورد با استفاده از هش استاتیک وارد شود، تابع هش h آدرس سطل برای کلید جستجو K را محاسبه می‌کند، جایی که رکورد در آن ذخیره خواهد شد.

  آدرس سطل = h(K)

• جستجو (Search) - وقتی یک رکورد نیاز به بازیابی دارد، همان تابع هش می‌تواند برای بازیابی آدرس سطل که داده در آن ذخیره شده است، استفاده شود.

• حذف (Delete) - این به سادگی یک عمل جستجو دنبال شده توسط یک عمل حذف است.

سیل خروج سطل

شرایط سیل خروج سطل به عنوان تصادف شناخته می‌شود. این یک وضعیت مهلک برای هر تابع هش استاتیک است. در این حالت، زنجیره‌بندی سیل خروج می‌تواند استفاده شود.

• زنجیره‌بندی سیل خروج - وقتی سطل‌ها پر شده‌اند، برای همان نتیجه هش یک سطل جدید تخصیص داده می‌شود و پس از آن به سطل قبلی پیوند داده می‌شود. این مکانیزم هشینگ بسته نامیده می‌شود.

• مطابقت خطی - وقتی یک تابع هش یک آدرس را تولید می‌کند که داده در آن قبلاً ذخیره شده است، سطل خالی بعدی برای آن اختصاص داده می‌شود. این مکانیزم هشینگ باز نامیده می‌شود.

هشینگ پویا

مشکل هشینگ استاتیک این است که هنگام رشد یا کاهش اندازه پایگاه داده، به صورت پویا تغییر اندازه نمی‌کند. هشینگ پویا یک مکانیزم فراهم می‌کند که به صورت پویا و بر اساس نیاز، سطل‌های داده اضافه و حذف می‌شوند. هشینگ پویا همچنین به عنوان هشینگ گسترده نیز شناخته می‌شود.

تابع هش، در هشینگ پویا، باید تعداد زیادی مقدار تولید کند و تنها تعداد کمی از آن‌ها در ابتدا استفاده می‌شود.

سازماندهی

پیشوند یک مقدار هش به عنوان یک شاخص هش در نظر گرفته می‌شود. تنها بخشی از مقدار هش برای محاسبه آدرس‌های سطل استفاده می‌شود. هر شاخص هش یک مقدار عمق دارد که نشان می‌دهد چند بیت برای محاسبه یک تابع هش استفاده می‌شود. این بیت‌ها می‌توانند به 2n سطل اشاره کنند. وقتی کلیه این بیت‌ها مصرف می‌شوند - به عبارت دیگر، وقتی همه سطل‌ها پر هستند - آنگاه مقدار عمق به طور خطی افزایش می‌یابد و دو برابر سطل‌ها تخصیص داده می‌شود.

عملیات

• پرس‌وجو (Querying) - عمق شاخص هش را بررسی کنید و از آن بیت‌ها برای محاسبه آدرس سطل استفاده کنید.

• به‌روزرسانی (Update) - پرس‌وجو را همانطور که گفته شد انجام داده و داده را به‌روز کنید.

• حذف (Deletion) - پرس‌وجو را انجام داده و داده مورد نظر را حذف کنید.

• درج (Insertion) - آدرس سطل را محاسبه کنید

  • اگر سطل قبلاً پر شده است.
    • سطل‌های بیشتری اضافه کنید.
    • بیت‌های اضافی به مقدار هش اضافه کنید.
    • تابع هش را دوباره محاسبه کنید.
  • در غیر این صورت
    • داده را به سطل اضافه کنید،
  • اگر تمام سطل‌ها پر باشند، روش‌های هشینگ استاتیک را اجرا کنید.

هشینگ مناسب نیست وقتی داده‌ها در یک ترتیب سازماندهی شده باشند و پرس‌وجوها نیاز به محدوده‌ای از داده‌ها داشته باشند. وقتی داده‌ها گسسته و تصادفی باشند، هش بهترین عملکرد را ارائه می‌دهد.

الگوریتم‌های هشینگ پیچیدگی بیشتری نسبت به فهرست‌بندی دارند. تمام عملیات هش در زمان ثابت انجام می‌شود.