درختان B در مقابل درختان B+؛ چرا یک ساختار اندیس‌گذاری، عملیات ورودی/خروجی دیسک را برای کوئری‌های پایگاه داده به حداقل می‌رساند

هنگامی که گروه توسعه جهانی PostgreSQL نسخه ۱۳ را در سپتامبر ۲۰۲۰ منتشر کرد، موتور پایگاه داده با معرفی قابلیت حذف تکرار (deduplication) در درخت B، نحوه مدیریت ورودی‌های اندیس تکراری را به طور اساسی تغییر داد. به جای ذخیره چندین باره کلیدهای یکسان، سیستم شروع به ادغام آن‌ها در یک لیست ارسال واحد کرد. این بهینه‌سازی، فضای ذخیره‌سازی اندیس‌ها را کاهش داد، اما بر اساس یک ساختار داده بنیادی بنا شده بود که عملکرد تقریباً تمام پایگاه‌های داده رابطه‌ای مدرن را تعیین می‌کند: درخت B+.[3]

در حالی که بازاریابی پایگاه داده مدرن اغلب «بهینه‌سازی کوئری مبتنی بر هوش مصنوعی» یا «مقیاس‌پذیری بدون طرح‌واره» را تبلیغ می‌کند، قابلیت واقعی که ورودی/خروجی دیسک (I/O) را در سیستم‌های تولیدی مانند MySQL InnoDB، Oracle و SQLite به حداقل می‌رساند، همچنان درخت B+ است. تمایز بین درخت B استاندارد و نوع B+ آن صرفاً آکادمیک نیست. این تمایز نشان‌دهنده یک موازنه مهندسی خاص است که برای حل تأخیر فیزیکی خواندن داده از دیسک ذخیره‌سازی طراحی شده است.[1]

برای درک اینکه چرا درخت B+ غالب است، ابتدا باید به محدودیت‌های فیزیکی ذخیره‌سازی پایگاه داده نگاه کرد. یک رویکرد ساده‌لوحانه برای پایگاه داده این است که رکوردها را به صورت متوالی در یک فایل بسته‌بندی کند. تیم مهندسی Fly.io اشاره می‌کند: «با این حال، هیچ راهی برای درج یا به‌روزرسانی سطرها در وسط فایل بدون جابجایی و بازنویسی تمام بایت‌های پس از سطر جدید وجود ندارد.»[4]

در عوض، پایگاه‌های داده سطرها را در قطعاتی با اندازه ثابت به نام «صفحه» (page) گروه‌بندی می‌کنند. اندازه استاندارد صفحه ۴ کیلوبایت است که با اندازه بلوک مورد استفاده معمول سیستم‌های عامل و سیستم‌های فایل هم‌تراز است. هم‌تراز نگه داشتن همه چیز با این مرز ۴ کیلوبایتی، تعداد واکشی‌های صفحه مورد نیاز از دیسک را کاهش می‌دهد. از آنجایی که ورودی/خروجی دیسک کندترین عملیات در معماری پایگاه داده است، محدود کردن واکشی‌های صفحه منجر به یک مزیت عملکردی بزرگ می‌شود.[4]

درخت B استاندارد، که توسط رودلف بایر (Rudolf Bayer) و ادوارد مک‌کریت (Edward McCreight) در سال ۱۹۷۰ اختراع شد، برای پیمایش کارآمد این صفحات طراحی شده بود. طبق تعریف دانشنامه‌ای آن: «در علوم کامپیوتر، درخت B یک ساختار داده درختی خودمتعادل‌ساز است که داده‌های مرتب‌شده را حفظ می‌کند و امکان جستجو، دسترسی متوالی، درج و حذف را در زمان لگاریتمی فراهم می‌سازد.»[2]

در یک درخت B استاندارد، هر گره در درخت می‌تواند هم کلیدهای مسیریابی و هم رکوردهای داده واقعی (یا اشاره‌گرهایی به داده‌ها) را ذخیره کند. اگر یک کوئری به دنبال یک شناسه کاربری خاص باشد، پایگاه داده درخت را از گره ریشه به سمت پایین و از طریق گره‌های داخلی پیمایش می‌کند. اگر رکورد مورد نظر به طور اتفاقی در یک گره داخلی ذخیره شده باشد، جستجو زودتر خاتمه می‌یابد و در یک خوانش دیسک صرفه‌جویی می‌شود.[1]

