Postgresql
@code_craftersPostgreSQL Indexes: B-Tree
در پایگاه داده های رابطه ای Index ها یک ویژگی بسیار مهم هستند که هزینه جستجوی ، جستجوی ما را کاهش میدهند.
What is B-Tree?
به نقل از ویکی پدیا در مورد درخت B:
در علم کامپیوتر، درخت B یک ساختار داده یکپارچه و خود متعادل کننده است که دادهها را مرتب نگهداری میکند و امکان جستجو، دسترسی متوالی، درج و حذف دادهها را با زمان لگاریتمی فراهم میکند.
(نکته : زمان لگاریتمی به معنای رشد آهستهتر یک الگوریتم با افزایش اندازه ورودی است.)
در واقع، یک ساختار داده است که خودش را مرتب میکند. به همین دلیل است که خود متعادل کننده است؛ شکل خود را به تنهایی انتخاب میکند.
درختB یک تعمیم از درخت جستجوی دودویی است که در آن یک گره میتواند بیش از دو فرزند داشته باشد. برخلاف درختهای جستجوی دودویی خود متعادل کننده ، B-درخت بهینهسازی شده است برای سیستمهایی که بلوکهای بزرگی از داده را خوانده و نوشته میکنند. این به این معناست که B-درخت قادر است به صورت کارآمد و با کمترین تلاش، عملیات خواندن و نوشتن در دادههای بزرگ را انجام دهد.
بر عکس درختهای دودویی معمولی، درخت B قادر است تعداد برگ های متفاوت داشته باشد و خودش را متعادل کند. علاوه بر این، پیادهسازیهای آن بهینهسازی شده برای ورود/خروج (I/O) هستند که آن را برای فهرستهای پایگاه داده مناسب میکند.
درختB مثالی خوب از ساختار داده برای حافظه خارجی هستند. آنها به طور معمول در پایگاههای داده و سیستمهای فایل استفاده میشوند.
هماکنون بسیاری از جزئیات در مورد درختهای B وجود دارد. آشنایی با نحوه کارکرد آنها بسیار جالب است، بنابراین بیایید آن را بررسی کنیم.
عملکرد
قبل از شروع به بحث در مورد B-Tree به عنوان یک ساختار داده خود متعادل کننده ، باید اطلاع دهم که درباره B-Tree تئوریهای فراوانی وجود دارد که ما در این بخش به آنها نخواهیم پرداخت کرد. به عنوان مثال، شما ممکن است قبل از ورود به B-Tree، ابتدا به درختهای دودویی، درختهای ۲۳ و درختهای ۲۳۴ آشنا باشید. با این حال، آنچه که در اینجا بحث خواهیم کرد، کافی است تا درک کنید چگونه Index درختB کار میکند.
با این توضیح، به درخت دودویی فکر کنید. در درختهای دودویی، هر گره میتواند حداکثر دو فرزند داشته باشد، به همین دلیل نامش درخت دودویی است.
(عکس درخت دودویی - Binary Tree)
یک درخت B یک درخت است که هر گره میتواند چندین فرزند داشته باشد، به عبارت بهتر، یک درخت B میتواند N فرزند داشته باشد. در حالی که در درختهای جستجوی دودویی هر گره میتواند یک مقدار داشته باشد، در درختهای B مفهوم کلیدها وجود دارد. کلیدها مانند یک لیست از مقادیر هستند که هر یک از گرهها آنها را نگه میدارد.
درختهای B همچنین مفهوم ترتیب را دارند، به این صورت که برای درختهای B، ترتیب 3 به معنی این است که هر گره غیر برگی از درخت میتواند حداکثر 3 فرزند داشته باشد. با این در نظر گرفتن، این بدان معناست که هر گره میتواند دو (3-1) کلید داشته باشد.
گیج کننده است؟ خب، به این فکر کنید: در یک گره غیر برگ با کلیدهای 5 و 10، میتوانید سه گره اضافه کنید:
یک گره با مقادیر کوچکتر از 5
یک گره با مقادیر بین 5 و 10
و یک گره با مقادیر بزرگتر از 10
(مطابق عکس)
مهمترین بحث درمورد درخت B مربوط به توازن آن است. مفهوم درخت B بر پایهی این واقعیت استوار است که هر گره دارای کلیدها است، همانند مثال قبل. روشی که درخت B برای توازن خود به کار میگیرد، بسیار جالب است و کلیدها بخش مهمی را در این عملکرد دارند.
به طور کلی، هر زمان که یک مقدار جدید (یا در مورد ما، یک عدد) اضافه میشود، درخت B مکان مناسب (یا گره) برای قرارگیری آن مقدار را پیدا میکند. به عنوان مثال، اگر میخواهیم عدد 6 را اضافه کنیم، درخت B "از گره ریشه سؤال میکند" که عدد را در کدام گره قرار دهد. "پرسیدن" چیز دیگری نیست جز مقایسه عدد جدید با کلیدهای گره. از آنجا که عدد 6 بزرگتر از 5 است، اما کوچکتر از عدد 10 (که کلیدهای گره ریشه هستند) است، یک گره جدید را در زیر گره ریشه ایجاد میکند.
با استفاده از این مکانیزم، B-Tree همواره مرتب است و جستجوی یک مقدار در آن نسبتاً کم هزینه است. تعدادی پیادهسازی از B-Tree وجود دارد. در حد این نوشته، مفید است بدانید که PostgreSQL از پیادهسازی B-Tree الگوریتم "Lehman and Yao’s high-concurrency B-tree management algorithm" استفاده میکند.
اما این چگونه Index ها در درخت b با PostgreSQLمرتبط است ؟
درخت Bو PostgreSQL
درIndex PostgreSQL به طور ساده، تکثیری از دادههای موجود در ستون(های)ی که Index بر روی آنها قرار دارد هستند. تنها تفاوت در ترتیب دادهها است - تکثیر دادهها مرتب شده است، که به PostgreSQL امکان میدهد به سرعت دادهها را پیدا و بازیابی کند. به عنوان مثال، وقتی در یک جدول جستجویی را انجام میدهید و ستونی که با آن جستجو میکنید Index شده است، Index هزینه کوئری را کاهش میدهد زیرا PostgreSQL در Index جستجو میکند و به راحتی مکان داده را بر روی دیسک پیدا میکند.
ساختار داده B-Tree واقعاً مناسب است، زمانی که به یاد داشته باشید که Index مرتب است. در زیرساخت Index ها درخت B-Tree وجود دارد، اما یکی از اندازههای بزرگ. به دلیل طبیعت ساختار داده B-Tree، هر زمان که یک رکورد جدید به جدول Index گذاری شده اضافه میشود، میداند چگونه تعادل را بازسازی کند و ترتیب رکوردها را در آن حفظ کند.
محدودیت ها
استفاده از Indexها در مواردی که حجم داده بزرگ است، قدرت آنها را به خوبی نشان میدهد. این نیاز به ساخت Indexهایی با اندازه جداول دادههای واقعی بزرگ را ایجاب میکند. اما آیا این واقعا ضروری است؟
در صورتی که با میلیاردها رکورد کار داشته باشیم، این بدان معنی است که Indexها میلیاردها رکورد را به صورت مرتب ذخیره میکنند. این حجم بزرگ داده ممکن است باعث افزایش زمان اجرای دستور INSERT شود. زیرا هر بار که یک رکورد جدید اضافه میشود، Index باید رکورد را در مکان مناسبی قرار دهد تا ترتیب Indexها حفظ شود. برای مدیریت این محدودیت، Index B-Tree از فایلهای صفحهای استفاده میکند که به طور ساده، گرههایی در یک ساختار داده B-Tree بزرگ هستند.
اگرچه هر Index به طور کلی ذخیره میشود، اما مکانیزم صفحهبندی Index دادهها را جدا کرده و باز هم ترتیب را حفظ میکند. به این ترتیب، PostgreSQL بجای بارگذاری کل Index به حافظه برای اضافه کردن یک رکورد، صفحهای را پیدا میکند که رکورد جدید باید در آن قرار گیرد و مقدار Indexشده را در آن ذخیره میکند.
استفاده از Index درختB
با رد کردن جزئیات کارکرد Index درختB، بیایید ببینیم چگونه از آن استفاده کنیم. دستور اضافه کردن یک Index به یک ستون به صورت زیر است:
CREATE INDEX name ON table USING btree (column);
یا، از آنجا که Index، B-Tree Index پیشفرض است، میتوانیم بخش USING دستور را حذف کنیم:
CREATE INDEX name ON table;
این دستور یک BTree Index را بر روی ستون name در جدول table ایجاد خواهد کرد.
جمع بندی
در این آموزش ما یک نگاه کلی به یکی از محبوبترین Indexها در PostgreSQL داشتیم. ما دیدیم که چه تفاوتی بین درخت جستجوی دودویی و B-Tree وجود دارد و چگونه رفتار آنها در PostgreSQL ترجمه میشود.
@code_crafters