B-Tree در SQL SERVER چیست؟ - مقدمه

 اهمیت آشنایی با ساختار B-Tree در SQL SERVER به این دلیل است که ایندکس ها در این ساختار نگهداری می شوند. شناخت ساختار B-Tree در SQL SERVER و نحوه چیدمان و جستجوی اطلاعات در آن، در مباحث مقدماتی تا پیشرفته مرتبط با ایندکس ها(ترتیب کلید ایندکس، کشف ایندکس های غیر کاربردی، شناخت ایندکس هی دارای همپوشانی، ایندکس گذاری صحیح و ...) بسیار تأثیر گذار است. خوشبختانه ما با مفهوم درخت، از قبل آشنایی داریم و در مباحث مختلف از ساختمان داده و طراحی الگوریتم با انواع درخت ها و عملیات مرتبط با آن ها آشنا شده ایم. به طور خلاصه، درخت یک ساختمان داده غیر خطی است که برای عملیاتی مانند جستجو، مرتب سازی، حذف عناصر تکراری و ... از آن ها استفاده می کنیم. البته در مورد B-Tree در SQL SERVER قصد نداریم که با یک دید ساختمان داده ای به آن بپردازیم و مطالب ارائه شده تنها در حد آشنایی با معماری آن و مباحث مورد نیاز در sql server هستند.

در آموزش B-Tree در SQL SERVER چیست در ابتدا تعریفی مختصر و جامع از B-Tree ارائه می دهیم و با بررسی مزایای B-Tree خواهیم دید که به چه دلیلی از بین انواع ساختارهای درخت، تنها از B-Tree در SQL SERVER جهت نگهداری ایندکس ها استفاده می شود. به بررسی معماری B-Tree می پردازیم و در ادامه یک ابزار جهت آشنایی بیشتر با B-Tree و انواع عملیات در آن معرفی خواهد شد(صرفاً جهت مطالعه علاقمندان). در پایان با ارائه یک مثال عملی، نحوه ذخیره سازی اطلاعات در B-Tree و جستجوی یک مقدار خاص در این ساختار را با هم خواهیم دید.

---

B-Tree در SQL SERVER چیست؟ - معرفی

در ابتدا اگر بخواهبم یک تعریف مختصر و جامع برای B-Tree ارائه دهیم به این صورت است که:

"B-Tree یک درخت متوازنِ Disk Based چند سطحی است "

نکته: B-Tree به معنای درخت متعادل(Balanced Tree) است و نه درخت دودویی(Binary Tree) و یا درخت جستجوی دودویی(BST-Binary Search Tree).

قبل از ادامه مطالب، لازم است یک آشنایی ابتدایی با معماری B-Tree داشته باشیم. همانطور که در شکل زیر مشخص است یک B-Tree از سه سطح ریشه(Root)، میانی(Intermediate) و برگ(Leaf) تشکیل شده است. سطح برگ حاوی اطلاعات واقعی ما هستند. به عبارتی دیگر می توان اینگونه فرض کرد که جدول ما، به طور کامل در سطح برگ(Leaf) توزیع شده است. سطوح میانی و ریشه به عنوان یک کمک جهت انجام عملیات در این ساختار اضافه شده اند(در ادامه با ذکر مثال، به جزئیات بیشتری اشاره می کنیم):

در ادامه به توضیح هر کدام از سه قسمت اصلی مشخص شده در تعریف B-Tree  می پرداذیم:

1. B-Tree در SQL SERVER یک درخت متوازن است:

 یکی از مهمترین ویژگی های درخت B-Tree متوازن بودن آن محسوب می شود به این معنا که کلیه نودهای موجود در سطح برگ(leaf) دارای فاصله(عمق) یکسانی تا ریشه هستند. به دلیل اینکه در هر عملیاتی تعداد مراجعه به دیسک متناسب با تعداد سطوح است. بنابراین زمانی که همه نودهای سطح برگ دارای عمق یکسانی باشند، انجام عملیات در هر نود هزینه یکسانی با سایر نودها دارد.

نکته: هر نود موجود در B-Tree یک صفحه(page) با ظرفیت 8KB است.

2. B-Tree در SQL SERVER یک درخت Disk Based است:

همانطور که در نکته بالا اشاره شد، هر نود موجود در B-Tree، یک page بر روی دیسک است و اشاره گر بین pageها حاوی آدرس pageهای دیگر روی دیسک هستند. از B-Tree در Storage و وسایل ذخیره سازی ثانویه نیز استفاده می شود.

3. B-Tree در SQL SERVER یک درخت چند سطحی است:

در قسمت ابتدایی از این بخش دیدیم که یک B-Tree از سطوح ریشه، میانی و برگ تشکیل شده است. نکته ای که در مورد سطوح درخت B-Tree وجود دارد این است که رشد یا زیاد شدن این سطوح به کندی انجام می شود. به عنوان مثال جهت نگهداری اطلاعات چند میلیونی در یک B-Tree، سطح میانی تنها دارای دو یا سه سطح است و به ندرت یک B-Tree با شش سطح میانی ایجاد می شود. در واقع با توجه به وابستگی هزینه عملیات به تعداد سطوح،کم بودن تعداد آن از نقاط قوت B-Tree محسوب می شود.