با این حال، ذخیره داده در داخل گره‌های داخلی یک جریمه ساختاری جدی ایجاد می‌کند. از آنجایی که یک صفحه ۴ کیلوبایتی فضای محدودی دارد، پر کردن آن با رکوردهای داده حجیم به این معنی است که کلیدهای مسیریابی کمتری می‌توانند در همان صفحه جای بگیرند. کلیدهای کمتر در هر گره، «عامل انشعاب» (branching factor) درخت را کاهش می‌دهد و درخت را مجبور می‌کند بلندتر شود. یک درخت بلندتر نیاز به پرش‌های عمودی بیشتری برای رسیدن به پایین دارد و هر پرش نشان‌دهنده یک عملیات ورودی/خروجی دیسک جداگانه است.

درخت B+ این گلوگاه هندسی را با جداسازی دقیق پیمایش از ذخیره‌سازی حل می‌کند. در درخت B+، گره‌های داخلی تنها کلیدهای مسیریابی را ذخیره می‌کنند، در حالی که تمام رکوردهای داده واقعی به گره‌های برگ در انتهای ساختار منتقل می‌شوند.

با حذف داده‌ها از گره‌های داخلی، یک درخت B+ می‌تواند صدها کلید مسیریابی را در یک صفحه ۴ کیلوبایتی جای دهد. به عنوان مثال، اگر یک ورودی صفحه داخلی حدود ۸ بایت برای ذخیره یک کلید اصلی فرزند و شماره صفحه آن نیاز داشته باشد، یک صفحه داخلی ۴ کیلوبایتی می‌تواند تقریباً ۵۰۰ ورودی را در خود نگه دارد.[4]

این عامل انشعاب بالا، درخت را از نظر ریاضی مسطح می‌کند. یک درخت B+ با عامل انشعاب ۵۰۰ می‌تواند ۱۲۵ میلیون رکورد را تنها در سه سطح (۵۰۰ × ۵۰۰ × ۵۰۰) اندیس‌گذاری کند. در نتیجه، هر رکوردی در یک جدول ۱۲۵ میلیون ردیفی را می‌توان با حداکثر سه بار خواندن دیسک بازیابی کرد. در عمل، گره‌های ریشه و داخلی سطح اول اغلب در حافظه RAM کش می‌شوند، به این معنی که ممکن است جستجو تنها به یک خوانش فیزیکی دیسک نیاز داشته باشد.[5]

مزیت اصلی دوم درخت B+، نحوه مدیریت کوئری‌های محدوده‌ای (range queries) است. در یک درخت B استاندارد، داده‌ها در سطوح مختلف سلسله مراتب پراکنده شده‌اند. اگر یک کوئری تمام رکوردها بین شناسه ۱۰۰ و شناسه ۵۰۰ را درخواست کند، پایگاه داده باید یک پیمایش درون‌ترتیبی (in-order traversal) انجام دهد و مکرراً از شاخه‌های درخت بالا و پایین برود تا رکوردهای متوالی را پیدا کند.[1]

درخت B+ این پیمایش عمودی را حذف می‌کند. از آنجایی که تمام داده‌ها در سطح برگ قرار دارند، گره‌های برگ در یک لیست پیوندی دوگانه (doubly-linked list) به هم متصل شده‌اند. هنگامی که پایگاه داده به گره برگی که حاوی شناسه ۱۰۰ است می‌رسد، به سادگی به صورت افقی در طول لیست پیوندی حرکت می‌کند تا رکوردهای بعدی را بخواند تا زمانی که به شناسه ۵۰۰ برسد.

این اسکن افقی برای خوانش‌های متوالی دیسک بسیار بهینه شده است. پایگاه داده می‌تواند صفحات مجاور را از قبل از دیسک واکشی کند و عملیاتی مانند `SELECT * FROM users WHERE age > 21` یا `ORDER BY timestamp DESC` را به طرز چشمگیری سرعت بخشد.[1]

