روشهای نمایهسازی و دسترسی
نمایهها و روشهای دسترسی، ساختارهای داده کمکی هستند – عمدتاً درختان B+ و نمایههای هش – که به پایگاه داده اجازه میدهند تا بدون اسکن کل جدول، تاپلهای منطبق را پیدا کند و مسیرهای دسترسی سریعی را فراهم میکنند که بهینهساز به آنها متکی است.
Definition
نمایه یک ساختار داده کمکی بر روی یک یا چند ویژگی از یک رابطه است که مقادیر کلید را به مکانهای تاپلهای منطبق نگاشت میکند و امکان بازیابی در زمانی کمتر از خطی نسبت به اندازه جدول را فراهم میآورد؛ یک روش دسترسی، مکانیزمی است که یک پرس و جو برای خواندن دادهها استفاده میکند، مانند اسکن کامل یا اسکن نمایه.
Scope
این موضوع ساختارها و مفاهیم پشت مسیرهای دسترسی به داده را پوشش میدهد: تمایز بین نمایههای خوشهای و غیرخوشهای، اولیه و ثانویه؛ درخت B+ به عنوان نمایهی مرتبسازی پرکاربرد که از جستجوی برابری و محدودهای پشتیبانی میکند؛ نمایههای مبتنی بر هش برای جستجوی برابری؛ و نقش نمایهها در انتخاب، اتصال، و اجتناب از مرتبسازی. این موضوع به چگونگی تأثیر انتخاب نمایه بر هزینه پرس و جو و سربار بهروزرسانی میپردازد. انتخاب کلی طرح توسط بهینهساز مبتنی بر هزینه، که یک موضوع جداگانه است، از این بحث مستثنی است.
Core questions
- چگونه یک درخت B+ از پرس و جوهای برابری و محدودهای به طور کارآمد پشتیبانی میکند؟
- تفاوت بین نمایههای خوشهای و غیرخوشهای، اولیه و ثانویه چیست؟
- چه زمانی یک نمایه هش بر یک نمایه درختی ترجیح داده میشود؟
- چگونه نمایهها انتخابها، اتصالها و بازیابی مرتبشده را سرعت میبخشند؟
- هزینه نگهداری نمایهها تحت درج، بهروزرسانی و حذف چیست؟
Key concepts
- نمایه درخت B+
- نمایه هش
- نمایه خوشهای در مقابل غیرخوشهای
- نمایههای اولیه و ثانویه
- نمایههای متراکم و پراکنده
- جستجوی محدودهای و برابری
- هشسازی توسعهپذیر و خطی
- هزینه نگهداری نمایه
Key theories
- نمایههای درخت B+
- درخت B+ یک درخت جستجوی متوازن با فنآوت بالا است که کلیدها را به ترتیب مرتبشده ذخیره میکند و تمام ارجاعات داده در برگها قرار دارند؛ این درخت از پرس و جوهای برابری و محدودهای و اسکنهای مرتبشده با ورودی/خروجی لگاریتمی پشتیبانی میکند و تحت درج و حذف متوازن باقی میماند.
- نمایههای خوشهای در مقابل غیرخوشهای
- یک نمایه خوشهای، ردیفهای جدول را به صورت فیزیکی بر اساس کلید نمایه مرتب نگه میدارد، که اسکنهای محدودهای را بسیار کارآمد میکند، در حالی که یک نمایه غیرخوشهای (ثانویه) به یک فایل نامرتب اشاره میکند، بنابراین بازیابی بسیاری از ردیفهای منطبق ممکن است به ازای هر ردیف یک عملیات ورودی/خروجی هزینه داشته باشد.
- نمایههای هش
- نمایههای مبتنی بر هش، کلیدها را برای جستجوهای برابری با زمان ثابت مورد انتظار به سطلها نگاشت میکنند اما از پرس و جوهای محدودهای پشتیبانی نمیکنند؛ طرحهای دینامیک مانند هشسازی توسعهپذیر و خطی به آنها اجازه میدهند تا با دادهها به طور تدریجی رشد کنند.
Clinical relevance
نمایهسازی رایجترین اهرم عملی برای عملکرد پایگاه داده است: انتخاب نمایههای صحیح میتواند اسکنهای کامل جدول را به جستجوهای میلیثانیهای برای پرس و جوهای تراکنشی و تحلیلی تبدیل کند، در حالی که نمایهسازی بیش از حد، بهروزرسانیها را کند میکند، بنابراین طراحی نمایه یک تصمیم مکرر در عملیات سیستمهای واقعی است.
History
بایر و مککریت درخت B را در سال ۱۹۷۲ برای نگهداری نمایههای مرتبشده بزرگ روی دیسک معرفی کردند؛ گونه درخت B+، که تمام دادهها را در برگها نگه میدارد، به نمایه استاندارد پایگاه داده تبدیل شد، همانطور که در مقاله «درخت B فراگیر» کامر در سال ۱۹۷۹ بررسی شد. روشهای دسترسی مبتنی بر هش و طرحهای هش دینامیک به موازات هم توسعه یافتند، و هر دو خانواده همچنان هسته اصلی هر موتور رابطهای هستند.
Key figures
- Rudolf Bayer
- Edward McCreight
- Douglas Comer
Related topics
Seminal works
- bayer1972
- comer1979
- ramakrishnan2003
Frequently asked questions
- چرا در پایگاههای داده به جای درختان جستجوی دودویی از درختان B+ استفاده میشود؟
- پایگاههای داده، دادهها را روی دیسک ذخیره میکنند، جایی که هزینه عمدتاً توسط تعداد خواندن صفحات تعیین میشود. درختان B+ دارای فنآوت بالا هستند، بنابراین هر گره یک صفحه دیسک را پر میکند و درخت بسیار کمعمق است، که تنها به چند عملیات ورودی/خروجی برای رسیدن به هر رکورد نیاز دارد. یک درخت دودویی بسیار عمیقتر خواهد بود و دسترسیهای دیسک بسیار بیشتری را به همراه خواهد داشت.
- چه زمانی باید از نمایه هش به جای درخت B+ استفاده کنم؟
- زمانی که فقط به جستجوهای برابری نیاز دارید (مثلاً یافتن ردیف با یک شناسه مشخص) و دسترسی با زمان ثابت مورد انتظار را میخواهید، از نمایه هش استفاده کنید. زمانی که به پرس و جوهای محدودهای، اسکنهای مرتبشده یا تطابق پیشوندی نیز نیاز دارید، از درخت B+ استفاده کنید، زیرا نمایههای هش ترتیب کلید را حفظ نمیکنند و نمیتوانند به طور کارآمد به شرایط محدودهای پاسخ دهند.