---

B-Tree در SQL SERVER چیست؟ - درج و جستجو

جهت درج اطلاعات در یک B-Tree ابتدا از سطح برگ شروع می کنیم. همانطور که اشاره کردیم سطح برگ این درخت، از pageهایی با ظرفیت 8 کیلوبایت تشکیل شده است. به عبارتی در اولین مرحله ایجاد B-Tree اطلاعات را در فضاهایی 8 کیلوبایتی توزیع می کنیم. در تصویر زیر، اعداد 1 تا 2000 را در صفحات سطح برگ توزیع کرده ایم:

در مرحله بعدی نوبت به ایجاد سطح میانی(Intermediate Level) می رسد. برای ایجاد سطح میانی، کوچکترین عدد از هر صفحه موجود در سطح برگ، به صفحه موجود در سطح میانی منتقل می شود و یک اشاره گر به صفحه حاوی این عدد ایجاد می گردد:

مرحله قبل را تا جایی ادامه می دهیم که در سطح جدید بالایی، تنها یک نود(page) ایجاد شود که به آن سطح ریشه گفته می شود:

به این ترتیب ما یک معماری B-Tree در SQL SERVER جهت ذخیره سازی اطلاعات ایندکس ایجاد کرده ایم. به عبارتی دیگر، زمانی که برای یک جدول ایندکس کلاستر ایجاد می کنید، sql server در ابتدا یک کپی از جدول اصلی ما ایجاد و ساختار بالا را برای آن ایجاد می کند و در پایان، این ساختار جدید را با جدول اصلی جایگزین می کند.(جزئیات بیشتر در این رابطه در آموزش معماری ایندکس کلاستر و نان کلاستر ارائه خواهد شد).

در واقع می تواینم اینگونه تصور کنیم که B-Tree از نظر شکل ظاهری مانند یک درخت وارونه شده است که ریشه درخت در بالا قرار دارد و میوه های آن که مانند اطلاعات ما هستند در شاخه ها(سطح برگ) قرار گرفته اند:

و اما برای جستجو کردن در یک درخت B-Tree در SQL SERVER برعکس مراحل ایجاد آن، از سطح ریشه عملیات جستجو را شروع می کنیم و با مقایسه هایی که در هر مرحله انجام می دهیم نهایتاً به داده مورد نظر می رسیم. به عنوان مثال فرض کنید قصد داریم در درخت B-Tree ایجاد شده در مرحله قبل، عدد 100 را جستجو کنیم. مراحل جستجو به این صورت است:

در ابتدا عدد 100 را با مقادیر موجود در نود سطح ریشه(همیشه یک نود در سطح ریشه قرار دارد) مقایسه می کنیم. در مثال ما، عدد 100 از 1 بزرگتر و از 1001 کوچکتر است در این حالت به سمت چپ درخت و سطح میانی حرکت می کنیم(در صورت بزرگتر بودن، به سمت راست حرکت می کنیم) مجدداً عمل مقایسه را در این نود انجام می دهیم و می بینیم که عدد 100 از 1 بزرگتر و از 101 کوچکتر است پس باز هم به سمت چپ درخت و یک سطح پایین تر حرکت می کنیم. با توجه به اینکه به سطح ریشه رسیده ایم و داده های اصلی ما در این سطح قرار گرفته اند، در نود مربوطه جستجو می کنیم و عدد 100 را بدست می آوریم(جستجوی هر عدد دیگری نیز، دارای مراحل و هزینه یکسانی می باشد):

می تواینم اینگونه تصور کنیم که عملیات جستجوی B-Tree در SQL SERVER از نظر شکل ظاهری مانند مراحلی است که برای چیدن یک میوه از درخت دنبال می کنیم! در ابتدا میوه مورد نظر را انتخاب می کنیم و از ریشه(ساقه) درخت بالا می رویم و با رسیدن به هر شاخه، در جهت میوه مورد نظر حرکت را ادامه می دهیم:

در صورت علاقه به یادگیری مطالب بیشتر در مورد B-Tree می توانید از شبیه ساز B-Tree simulator استفاده کنید(کافیست این عبارت را در گوگل جستجو کنید).

---

 B-Tree در SQL SERVER چیست؟ - جمع بندی

در این آموزش با تعریف و معماری B-Tree، نحوه ذخیره سازی و جستجوی اطلاعات در آن آشنا شدیم. به عنوان یک جمع بندی می توانیم به این نکته اشاره کنیم که مهمترین دلایل استفاده از B-Tree در SQL SERVER عبارتند از:

1. انجام اکثر عملیات در B-Tree، نسبت یه سایر درخت هایی که می شناسیم سریعتر است.

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

3. مزیت مهم دیگر پیمایش سریع B-Tree است. به دلیل وجود ارتباط(اشاره گر) بین نودها(صفحات) در این ساختار، پیمایش آن به سرعت انجام می شود.

4. رشد B-Tree به کندی انجام می شود به نحوی که یک B-Tree با شش سطح میانی به ندرت دیده می شود(هزینه عملیات، متناسب با تعداد سطوح است).

 

• قبلی
• بعدی