معماری PostgreSQL یک مثال واضح از این پیاده‌سازی ارائه می‌دهد. مستندات رسمی بیان می‌کند: «اندیس‌های درخت B در PostgreSQL ساختارهای درختی چند سطحی هستند که در آن هر سطح از درخت می‌تواند به عنوان یک لیست پیوندی دوگانه از صفحات استفاده شود.» «به طور معمول، بیش از ۹۹ درصد از کل صفحات، صفحات برگ هستند.»[3]

این ساختار به PostgreSQL اجازه می‌دهد تا کوئری‌های پیچیده را به طور کارآمد مدیریت کند. هنگامی که کاربر یک کوئری با عملگر `BETWEEN` یا `IN` اجرا می‌کند، برنامه‌ریز کوئری (query planner) به اندیس درخت B متکی است تا مرز شروع را پیدا کند و سپس به صورت افقی اسکن را انجام دهد.[3]

PostgreSQL همچنین محدودیت‌های اندازه سخت‌گیرانه‌ای را برای حفظ کارایی درخت اعمال می‌کند. پایگاه داده حکم می‌کند که یک ورودی اندیس نمی‌تواند تقریباً از یک سوم یک صفحه تجاوز کند. این تضمین می‌کند که حتی در بدترین حالت، هر گره داخلی حداقل عامل انشعاب سه را حفظ کند و از تبدیل شدن درخت به یک لیست پیوندی جلوگیری شود.[3]

موازنه کارایی خواندن درخت B+، سربار (overhead) جزئی در طول عملیات نوشتن است. از آنجایی که تمام داده‌ها باید در گره‌های برگ قرار گیرند، درج یک رکورد جدید می‌تواند باعث سرریز شدن صفحه برگ شود. هنگامی که یک صفحه از ظرفیت ۴ کیلوبایتی خود فراتر می‌رود، پایگاه داده باید یک «تقسیم صفحه» (page split) انجام دهد، رکوردها را بین دو صفحه جدید تقسیم کند و گره والد را با کلید مسیریابی جدید به‌روزرسانی کند.

اگر گره والد نیز پر باشد، تقسیم به صورت بازگشتی به سمت بالا آبشاری می‌شود. در موارد نادر، این آبشار به ریشه می‌رسد و ریشه را مجبور به تقسیم و اضافه کردن یک سطح جدید به کل درخت می‌کند. با وجود این جریمه نوشتن، اکثریت قریب به اتفاق حجم کاری پایگاه داده، خوانش محور (read-heavy) هستند، که بهینه‌سازی خواندن درخت B+ را به مصالحه مهندسی صحیح تبدیل می‌کند.

فروشندگان پایگاه داده مدرن اغلب موتورهای ذخیره‌سازی انقلابی جدیدی را اعلام می‌کنند، اما به ندرت جایگزین کاملی برای این ساختار ارائه می‌دهند. به عنوان مثال، ویژگی حذف تکرار که در PostgreSQL 13 معرفی شد، به عنوان یک جهش عملکردی بزرگ بازاریابی شد، اما به طور خاص صفحات برگ درخت B+ موجود را هدف قرار می‌دهد و کلیدهای تکراری را برای به تأخیر انداختن تقسیم صفحات ادغام می‌کند، نه اینکه چرخ را از نو اختراع کند.[3]

فراگیری درخت B+ بر یک واقعیت بنیادی مهندسی سیستم‌ها تأکید می‌کند: محدودیت‌های سخت‌افزاری، طراحی نرم‌افزار را دیکته می‌کنند. تا زمانی که خواندن از دیسک ذخیره‌سازی به مراتب کندتر از خواندن از حافظه سیلیکونی باشد، مسطح کردن فضای جستجو هدف اصلی معماری پایگاه داده باقی خواهد ماند. مرز بعدی برای موتورهای اندیس‌گذاری، تطبیق این ساختارها برای درایوهای حافظه غیرفرار اکسپرس (NVMe) است، جایی که شکاف تأخیر بین RAM و ذخیره‌سازی در حال کاهش است و به طور بالقوه تعادل ریاضی درخت B+ را یک بار دیگر تغییر می‌دهد.[1]