موضوع مقاله: درخت بی‌پلاس | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت بی‌پلاس | مقدمه: درعوض، مفهوم نگهداری همه داده‌ها در برگ‌ها به‌طور مکرر به عنوان یک متغیر جذاب پرورش یافته‌است. | ## بخش 1: درخت بی‌پلاس | کومر ذکر کرده که درخت بی پلاس در نرم‌افزار دسترسی به داده‌های 《VSAM 》متعلق به شرکت 《IBM》 مورد استفاده قرار گرفته و او به یک مقاله منتشر شده 《IBM》 در سال ۱۹۷۳ اشاره می‌کند. درخت بی پلاس در علوم کامپیوتر، یک درخت بی پلاس درختی است که داده مرتب شده را به شکلی نشان می‌دهد که درج، دریافت و حذف اطلاعات که هر کدام با یک کلید مشخص می‌شود، کارآمد باشد. این یک حافظه ذخیره‌ای پویا و چند سطحی است، با پیوندهای بیشینه و کمینه بین تعداد کلیدهای هر خانه ذخیره‌ای (عموماً به آن‌ها گره یا بلوک گفته می‌شود). در یک درخت بی پلاس، بر خلاف یک درخت بی ماینس، تمام رکوردها در سطح برگ‌های درخت ذخیره می‌شوند؛ تنها کلیدها در گره داخلی ذخیره می‌شوند. ارزش اولیهٔ یک درخت بی پلاس در ذخیره کردن داده‌های آن با مفهوم یک ذخیره‌سازی بلوک-محور به‌طور خاص سیستم فایل‌ها برای بازیابی کار آمد است. این عمدتاً به دلیل این است که بر خلاف درخت جستجوی دودویی، درختان بی پلاس گنجایش خروجی زیادی دارند (به‌طور نمونه‌ای از مرتبه ۱۰۰ یا بیشتر)، که تعداد عملیات ورودی/خروجی مورد نیاز برای پیدا کردن یک عنصر در درخت را کاهش می‌دهد. نکته‌ها درجه یا عامل شاخه‌ای شدن یک درخت بی پلاس با مقدار b، گنجایش گره‌ها (تعداد فرزندان گره‌ها) را برای گره‌های داخلی درخت محاسبه می‌کند. تعداد فرزندان واقعی برای هر گره، که آن را با m مشخص می‌کنند، برای گره‌های داخلی محدود می‌شود در نتیجه . برای مثال: اگر درجهٔ یک درخت بی پلاس ۷ باشد، هر گره داخلی (به جز ریشه) ممکن است بین ۴ تا ۷ فرزند داشته باشد؛ برگ‌ها فرزندی ندارند (بر اساس تعریف)، ولی محدود شده‌اند در نتیجه تعداد کلیدها باید حداقل و حد اکثر b-1 باشد. جستجو الگوریتم انجام دادن یک جستجو برای یک رکورد r اشاره گرها را تا فرزند درست هر گره دنبال می‌کند تا زمانی که به یک برگ برسد. پس از آن، برگ پیمایش می‌شود تا زمانی که رکورد صحیح یافت شود (یا تا زمانی که شکست بخورد). درج یک جستجو انجام بده تا مشخص شود که رکورد جدید در کدام سطل باید برود اگر سطل پر نبود، رکورد را اضافه کن. | ## بخش 2: درخت بی‌پلاس | یک برگ جدید ایجاد کن و نیمی از عناصر سطل را به سطل جدید منتقل کن کوچک‌ترین کلید برگ جدید را درج کن و آن را به گره پدر اشاره بده. اگر گره پدر پر است، آن را هم دو قسمت کن حال کلید میانی را به گره پدر اضافه کن تا زمانی که به پدری نرسیده که نیازی به افراز ندارد ادامه بده اگر ریشه افراز شود، یک ریشه جدید ایجاد کن که یک کلید و دو اشاره گر داشته باشد. درخت‌های B در ریشه رشد می‌کنند نه در برگ‌ها حذف از ریشه شروع کن، برگ L را که وارده تعلق دارد پیدا کن. *اگر L کمتر از آنچه که باید ورودی داشته باشد، * توزیع مجدد انجام دهید، از همزادها قرض کنید. اگرچه نسبتاً گران است، چون برای هر وارده نیازداریم از ریشه شروع کنیم و پایین برویم تابه صفحه برگ مناسب برسیم. یک صفحه خالی اختصاص می‌دهیم تا به جای ریشه به کار رود و یک اشاره گر به صفحه اول وارده‌ها در داخل آن قرار می‌دهیم. زمانی که ریشه پراست، ریشه را تقسیم می‌کنیم، ویک صفحه ریشه جدید ایجاد می‌کنیم ویژگی‌ها برای یک درخت بی پلاس از درجهٔ b با h تعداد طبقهٔ ذخیره شده: بیشینهٔ تعداد رکوردهای ذخیره شده برابر است با کمینه تعداد کلیدها برابر است با حافظهٔ مورد نیاز برای ذخیره درخت از(O(nاست درج کردن یک رکورد در بدترین حالت به عملیات نیاز دارد جستجوی یک رکورد در بدترین حالت به عملیات نیاز دارد حذف کردن یک رکورد (قبلاً یافت شده) در بدترین حالت به عملیات نیاز دارد انجام یک جستجوی حوزه‌ای با k عنصر در آن محدوده در بدترین حالت به عملیات نیاز دارد انجام یک جستجوی صفحه‌ای با اندازه صفحه s و شماره صفحه p به (s*p)عملیات نیاز دارد. اجرا برگ‌های (پایین‌ترین بلوک‌های ذخیره‌ای) درخت بی پلاس اغلب در یکلیست پیوندی به یکدیگر متصل هستند؛ این، جستجوی حوزه‌ای یا بازگویی (ترتیبی) از طریق بلوک‌ها را آسان تر و کارآمد تر می‌کند (با این که پیوند بالایی ذکر شده بدون این مورد اضافه شده نیز امکان‌پذیر است). اگر بلوک‌های ذخیره‌ای یک سیستم دارای سایز B بایت باشند، و تعداد کلیدهایی که باید ذخیره شوند k باشد، به‌طور مستدل کارآمدترین درخت بی پلاس آن است که b = (B / k) – 1. با این که ایجاد این محدودیت به‌طور نظری ضروری نیست، اما در عمل، اغلب کمی فضای اضافی توسط بلوک‌های ذخیره‌ای گرفته می‌شود (به عنوان مثال، ارجاع‌های لیست پیوندی در بلوک‌های برگ). داشتن یک بلوک ذخیره‌ای که کمی بزرگتر از بلوک واقعی سیستم ذخیره‌ای است یک کاهش اساسی در کارایی را نشان می‌دهد؛ در نتیجه احتیاط بیش از حد ترجیح داده می‌شوداست. اگر گره‌های درخت بی پلاس به صورت آرایه‌ای از عناصر سازمان دهی شده باشند، برای درج یا حذف یک عنصر زمان قابل توجهی صرف می‌شود از آنجا که به‌طور میانگین نیمی از آرایه باید جابجا شود (شیفت داده شود). | ## بخش 3: درخت بی‌پلاس | برای غلبه بر این مشکل، عناصر درون یک گره می‌توانند به جای آرایه به صورت یک درخت دودویی جستجو یا یک درخت بی پلاس سازماندهی شوند. در این مورد یک انتخاب معقول برای سایز بلوک‌ها برابر سایز پهنای باند حافظه نهان(cache) پردازنده‌است. اگر چه بعضی از تحقیقات نشان داده‌است که یک بلوک با سایزی که چند برابر سایز پهنای باند حافظه نهان پردازنده‌است می‌تواند اجرای بهتری داشته باشد اگر واکشی از قبل توسط حافظه نهان استفاده شود. بهینه بودن فضا در درخت بی پلاس می‌تواند با استفاده از بعضی تکنیک‌های فشرده‌سازی بهبود پیدا کند. یک راه استفاده از رمزگذاری دلتا (اختلافی) برای فشرده کردن کلیدهای ذخیره شده در هر بلوک است. برای کلیدهای رشته‌ای(string)، فضا می‌تواند با استفاده از روش زیر ذخیره شود: معمولاً i امین ورودی یک بلوک داخلی اولین کلید بلوک i+1 ام را دربردارد. به جای ذخیره کردن کل کلید می‌توان کوتاه‌ترین پیشوند از اولین کلید بلوک i+1 ام که اکیداً (در ترتیب واژه نگاری) بزرگ‌تر از آخرین کلید از بلوک i است. همچنین راه ساده‌ای برای فشرده‌سازی اشاره گرها وجود دارد: اگر فرض کنیم که بعضی از بلوک‌های پشت سر هم i+k...i+1،i به صورت متصل و نزدیک به هم ذخیره می‌شوند، پس تنها ذخیرهٔ اشاره گر به اولین بلوک و تعداد بلوکهای پی در پی کفایت می‌کند. یک روش برای غلبه کردن بر این مشکل این است که هر بلوک را به زیر بلوک‌هایی تقسیم کرده و آن‌ها را جداگانه فشرده کنیم. در این روش جستجو و درج یک عنصر تنها نیاز است که یک زیربلوک به جای یک بلوک کامل فشرده یا ناهم فشرده شود. | ## جمع‌بندی | مانع دیگر روش‌های فشرده‌سازی این است که تعداد عناصر ذخیره شده ممکن است به‌طور قابل ملاحظه‌ای از یک بلوک به دیگری با توجه به این که تا چه حد این عناصر به خوبی در هر بلوک فشرده‌سازی شده‌اند، تغییر کند.