درخت بی‌پلاس

B+ tree
گونه	درختی (ساختار اطلاعات)
زمان اجرای الگوریتم بر پایه نماد O بزرگ
الگوریتم میانگین بدترین حالت فضا O(n) O(n) جستجو O(log n) O(log n) درج O(log n) O(log n) حذف O(log n) O(log n)

درخت بی برای اولین بار در مقاله 《Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173–189 (1972) 》به وسیله‌ی رودلف بایر و ادوارد م. مک کریت توصیف شد. هیچ مقاله تنهایی وجود ندارد که مبحث درخت بی پلاس را معرفی کند. درعوض، مفهوم نگهداری همه داده‌ها در برگ‌ها به‌طور مکرر به عنوان یک متغیر جذاب پرورش یافته‌است. یک برآورد اولیه از درختان بی، که درختان بی پلاس را هم دربر می‌گیرد در دوگلاس کومر دیده می‌شود:《"The Ubiquitous B-Tree", ACM Computing Surveys 11(2): 121–137 (1979)》. کومر ذکر کرده که درخت بی پلاس در نرم‌افزار دسترسی به داده‌های 《VSAM 》متعلق به شرکت 《IBM》 مورد استفاده قرار گرفته و او به یک مقاله منتشر شده 《IBM》 در سال ۱۹۷۳ اشاره می‌کند.

درخت بی پلاس

در علوم کامپیوتر، یک درخت بی پلاس درختی است که داده مرتب شده را به شکلی نشان می‌دهد که درج، دریافت و حذف اطلاعات که هر کدام با یک کلید مشخص می‌شود، کارآمد باشد. این یک حافظه ذخیره‌ای پویا و چند سطحی است، با پیوندهای بیشینه و کمینه بین تعداد کلیدهای هر خانه ذخیره‌ای (عموماً به آن‌ها گره یا بلوک گفته می‌شود). در یک درخت بی پلاس، بر خلاف یک درخت بی ماینس، تمام رکوردها در سطح برگ‌های درخت ذخیره می‌شوند؛ تنها کلیدها در گره داخلی ذخیره می‌شوند.

ارزش اولیهٔ یک درخت بی پلاس در ذخیره کردن داده‌های آن با مفهوم یک ذخیره‌سازی بلوک-محور به‌طور خاص سیستم فایل‌ها برای بازیابی کار آمد است. این عمدتاً به دلیل این است که بر خلاف درخت جستجوی دودویی، درختان بی پلاس گنجایش خروجی زیادی دارند (به‌طور نمونه‌ای از مرتبه ۱۰۰ یا بیشتر)، که تعداد عملیات ورودی/خروجی مورد نیاز برای پیدا کردن یک عنصر در درخت را کاهش می‌دهد.

سیستم فایل هایJFS, NTFS, NSS, Reiser FS, JFS همگی از این نوع درخت برای ذخیره‌سازی (فهرست سازی) اطلاعات دربارهٔ داده‌ها استفاده می‌کنند. سیستم‌های مدیریتی رابطه‌ای پایگاه‌های داده مثل IBM DB2، Informix, Microsoft SQL Server, Oracle 8، Sybase ASE, PostgerSQL, Firebird, MySQL واس‌کیوال لایت این نوع درخت را برای جدول خانه‌های حافظه پشتیبانی می‌کنند. سیستم‌های مدیریتی کلید-مقدار مانند Tokyo Tyrant و Tokyo Cabinet این نوع درخت را برای دسترسی به داده‌ها تأیید می‌کند. InfinityDB یک درخت ب متقارن است.

نکته‌ها

درجه یا عامل شاخه‌ای شدن یک درخت بی پلاس با مقدار b، گنجایش گره‌ها (تعداد فرزندان گره‌ها) را برای گره‌های داخلی درخت محاسبه می‌کند. تعداد فرزندان واقعی برای هر گره، که آن را با m مشخص می‌کنند، برای گره‌های داخلی محدود می‌شود در نتیجه ${\displaystyle \lceil {\frac {b}{2}}\rceil \leq \ m\leq \ b}$. ریشه درخت یک استثنا است: تنها مجاز است که دو فرزند داشته باشد. برای مثال: اگر درجهٔ یک درخت بی پلاس ۷ باشد، هر گره داخلی (به جز ریشه) ممکن است بین ۴ تا ۷ فرزند داشته باشد؛ برگ‌ها فرزندی ندارند (بر اساس تعریف)، ولی محدود شده‌اند در نتیجه تعداد کلیدها باید حداقل ${\displaystyle \lceil {\frac {b-1}{2}}\rceil }$ و حد اکثر b-1 باشد. در حالتی که یک درخت بی پلاس تقریباً خالی است، تنها یک گره دارد، که یک برگ است. (ریشه نیز در این مورد یک برگ تنها است). این گره مجاز است که در صورت نیاز فقط یک کلید داشته باشد.

