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

مقدمه

در اینجا به دنبال آن نیستیم که بگوییم چرا از ایندکس‌ها در SQL Server استفاده می‌کنیم و یا چه کاربردی دارند. زیرا با یک جستجوی ساده در اینترنت می‌توانید متوجه شوید که یک ایندکس مناسب روی یک جدول با حجم چند گیگابایتی چگونه می‌تواند عملکرد واکشی دیتا را بهبود ببخشد؟ بنابراین در این مقاله به دنبال آن هستیم تا نحوه ایجاد ایندکس‌ها را درک کنیم و بیاموزیم که DBMS مربوط به 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 را در خود نگهداری می‌کند.
• ساختار این درخت بصورت سلسله مراتبی می‌باشد.

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

نحوه تشکیل درخت B-Tree بدین صورت است که در ابتدا Sql Server تعداد کل Page‌های مورد استفاده در یک جدول را مورد بررسی قرار می‌دهد (از طریق IAM Page) و با توجه به آن شروع به تشکیل درخت می‌کند. بدین صورت که هر چه تعداد Page‌ها (رکوردهای جدول) بیشتر باشد به مراتب تعداد سطوح میانی این جدول نیز می‌تواند بیشتر شود. سطوح میانی تا زمانی تشکیل می‌شوند و افزایش می‌یابند که یک نود تنها (ریشه) باقی بماند و تمام داده‌ها در برگ جای گیرند. شکل زیر ساختار یک جدول B را نشان می‌دهد.با توجه به شکل بالا مشاهده می‌شود این درخت ازیک گره ریشه و یک سطح میانی تشکیل شده است و تمامی برگ‌ها در یک سطر قرار دارند و دارای اطلاعات رکوردها هستند (در حالت 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 هیچ ترتیبی در چینش رکوردها ندارد.
با استفاده از دستور زیر می‌توان مشخصات مربوط به 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')

با استفاده از دستور زیر نیز می‌توان تعداد 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

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