بررسی نحوه تشکیل درخت B-Tree در SQL Server

بررسی نحوه تشکیل درخت B-Tree در SQL Server

نوشته شده توسط: ایمان باقری
تاریخ انتشار: ۲۰ بهمن ۱۳۹۹
آخرین بروزرسانی: 13 آذر 1403
زمان مطالعه: 18 دقیقه
۳
(۶)

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

درخت B-Tree در SQL Server

جدول Heap جدولی است که فاقد ایندکس کلاستر می‌باشد. بنابراین ترتیبی در چینش رکوردها در درون Page‌ ها وجود ندارد. با توجه این تعریف اولین نکته‌ای که می توان دریافت آن است که وجود ایندکس کلاستر در یک جدول باعث می‌شود رکوردهای آن جدول دارای چینش فیزیکی مرتب شده باشند

ویژگی‌های درخت B-Tree در SQL Server

یک ایندکس از تعدادی Page تشکیل می‌شود که به هر کدام از این Page‌ ها یک Node گفته می‌شود. این Node‌ها بصورت ساختار یک درخت B-Tree ذخیره می‌شوند. یک درخت B-Tree از ویژگی‌های زیر تشکیل شده است:

  • هر Node در آن در حقیقت یک Page می‌باشد.
  • فقط دارای یک Node ریشه می‌باشد.
  • دارای یک یا چند سطح میانی است که به آن Intermediate level گفته می‌شود.
  • دارای سطح برگ (Leaf level) می‌باشد که برای ایندکس کلاستر حکم Data Page را دارد اما برای ایندکس Non-Cluster تنها آدرس محل Data Page را در خود نگهداری می‌کند.
  • ساختار این درخت بصورت سلسله مراتبی می‌باشد.

دوره Performance Tuning در SQL Server

تشکیل درخت B-Tree در SQL Server

نحوه تشکیل درخت B-Tree بدین صورت است که در ابتدا SQL Server تعداد کل Page‌ های مورد استفاده در یک جدول را مورد بررسی قرار می‌دهد (از طریق IAM Page) و با توجه به آن شروع به تشکیل درخت می‌کند. بدین صورت که هر چه تعداد Page‌ها (رکوردهای جدول) بیشتر باشد به مراتب تعداد سطوح میانی این جدول نیز می‌تواند بیشتر شود. سطوح میانی تا زمانی تشکیل می‌شوند و افزایش می‌یابند که یک نود تنها (ریشه) باقی بماند و تمام داده‌ها در برگ جای گیرند. شکل زیر ساختار یک جدول B را نشان می‌دهد.تشکیل درخت B-Treeبا توجه به شکل بالا مشاهده می‌شود این درخت ازیک گره ریشه و یک سطح میانی تشکیل شده است و تمامی برگ‌ها در یک سطر قرار دارند و دارای اطلاعات رکوردها هستند (در حالت Cluster index) هر گره شامل کوچکترین مقدار کلید (با توجه به کلید Index) و آدرس Page سطح بعدی مربوطه می‌شود. Sql Server تشکیل درخت را تا جایی ادامه می‌دهد که به آدرس نهایی و گره برگ دست یابد.

به‌عنوان‌مثال یک جدول با نام  SalesProduct تشکیل می‌دهیم و برای آن یک Cluster index تشکیل می‌دهیم.

CREATE TABLE [dbo].[SalesProduct])
  ,[ProductID] [int] NOT NULL
  ,[DueDateId] [int] NOT NULL
  ,[CurrencyID] [int] NOT NULL
  ,[OrderQuantity] [smallint] NULL
  [UnitPrice] [money] NULL
)
GO
insert into [dbo].[SalesProduct])
  ,[ProductID]
  ,[DueDateId]
  ,[CurrencyID]
  ,[OrderQuantity]
  [UnitPrice]
(
values
(floor(RAND()*(300-100)+100) ,20210101	,۲۰	,floor(RAND()*(50-1))	,(RAND()*(500000-100000)+10000) )
 go 100000
CREATE CLUSTERED INDEX [ClusteredIndex-ProductID1] ON [dbo].[SalesProduct]
)
  [ProductID] ASC