جستجو

الگوریتم انجام دادن یک جستجو برای یک رکورد r اشاره گرها را تا فرزند درست هر گره دنبال می‌کند تا زمانی که به یک برگ برسد. پس از آن، برگ پیمایش می‌شود تا زمانی که رکورد صحیح یافت شود (یا تا زمانی که شکست بخورد).

 function search(record r)
 u:= root
 while (u is not a leaf) do
 choose the correct pointer in the node
 move to the first node following the pointer
 u:= current node
 scan u for r

این سودوکد فرض کرده که هیچ تکراری مجاز نیست.

جستجو خیلی سریع است.

درج

• یک جستجو انجام بده تا مشخص شود که رکورد جدید در کدام سطل باید برود
• اگر سطل پر نبود، رکورد را اضافه کن.
• در غیر این صورت سطل را دو قسمت کن.
• یک برگ جدید ایجاد کن و نیمی از عناصر سطل را به سطل جدید منتقل کن
• کوچک‌ترین کلید برگ جدید را درج کن و آن را به گره پدر اشاره بده.
• اگر گره پدر پر است، آن را هم دو قسمت کن
• حال کلید میانی را به گره پدر اضافه کن
• تا زمانی که به پدری نرسیده که نیازی به افراز ندارد ادامه بده
• اگر ریشه افراز شود، یک ریشه جدید ایجاد کن که یک کلید و دو اشاره گر داشته باشد.
• درخت‌های B در ریشه رشد می‌کنند نه در برگ‌ها

حذف

• از ریشه شروع کن، برگ L را که وارده تعلق دارد پیدا کن.
• وارده را حذف کن

 * اگر L حداقل نیمه پر است، انجام بده!
 *اگر L کمتر از آنچه که باید ورودی داشته باشد،
 * توزیع مجدد انجام دهید، از همزادها قرض کنید.
 * اگر توزیع مجدد با شکست مواجه شد،L و همزاد را ادغام کنید.

• اگر ادغام رخ داد، باید وارده (اشاره‌کننده به L یا همزاد) را از والد حذف کنید.
• ادغام باید به ریشه منتشر شود، ارتفاع کاهش یابد.

بارگذاری قسمت

• یک مجموعه از رکوردهای داده، داده شده‌است. می‌خواهیم یک درخت +B اندیس روی برخی فیلد کلید بسازیم. یک روش این است که هر رکورد را در داخل یک درخت تهی قراردهیم. اگرچه نسبتاً گران است، چون برای هر وارده نیازداریم از ریشه شروع کنیم و پایین برویم تابه صفحه برگ مناسب برسیم. راه دیگر، استفاده از bulk-loading است.

 *اولین مرحله این است که وارده‌های داده را مطابق با یک کلید جستجو مرتب کنیم.

• یک صفحه خالی اختصاص می‌دهیم تا به جای ریشه به کار رود و یک اشاره گر به صفحه اول وارده‌ها در داخل آن قرار می‌دهیم. زمانی که ریشه پراست، ریشه را تقسیم می‌کنیم، ویک صفحه ریشه جدید ایجاد می‌کنیم

ویژگی‌ها

برای یک درخت بی پلاس از درجهٔ b با h تعداد طبقهٔ ذخیره شده:

