درخت بی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات: تصحیح جایگذاری کاما، شمارگان هزارگان |
جز ربات: تصحیح کاما، شمارگان هزارگان |
||
خط ۳:
در [[علوم کامپیوتر]]، یک '''درخت بی''' یا بی‌تری {{انگلیسی|B-tree}} [[داده‌ساختاری درختی]] است که داده‌ها را به صورت مرتب‌شده نگه می‌دارد و جستجو، درج و حذف را در [[زمان مصرفی]] لگاریتمی میسر می‌سازد. بر خلاف [[درخت‌های جستجوی دودویی متوازن]] {{انگلیسی|Balanced binary search tree}}، این داده‌ساختار برای سیستم‌هایی که بلاک‌های عظیم اطلاعات را خوانده و می‌نویسند بهینه‌سازی شده است. این داده‌ساختار معمولاً در [[پایگاه‌های داده]] و [[فایل‌های سیستمی]] استفاده می‌شود.
در درخت بی، گره‌های درونی(و نه برگ‌ها) می‌توانند یک شمارهٔ متغیر از محدوده‌ای ازپیش‌تعریف‌شده مربوط به گره‌های فرزند را اختیار کنند. زمانی که داده‌ها درج شده و یا از یک گره حذف می‌شوند، شمارهٔ گره‌های فرزند آن‌ها تغییر می‌کند. به منظور نگه‌داری محدودهٔ ازپیش‌تعریف‌شده، ممکن است گره‌های درونی به هم متصل شده و یا از هم جدا شوند. به دلیل اینکه محدوده‌ای از گره‌های فرزند مجاز هستند، درخت بی، همانند دیگر [[درخت‌های جستجوی متوازن]]
یک درخت بی با استلزام اینکه همهٔ [[برگ‌ها]] در یک عمق قرار داشته باشند، به صورت متوازن نگه داشته‌می‌شود. این عمق از طریق عناصری که به درخت اضافه می‌شوند کم‌کم افزایش می‌یابد، ولی افزایش در عمق سراسری، کم اتفاق می‌افتد و وجود یک گرهٔ اضافیِ دورتر از ریشه را نتیجه می‌دهد.
خط ۱۵:
# گره‌ای که برگ نبوده و k فرزند داشته‌باشد، حاوی k-1 کلید می‌باشد.
[[رودالف بیر]] و دد مک‌کرِیت درخت بی را زمانی که در شرکت [[بوئینگ]] <ref>[http://www.minet.uni-jena.de/dbis/lehre/ss2004/dbs2/Bayer_hist.pdf R. Bayer, E. McCreight. ''Organization and Maintenance of Large Ordered Indexes'', in ''Acta Informatica'', Vol. 1, Fasc. 3, 1972 pp. 173-189]</ref>
:"''B''alanced," "''B''road," یا "''B''ushy" ممکن است استفاده شده‌باشند [چون همهٔ برگ‌ها در یک سطح قرار دارند]. دیگران اظهار داشتند که حرف "B" از کلمهٔ [[بوئینگ]] گرفته شده است [به این دلیل که پدیدآوردنده درسال 1972 در آزمایشگاه‌های تحقیقاتی علمی شرکت بوئینگ کار می‌کرد]. با این وجود پنداشتن درخت بی به عنوان درخت "بِیِر" نیز درخور است.<ref>Douglas Comer. The Ubiquitous B-Tree. Computing Surveys, 11(2):123. June 1979.</ref>
== ساختارهای گره ==
عناصر هر گرهٔ درونی به عنوان مقادیری که [[زیردرخت]] های آن را تقسیم می‌کند، عمل می‌کنند. به عنوان مثال، اگر یک گرهٔ درونی سه فرزند (یا زیر درخت) داشته باشند، آنگاه این گره باید دو مقدار یا عنصر جداییِِ ''a''<sub>1</sub> و ''a''<sub>2</sub> داشته باشد. همهٔ مقادیر زیردرخت چپ کمتر از ''a''<sub>1</sub>
گره‌های درونی-- نه برگ‌ها-- در یک درخت بی معمولا" به عنوان نمایندهٔ مجموعهٔ مرتبی از عناصر و اشاره‌گرهای فرزندان در نظر گرفته می‌شوند. هر گرهٔ درونی شامل یک '''بیشینه ''' از ''U'' فرزند بوده و به جز ریشه، همگی یک '''کمینه ''' از ''L'' فرزند دارند. برای همهٔ گره‌های درونی به جز ریشه، تعداد عناصر، یکی کمتر تعداد اشاره‌گرهای فرزندان می‌باشد؛ تعداد عناصر بین ''L-1'' و ''U-1''. می‌باشد. مقدار ''U'' باید 2''L'' و یا 2''L''-1 باشد؛ بنابراین هر گرهٔ درونی حداقل نیمه‌پر است. این رابطه بین ''U'' و ''L'' ایجاب می‌کند که دو گرهٔ نیمه‌پر بتوانند به منظور ایجاد یک گرهٔ مطلوب به هم وصل شوند، و یک گرهٔ کامل بتواند به دو گرهٔ مطلوب منشعب شود. این ویژگی‌ها، حذف و درج مقادیر جدید را در یک درخت بی ممکن می‌سازد و امکان حفظ ویژگی‌های درخت بی را به درخت می‌دهد.
خط ۲۵:
ریشه، برای تعداد فرزندان، کران بالا دارد، ولی کران پایین نه. برای مثال، وقتی در کل کمتر از ''L-1'' عنصر داشته باشیم، ریشه تنها گرهٔ درخت خواهد بود، و در عین حال فرزندی هم نخواهد داشت.
یک درخت بی با عمق ''n+1'' می‌تواند همانند بک درخت بی با عمق ''n'' حدود ''U''
بعضی از درخت‌های متوازن مقادیر را فقط در برگ‌ها ذخیره می‌کنند، و بدین ترتیب انواع مختلف برگ‌ها و گره‌های درونی را خواهند داشت. درختِ بی، مقادیر را در همهٔ گره‌ها نگه می‌دارد، و ممکن است ساختار مشابهی را برای تمام گره‌ها به کار ببندد. با این وجود، به این دلیل که برگ‌ها فرزندی ندارند، یک ساختار اختصاصی برای برگ‌ها در درختِ بی، کارایی را بهبود خواهد بخشید.
خط ۵۳:
## این مقدارِ جدایی به گرهٔ پدر اضافه می‌شود، که این کار ممکن است باعث تقسیم شدن پدر شود، و این روند به همین ترتیب ادامه می‌یابد.
اگر این تقسیم شدن‌ها تا ریشه ادامه یابد، ریشهٔ جدیدی با یک مقدارِ جدایی یکتا و دو فرزند ایجاد می‌کند و دلیل اینکه حد پایین برای اندازهٔ گره‌های درونی برای ریشه اعمال نمی‌شود نیز همین می‌باشد. بیشینهٔ تعداد عناصر در یک گره ''U''-1 می‌باشد. زمانی که گره‌ای تقسیم می‌شود، یک عنصر به پدر انتقال می‌یابد، ولی یک عنصر هم اضافه می‌شود. بنابراین، باید امکان‌پذیر باشد که بیشینهٔ تعداد عناصر ( ''U''-1 ) به دو گرهٔ مجاز تقسیم شود. اگر این عدد فرد باشد، آنگاه ''U''=2''L'' بوده و یکی از گره‌های جدید شامل U''-2)/2 = ''L''-1'') عنصر و از این‌رو یک گرهٔ مجاز خواهد بود. دیگری هم که یک عنصر بیشتر دارد و از این‌رو گره‌ای مجاز خواهد بود. اگر ''U''-1 زوج باشد، آنگاه ''U''=2''L''-
یک الگوریتم بهبودیافته، بر پایهٔ پیمایشی منفرد به سمت پایین از ریشه به گره‌ای که قرار است عمل درج در آن انجام شود و تقسیم کردن هر گرهٔ کاملی که در این مسیر با آن مواجه می‌شود، استوار است. این الگوریتم از نیاز به فراخوانی مجدد پدر به داخل حافظه جلوگیری به عمل می‌آورد، که این فراخوانی در صورتی که گره‌ها در حافظهٔ ثانویه قرار داشته‌باشند ممکن است پرهزینه باشد. به هرحال، برای استفاده از این الگوریتم بهبودیافته، ما باید قادر باشیم بدون افزودن یک عنصر جدید، عنصری را به پدر منتقل کنیم و ''U''-2 عنصر باقی‌مانده را به دو گرهٔ قابل قبول تقسیم نماییم. این امر مستلزم آن است که به جای ''U'' = 2''L'' داشته باشیم: ''U'' = 2''L''-
=== حذف ===
خط ۹۷:
** اولین فرزندِ هم‌زادِ چپ را به آخرین فرزند گرهٔ ناقص وارد می‌کنیم.
* اگر هردوی فرزندانِ بدون واسطه، فقط کمینهٔ تعداد عناصر را داشته‌باشند؛
** یک گرهٔ جدید با همهٔ عناصرِ گرهٔ ناقص و همهٔ عناصر یکی از هم‌زادان آن و جداکنندهٔ بین دو گرهٔ هم‌زاد مرکب موجود در
** جداکننده را از پدر حذف می‌کنیم، و دو فرزندِ حاصله از آن را با گرهٔ ترکیب‌شده جایگزین می‌کنیم.
** اگر این کار تعداد عناصر گرهٔ پدر را به زیر مقدار کیمینه رساند، مراحل مذکور را برای آن گرهٔ ناقص هم تکرار می‌کنیم، مگر زمانی که به ریشه رسیده‌باشیم، چرا که ناقص بودن ریشه اشکالی ندارد.
| |||