درخت بی‌پلاس کیست؟ توضیح بده.
درخت بی برای اولین بار در مقاله《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》 در سال ۱۹۷۳ اشاره می‌کند.درخت بی پلاس.در علوم کامپیوتر، یک درخت بی پلاس درختی است که داده مرتب شده را به شکلی نشان می‌دهد که درج، دریافت و حذف اطلاعات که هر کدام با یک کلید مشخص می‌شود، کارآمد باشد. این یک حافظه ذخیره‌ای پویا و چند سطحی است، با پیوندهای بیشینه و کمینه بین تعداد کلیدهای هر خانه ذخیره‌ای (عموماً به آن‌ها یا گفته می‌شود). در یک درخت بی پلاس، بر خلاف یک ، تمام رکوردها در سطح برگ‌های درخت ذخیره می‌شوند؛ تنها کلیدها در گره داخلی ذخیره می‌شوند.ارزش اولیهٔ یک درخت بی پلاس در ذخیره کردن داده‌های آن با مفهوم یک ذخیره‌سازی به‌طور خاص برای بازیابی کار آمد است. این عمدتاً به دلیل این است که بر خلاف درخت جستجوی دودویی، درختان بی پلاس گنجایش خروجی زیادی دارند (به‌طور نمونه‌ای از مرتبه ۱۰۰ یا بیشتر)، که تعداد عملیات ورودی/خروجی مورد نیاز برای پیدا کردن یک عنصر در درخت را کاهش می‌دهد.سیستم فایل های, NTFS, , , همگی از این نوع درخت برای ذخیره‌سازی (فهرست سازی) اطلاعات دربارهٔ داده‌ها استفاده می‌کنند. پایگاه‌های داده مثل ، , , ، , PostgerSQL, , واس‌کیوال لایت این نوع درخت را برای جدول خانه‌های حافظه پشتیبانی می‌کنند. سیستم‌های مدیریتی کلید-مقدار مانند Tokyo Tyrant و این نوع درخت را برای دسترسی به داده‌ها تأیید می‌کند. InfinityDB یک درخت ب متقارن است.نکته‌ها.درجه یا عامل شاخه‌ای شدن یک درخت بی پلاس با مقدار b، گنجایش گره‌ها (تعداد فرزندان گره‌ها)را برای گره‌های داخلی درخت محاسبه می‌کند. تعداد فرزندان واقعی برای هر گره، که آن را با m مشخص می‌کنند، برای محدود می‌شود در نتیجه formula_1. ریشه درخت یک استثنا است: تنها مجاز است که دو فرزند داشته باشد. برای مثال: اگر درجهٔ یک درخت بی پلاس ۷ باشد، هر گره داخلی (به جز ریشه) ممکن است بین ۴ تا ۷ فرزند داشته باشد؛ برگ‌ها فرزندی ندارند (بر اساس تعریف)، ولی محدود شده‌اند در نتیجه تعداد کلیدها باید حداقل formula_2 و حد اکثر 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این سودوکد فرض کرده که هیچ تکراری مجاز نیست.جستجو خیلی سریع است.حذف. * اگر L حداقل نیمه پر است، انجام بده! *اگر L کمتر از آنچه که باید ورودی داشته باشد، * توزیع مجدد انجام دهید، از همزادها قرض کنید. * اگر توزیع مجدد با شکست مواجه شد،L و همزاد را ادغام کنید.بارگذاری قسمت. *اولین مرحله این است که وارده‌های داده را مطابق با یک کلید جستجو مرتب کنیم.ویژگی‌ها.برای یک درخت بی پلاس از درجهٔ b با h تعداد طبقهٔ ذخیره شده:اجرا.برگ‌های (پایین‌ترین بلوک‌های ذخیره‌ای) درخت بی پلاس اغلب در یکلیست پیوندی به یکدیگر متصل هستند؛ این، جستجوی حوزه‌ای یا بازگویی (ترتیبی) از طریق بلوک‌ها را آسان تر و کارآمد تر می‌کند (با این که پیوند بالایی ذکر شده بدون این مورد اضافه شده نیز امکان‌پذیر است). این نگهداری و مصرف فضا روی درخت را عمدتاً افزایش نمی‌دهد.اگر بلوک‌های ذخیره‌ای یک سیستم دارای B بایت باشند، و تعداد کلیدهایی که باید ذخیره شوند k باشد، به‌طور مستدل کارآمدترین درخت بی پلاس آن است که b = (B / k) – 1. با این که ایجاد این محدودیت به‌طور نظری ضروری نیست، اما در عمل، اغلب کمی فضای اضافی توسط بلوک‌های ذخیره‌ای گرفته می‌شود (به عنوان مثال، ارجاع‌های لیست پیوندی در بلوک‌های برگ). داشتن یک بلوک ذخیره‌ای که کمی بزرگتر از بلوک واقعی سیستم ذخیره‌ای است یک کاهش اساسی در کارایی را نشان می‌دهد؛ در نتیجه احتیاط بیش از حد ترجیح داده می‌شوداست.اگر گره‌های درخت بی پلاس به صورت آرایه‌ای از عناصر سازمان دهی شده باشند، برای درج یا حذف یک عنصر زمان قابل توجهی صرف می‌شود از آنجا که به‌طور میانگین نیمی از آرایه باید جابجا شود (شیفت داده شود). برای غلبه بر این مشکل، عناصر درون یک گره می‌توانند به جای آرایه به صورت یک درخت دودویی جستجو یا یک درخت بی پلاس سازماندهی شوند.درختان بی پلاس همچنین برای داده‌های ذخیره شده در RAM استفاده می‌شوند. در این مورد یک انتخاب معقول برای سایز بلوک‌ها برابر سایز پهنای باند حافظه نهان() پردازنده‌است. اگر چه بعضی از تحقیقات نشان داده‌است که یک بلوک با سایزی که چند برابر سایز پهنای باند حافظه نهان پردازنده‌است می‌تواند اجرای بهتری داشته باشد اگر توسط حافظه نهان استفاده شود.بهینه بودن فضا در درخت بی پلاس می‌تواند با استفاده از بعضی تکنیک‌های فشرده‌سازی بهبود پیدا کند. یک راه استفاده از (اختلافی) برای فشرده کردن کلیدهای ذخیره شده در هر بلوک است. برای بلوک‌های داخلی، حفظ فضا با فشرده‌سازی کلیدها یا اشاره گرها بدست می‌آید. برای کلیدهای رشته‌ای(string)، فضا می‌تواند با استفاده از روش زیر ذخیره شود: معمولاً i امین ورودی یک بلوک داخلی اولین کلید بلوک i+1 ام را دربردارد. به جای ذخیره کردن کل کلید می‌توان کوتاه‌ترین پیشوند از اولین کلید بلوک i+1 ام که اکیداً (در ترتیب واژه نگاری) بزرگ‌تر از آخرین کلید از بلوک i است. همچنین راه ساده‌ای برای فشرده‌سازی اشاره گرها وجود دارد: اگر فرض کنیم که بعضی از بلوک‌های پشت سر هم i+k...i+1،i به صورت متصل و نزدیک به هم ذخیره می‌شوند، پس تنها ذخیرهٔ اشاره گر به اولین بلوک و تعداد بلوکهای پی در پی کفایت می‌کند.تمام روش‌های فشردگی بالا دارای اشکالاتی هستند. اول، یک بلوک پر باید ناهم فشرده‌سازی شود برای این که یک عنصر را خارج کند. یک روش برای غلبه کردن بر این مشکل این است که هر بلوک را به زیر بلوک‌هایی تقسیم کرده و آن‌ها را جداگانه فشرده کنیم. در این روش جستجو و درج یک عنصر تنها نیاز است که یک زیربلوک به جای یک بلوک کامل فشرده یا ناهم فشرده شود. مانع دیگر روش‌های فشرده‌سازی این است که تعداد عناصر ذخیره شده ممکن است به‌طور قابل ملاحظه‌ای از یک بلوک به دیگری با توجه به این که تا چه حد این عناصر به خوبی در هر بلوک فشرده‌سازی شده‌اند، تغییر کند.