• بیشینهٔ تعداد رکوردهای ذخیره شده برابر است با ${\displaystyle n_{max}=b^{h}-b^{h-1}}$
• کمینه تعداد کلیدها برابر است با ${\displaystyle n_{kmin}=2(b/2)^{h-1}}$
• حافظهٔ مورد نیاز برای ذخیره درخت از(O(nاست
• درج کردن یک رکورد در بدترین حالت به ${\displaystyle (O(\log _{b}n}$ عملیات نیاز دارد
• جستجوی یک رکورد در بدترین حالت به${\displaystyle (O(\log _{b}n}$ عملیات نیاز دارد
• حذف کردن یک رکورد (قبلاً یافت شده) در بدترین حالت به ${\displaystyle (O(\log _{b}n}$ عملیات نیاز دارد
• انجام یک جستجوی حوزه‌ای با k عنصر در آن محدوده در بدترین حالت به ${\displaystyle (O(\log _{b}n+k}$ عملیات نیاز دارد
• انجام یک جستجوی صفحه‌ای با اندازه صفحه s و شماره صفحه p به (s*p)عملیات نیاز دارد.

اجرا

برگ‌های (پایین‌ترین بلوک‌های ذخیره‌ای) درخت بی پلاس اغلب در یکلیست پیوندی به یکدیگر متصل هستند؛ این، جستجوی حوزه‌ای یا بازگویی (ترتیبی) از طریق بلوک‌ها را آسان تر و کارآمد تر می‌کند (با این که پیوند بالایی ذکر شده بدون این مورد اضافه شده نیز امکان‌پذیر است). این نگهداری و مصرف فضا روی درخت را عمدتاً افزایش نمی‌دهد.

اگر بلوک‌های ذخیره‌ای یک سیستم دارای سایز B بایت باشند، و تعداد کلیدهایی که باید ذخیره شوند k باشد، به‌طور مستدل کارآمدترین درخت بی پلاس آن است که b = (B / k) – 1. با این که ایجاد این محدودیت به‌طور نظری ضروری نیست، اما در عمل، اغلب کمی فضای اضافی توسط بلوک‌های ذخیره‌ای گرفته می‌شود (به عنوان مثال، ارجاع‌های لیست پیوندی در بلوک‌های برگ). داشتن یک بلوک ذخیره‌ای که کمی بزرگتر از بلوک واقعی سیستم ذخیره‌ای است یک کاهش اساسی در کارایی را نشان می‌دهد؛ در نتیجه احتیاط بیش از حد ترجیح داده می‌شوداست.

اگر گره‌های درخت بی پلاس به صورت آرایه‌ای از عناصر سازمان دهی شده باشند، برای درج یا حذف یک عنصر زمان قابل توجهی صرف می‌شود از آنجا که به‌طور میانگین نیمی از آرایه باید جابجا شود (شیفت داده شود). برای غلبه بر این مشکل، عناصر درون یک گره می‌توانند به جای آرایه به صورت یک درخت دودویی جستجو یا یک درخت بی پلاس سازماندهی شوند.

درختان بی پلاس همچنین برای داده‌های ذخیره شده در RAM استفاده می‌شوند. در این مورد یک انتخاب معقول برای سایز بلوک‌ها برابر سایز پهنای باند حافظه نهان(cache) پردازنده‌است. اگر چه بعضی از تحقیقات نشان داده‌است که یک بلوک با سایزی که چند برابر سایز پهنای باند حافظه نهان پردازنده‌است می‌تواند اجرای بهتری داشته باشد اگر واکشی از قبل توسط حافظه نهان استفاده شود.

بهینه بودن فضا در درخت بی پلاس می‌تواند با استفاده از بعضی تکنیک‌های فشرده‌سازی بهبود پیدا کند. یک راه استفاده از رمزگذاری دلتا (اختلافی) برای فشرده کردن کلیدهای ذخیره شده در هر بلوک است. برای بلوک‌های داخلی، حفظ فضا با فشرده‌سازی کلیدها یا اشاره گرها بدست می‌آید. برای کلیدهای رشته‌ای(string)، فضا می‌تواند با استفاده از روش زیر ذخیره شود: معمولاً i امین ورودی یک بلوک داخلی اولین کلید بلوک i+1 ام را دربردارد. به جای ذخیره کردن کل کلید می‌توان کوتاه‌ترین پیشوند از اولین کلید بلوک i+1 ام که اکیداً (در ترتیب واژه نگاری) بزرگ‌تر از آخرین کلید از بلوک i است. همچنین راه ساده‌ای برای فشرده‌سازی اشاره گرها وجود دارد: اگر فرض کنیم که بعضی از بلوک‌های پشت سر هم i+k...i+1،i به صورت متصل و نزدیک به هم ذخیره می‌شوند، پس تنها ذخیرهٔ اشاره گر به اولین بلوک و تعداد بلوکهای پی در پی کفایت می‌کند.

تمام روش‌های فشردگی بالا دارای اشکالاتی هستند. اول، یک بلوک پر باید ناهم فشرده‌سازی شود برای این که یک عنصر را خارج کند. یک روش برای غلبه کردن بر این مشکل این است که هر بلوک را به زیر بلوک‌هایی تقسیم کرده و آن‌ها را جداگانه فشرده کنیم. در این روش جستجو و درج یک عنصر تنها نیاز است که یک زیربلوک به جای یک بلوک کامل فشرده یا ناهم فشرده شود. مانع دیگر روش‌های فشرده‌سازی این است که تعداد عناصر ذخیره شده ممکن است به‌طور قابل ملاحظه‌ای از یک بلوک به دیگری با توجه به این که تا چه حد این عناصر به خوبی در هر بلوک فشرده‌سازی شده‌اند، تغییر کند.

جستارهای وابسته

• درخت جستجوی دودویی
• درخت بی
• الگوریتم تقسیم و حل

منابع

• Ramakrishnan Raghu, Gehrke Johannes - Database Management Systems, McGraw-Hill Higher Education (2000), 2nd edition (en) page 267
• B+ tree