درخت بی‌پلاس

یک مثال ساده از درخت بی پلاس، وصل کردن کلیدهای ۱ تا ۷ به مقادیر داده‌ای d1 تا d7 است. در نظر داشته باشید که لیست پیوندی(قرمز)پیمایش سریع میان ترتیب را ممکن می‌سازد.

درخت بی برای اولین بار در مقاله 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 مشخص می‌کنند، برای گره‌های داخلی محدود می‌شود در نتیجه $\lceil \frac{b}{2}\rceil \le \ m \le \ b$. ریشه درخت یک استثنا است: تنها مجاز است که دو فرزند داشته باشد. برای مثال: اگر درجهٔ یک درخت بی پلاس ۷ باشد، هر گره داخلی (به جز ریشه) ممکن است بین ۴ تا ۷ فرزند داشته باشد؛ برگ‌ها فرزندی ندارند(بر اساس تعریف)، ولی محدود شده‌اند در نتیجه تعداد کلیدها باید حداقل $\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 با h تعداد طبقهٔ ذخیره شده:

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

اجرا

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

اگربلوک‌های ذخیره‌ای یک سیستم دارای سایز 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