(

پس از اجرای دستور فوق Sql Server جدول را تشکیل و ایندکس مورد نظر را با کلید ProductID ایجاد می‌نماید. حالا اگر به ExecutionPlan مربوط به کوئری زیر توجه کنید می‌بینید SQL Server با توجه به کلید Index اقدام به یافتن مقدار مورد درخواست می‌کند. این کار بصورت Clustered index Seek انجام می‌گیرد. پیشنهاد میکنیم برای درک بهتر مفاهیم دوره کوئری نویسی پیشرفته را مطالعه کنید.

SELECT [ProductID],[DueDateId],[CurrencyID] ,[OrderQuantity] ,[UnitPrice]
FROM  [SalesProduct]
where productid=215

شکل زیر کوئری مورد نظر را در دو حالت جدول Heap و Cluster index نشان می‌دهد. مشاهده می‌شود هزینه جدول ۹۹درصد می‌باشد. همچنین جدول دارای Cluster index مرتب شده می‌باشد در صورتی که جدول Heap هیچ ترتیبی در چینش رکوردها ندارد.تشکیل درخت B-Tree
با استفاده از دستور زیر می‌توان مشخصات مربوط به Page‌های تخصیص یافته و تعداد سطوح تشکیل شده برای B-Tree را دریافت نمود.

SELECT min_record_size_in_bytes,max_record_size_in_bytes,avg_record_size_in_bytes,page_count,index_depth,index_level
FROM sys.dm_db_index_physical_stats
 ;(DB_ID(N'DB_Name'), OBJECT_ID(N'SalesProduct'), NULL, NULL , 'DETAILED')

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

Use DB_NAME
SELECT
DB_NAME(PA.database_id) [DataBase], OBJECT_NAME(PA.object_id) [Table], SI.Name [Index],
    is_allocated, allocated_page_file_id [file_id], allocated_page_page_id [page_id], page_type_desc, page_level, previous_page_page_id [previous_page_id],
    next_page_page_id [next_page_id]
FROM   sys.dm_db_database_page_allocations
    (DB_ID(' DB_Name'), OBJECT_ID('SalesProduct'),NULL, NULL, 'DETAILED')PA
         LEFT OUTER JOIN sys.indexes SI  ON SI.object_id = PA.object_id
                   AND SI.index_id = PA.index_id
ORDER BY page_level DESC,  is_allocated DESC, previous_page_page_id

تشکیل درخت B-Treeگره ریشه در سطح ۲ قرار گرفته است. همچنین Next_Page و Previous_Page برای آن وجود ندارد. همچنین در سطح صفر برگ‌ها قرار گرفته‌اند که همان Data Page‌ ها هستند. بنابراین می‌توان دریافت B-Tree ایجاد شده برای جدول SalesProduct دارای سه سطح می‌باشد.

سخن پایانی

درخت B-Tree در SQL Server، هر ایندکس از تعدادی Page تشکیل شده که به هر کدام از اینها یک Node گفته می‌شود. در این مقاله به صورت گام به گام ساخت درخت B-Tree در SQL Server از ایندکس های Page آموزش داده شد. ما در نیک آموز منتظر نظرات ارزشمند شما درباره این مقاله هستیم.

چه رتبه ای می‌دهید؟

میانگین ۳ / ۵. از مجموع ۶

اولین نفر باش

title sign
دانلود مقاله
بررسی نحوه تشکیل درخت B-Tree در SQL Server
فرمت PDF
4 صفحه
حجم 1 مگابایت
دانلود مقاله
title sign
معرفی نویسنده
ایمان باقری
مقالات
6 مقاله توسط این نویسنده
محصولات
14 دوره توسط این نویسنده
ایمان باقری

ایمان باقری بیش از 10 سال است که بصورت حرفه‌ای با SQL Server کار می‌کند. و مدرس دوره‌های SQL Server در نیک آموز می‌باشد.

  • مشاور و متخصص در هوش تجاری و SQL Server
  • توسعه دهنده داشبورد های مدیریتی شرکت سام سرویس (سامسونگ)
  • طراحی و توسعه سیستم انبار داده حوزه بانکی
  • طراحی و پیاده سازی سیستم های تحلیلی و گزارشی
title sign
دیدگاه کاربران

هر روز یک ایمیل، هر روز یک درس
آموزش SQL Server بصورت رایگان
همین حالا فرم زیر را تکمیل کنید
دانلود رایگان جلسه اول
نیک آموز علاوه بر آموزش، پروژه‌های بزرگ در حوزه هوش تجاری و دیتا انجام می‌دهد.
close-link
close-image