ایندکس کلاستر چیست؟ - مقدمه

در آموزش ایندکس چیست با مفهوم و کاربرد ایندکس کلاستر، بصورت کلی آشنا شدیم و در آموزش B-Tree چیست نیز ساختار مورد نیاز جهت نگهداری ایندکس در sql server  را بررسی کردیم. در آموزش ایندکس کلاستر چیست قصد داریم ببینیم با ایجاد ایندکس کلاستر برای یک جدول، چه تغییری در ساختار آن رخ می دهد و به چه نحوی رکوردهای جدول در سطوح b-tree توزیع می شوند. در ادامه آموزش ایندکس کلاستر چیست نحوه جستجوی یک مقدار خاص در جدول دارای ایندکس کلاستر را به همراه پیمایش مرحله به مرحله b-tree ایجاد شده را خواهیم دید. در طول آموزش نکاتی پیرامون ایندکس کلاستر نیز مطرح خواهیم کرد.

---

ایندکس کلاستر چیست؟ - معماری

جهت درک بهتر از معماری ایندکس کلاستر و نحوه توزیع رکوردهای جدول در یک b-tree، از مثالی استفاده کرده ایم که بطور کامل قابل پیاده سازی در sql server است. در آموزش ایندکس چیست از یک جدول پرسنلی حاوی اطلاعات کارمندان استفاده کردیم در اینجا نیز از همان جدول با تعداد رکوردهای بیشتر استفاده می کنیم. فرض کنید جدول Employees با فیلدهای id,name,family,nationalcode دارای 16 رکورد است و اندازه فیلدهای جدول را به نحوی انتخاب کرده ایم که هر 4 عدد رکورد در یک صفحه(page) قرار بگیرد. بنابراین جدول ما ساختاری به صورت زیر خواهد داشت:

قصد داریم یک ایندکس کلاستر برای فیلد فامیل(family) ایجاد کنیم. به عبارتی دیگر، فیلد family را به عنوان کلید ایندکس انتخاب می کنیم:

CREATE CLUSTERED INDEX ix1 ON Employess (family);

 با اجرای دستور بالا مراحل زیر انجام می شود:

1. در ابتدا یک کپی از جدول employees ایجاد می شود.

2. رکوردهای موجود در جدول بر اساس فیلد family مرتب می شوند.

3. ساختار B-Tree مطابق آنچه در آموزش B-Tree چیست اشاره شده ایجاد می شود.

4. ساختار جدید ایجاد شده جایگزین جدول اصلی می شود.

مراحل ایجاد b-tree به این صورت است که ابتدا از هر صفحه(page) اولین(کوچکترین) مقدار انتخاب شده و به سطح بعدی(میانی یا intermediate) منتقل می شود و یک اشاره گر به صفحه حاوی این مقدار ایجاد می شود. به عنوان مثال: در Page1 مقدار "احمدی" به سطح میانی منتقل و اشاره گری به Page1 ایجاد می شود:

در ادامه روند ساخت b-tree فامیل "بندامیر" از Page2 به سطح میانی منتقل و اشاره گری به Page2 ایجاد می شود. این روند تا ایجاد سطح ریشه که تنها شامل یک صفحه(page) است ادامه پیدا می کند:

نکته: در ایندکس کلاستر(clustered index) ترتیب منطقی رکوردها با ترتیب فیزیکی آن ها یکسان است.

با توجه به نکته بالا، اگر پس از مرتب سازی جدول، رکورد حاوی فامیل "احمدی" اولین رکورد باشد(ترتیب منطقی)، می بایست بر روی دیسک و در چیدمان فیزیکی هم دقیقاً این رکورد اولین رکورد باشد.(این مورد را در مباحث اینترنالی sql بررسی خواهیم کرد).

اما این سؤال مطرح می شود که اگر پس از ایجاد ایندکس کلاستر، رکوردی با فامیل "ابطحی" در جدول درج شود، طبق نکته بالا بایستی قبل از رکورد حاوی فامیل "احمدی" روی دیسک قرار بگیرد. آیا برای این کار بایستی کلیه رکوردها بر روی دیسک شیفت داده شوند؟

در پاسخ لازم است اشاره کنیم که مدریت این کار با استفاده از Row Offset Array انجام می شود. به عبارت دیگر رکوردها پشت سرهم درج می شوند و این Row Offset Array است که مشخص می کند ترتیب رکوردها به چه شکل است. در مورد مثال بالا، فرض کنید 0x1 در Page1 به اولین رکورد جدول اشاره کند، با درج رکورد حاوی فامیل "ابطحی" از این پس 0x1 به این رکورد اشاره می کند و به عنوان اولین رکورد جدول محسوب می شود و نیازی به جابجایی فیزیکی مابقی رکوردها نیست. پس به جای تغییر محل فیزیکی رکوردها، تنها اشاره گرهای Row Offset Array بروز می شوند:

با توجه به نکته بالا یکی از مزیت های ایندکس کلاستر، سرعت بالای آن در خواندن تمام(scan) و یا بخشی(range scan) از رکوردهای جدول است.

نکته: ایندکس کلاستر می تواند بر روی فیلد حاوی مقادیر تکراری(non unique) ایجاد شود.(در این حالت sql server با اضافه کردن یک ستون مخفی 4 بایتی با نام Uniquifier آن را یونیک می کند)

در ادامه قصد داریم کارمندی با فامیل "پارسایی" را در جدول Employees جستجو کنیم. همانطور که در آموزش B-Tree چیست اشاره کردیم، برای عملیات جستجو از سطح ریشه شروع می کنیم. مراحل مورد نیاز برای یافتن اطلاعات فردی با فامیل "پارسایی" بعد از اجرای کوئری مربوطه را در شکل می بینیم:

در سطح ریشه دو فامیل "احمدی" و "ترک" وجود دارند، با توجه به اینکه فامیل "پارسایی" بعد از "احمدی" و قبل از "ترک" وجود دارد به سمت صفحه ای که "احمدی" به آن اشاره می کند می رویم. در مقایسه بعدی فامیل "پارسایی" بعد از دو فامیل "احمدی" و "بندامیر" قرار دارد بنابراین به سمت صفحه ای که فامیل "بندامیر" به آن اشاره دارد حرکت می کنیم و با توجه به اینکه به سطح برگ(leaf) از b-tree رسیده ایم شروع به جستجو در صفحه مربوطه(Page2) می کنیم. از آنجایی که رکوردهای موجود در این صفحه مرتب شده هستند، عملیات جستجو با سرعت بالایی انجام می شود و در اکثر موارد لازم نیست که همه رکوردهای موجود در صفحه بررسی شوند.

توجه داشته باشید که جستجوی هر فامیل دیگر نیز تنها نیاز به دو مرحله مشابه با مراحل مورد نیاز برای جستجوی فردی با فامیل "پارسایی" خواهد داشت(از مزایای b-tree). در صورتی که جدول Employees فاقد ایندکس کلاستر باشد، برای یافتن اطلاعات هر فامیل می بایستی کل جدول را جستجو کنیم(table scan) 

نکته: در sql server با ایجاد کلید اصلی(primary key) برای یک جدول، بطور پیش فرض یک ایندکس کلاستر(clustered index) بر روی فیلد کلید اصلی ایجاد می شود(این تنظیم قابل تغییر است).

شکل زیر، نمایشی از جدول تک ستونی حاوی اعداد 1 تا 2000 است که بر روی آن ایندکس کلاستر ایجاد کرده ایم. به عنوان تمرین، مراحل مورد نیاز برای یافتن عدد 902 و 1102 را بررسی کنید:

  

• قبلی
• بعدی