Kľúčový rozdiel: v binárnych stromoch sú stromové dátové štruktúry, ktoré ukladajú dáta a umožňujú užívateľovi prístup, vyhľadávanie, vkladanie a odstraňovanie údajov v algoritmickom čase. Rozdiel medzi stromom B a B + spočíva v tom, že v B-strome môžu byť kľúče a dáta uložené v internej aj v uzlových listoch, zatiaľ čo v strome B + môžu byť dáta a kľúče uložené len v uzloch listov,
Binárne stromy sú vyvážené vyhľadávacie stromy, ktoré sú navrhnuté tak, aby dobre fungovali na sekundárnych pamäťových zariadeniach s priamym prístupom, ako sú magnetické disky. Rudolf Bayer a Ed McCreight vynašli koncept B-stromu.
B-strom je všeobecný binárny vyhľadávací strom, v ktorom môže každý uzol mať viac ako dve deti. Každý interný uzol v B-strome obsahuje niekoľko kľúčov. Tieto klávesy oddeľujú hodnoty a ďalej vytvárajú podstránky. Vnútorné uzly v strome B môžu mať premenlivé počty podradených uzlov, ktoré sú usporiadané v rámci vopred definovaného rozsahu. V čase vloženia alebo odstránenia akýchkoľvek údajov z príslušného uzla dochádza k zmene počtu dcérskych uzlov. Aby sa zachoval preddefinovaný rozsah, vnútorné uzly môžu byť spojené alebo rozdelené. V strome B je povolený rozsah detských uzlov, vďaka čomu je potrebné zachovať vopred definovaný rozsah.
B-stromy nemusia byť často vyvažované na rozdiel od iných stromov s vlastným vyvažovaním. Uzly v týchto stromoch nie sú vždy plné; preto sa priestory v týchto stromoch spotrebúvajú zbytočne, čo vedie k plytvaniu priestoru. Iba dolná a horná hranica počtu detských uzlov sú zvyčajne určené pre určitú implementáciu. Napríklad v stromu 2-3 B (často jednoducho označovaný ako strom 2-3), každý vnútorný uzol môže mať iba 2 alebo 3 podradné uzly.
Okrem toho je strom B optimalizovaný pre systémy, ktoré čítajú a zapisujú veľké bloky dát. Je bežne používaný v databázach a súborových systémoch. V strome B sú všetky uzly udržiavané v rovnakých vyvažovacích hĺbkach od koreňových uzlov. Tieto hĺbky sa zvyšujú pomaly, keď sa počet prvkov zvyšuje; toto vedie k tomu, že všetky uzly listov sú ešte jeden uzol vzdialený od koreňa. Okrem toho sú B-stromy výhodnejšie v porovnaní s inými implementáciami vzhľadom na čas potrebný na prístup k údajom.
Strom B + je strom n-array s uzlom, ktorý pozostáva z veľkého počtu detí na uzol. Koreň môže byť list alebo uzol, ktorý obsahuje viac ako dve deti. Strom B + pozostáva z koreňa, vnútorných uzlov a listov.
Strom B + je rovnaký ako strom B; jediný rozdiel je v tom, že v stromu B + je na spodnej strane pridaná dodatočná hladina s pripojenými listami. Tiež, na rozdiel od stromu B, každý uzol v stromu B + obsahuje iba kľúče a nie páry kľúč-hodnota.
Navyše balančný faktor alebo poradie stromu B + meria kapacitu pre vnútorné uzly stromu, tj počet uzlov, ktoré môžu mať. Skutočný počet detí pre uzol je obmedzený na interné uzly. Koreň je však výnimkou, pretože môže mať viac ako dva deti. Napríklad, ak je poradie stromu B + 7, každý vnútorný uzol (okrem koreňa) môže mať medzi 4 a 7 deťmi; zatiaľ čo koreň môže mať medzi 2 a 7. Primárnou hodnotou stromu B + je uchovávanie údajov pre efektívne vyhľadávanie v kontexte úložného priestoru orientovaného blokom a najmä súborových systémov.
Primárna hodnota stromu B + spočíva v ukladaní a uchovávaní údajov, aby sa údaje nestratili. Tento prístup sa uplatňuje najmä v kontexte úložného priestoru orientovaného na bloky av niektorých konkrétnych súborových systémoch. Listy, ktoré sú najdôležitejšími indexovými blokmi stromu B +, sú navzájom prepojené v prepojenom zozname; a tým sa zjednodušia a zefektívňujú rozsahové otázky alebo usporiadaná iterácia cez bloky. Navyše vesmírny faktor nie je plytvaný v stromoch B +. Strom B + poskytuje efektívny formát dátovej štruktúry, čo zjednodušuje ich prístup a ukladanie. Stromy B + sú obzvlášť užitočné ako index databázového systému, kde sa dáta zvyčajne nachádzajú na disku.
Porovnanie stromu B a stromu B +:
B Strom | Strom B + | |
Stručné popisy webových stránok | AB strom je organizačná štruktúra pre ukladanie a vyhľadávanie informácií v podobe stromu, v ktorom sú všetky terminálne uzly v rovnakej vzdialenosti od základne a všetky neterminálne uzly majú medzi n a 2 n sub stromami alebo ukazovateľmi (kde n je celé číslo). | B + strom je strom n-array s premennou, ale často veľkým počtom detí na uzol. Strom B + pozostáva z koreňa, vnútorných uzlov a listov. Koreň môže byť buď list alebo uzol s dvomi alebo viacerými deťmi. |
Taktiež známy ako | Vyvážený strom. | Strom B plus. |
priestor | O (n) | O (n) |
Vyhľadávanie | O (log n) | O (log bn) |
insert | O (log n) | O (log bn) |
vymazať | O (log n) | O (log bn) |
skladovanie | V strome B vyhľadávacie tlačidlá a dáta uložené vo vnútorných alebo listových uzloch. | V strome B + sa údaje ukladajú len v uzlach listov. |
údaje | Uzly listov troch ukazovateľov ukladať na záznamy skôr ako skutočné záznamy. | Listy uzlov stromu uchovávajú skutočný záznam skôr ako ukazovatele na záznamy. |
priestor | Tieto stromy strácajú priestor | Tam stromy nestrácajú priestor. |
Funkcia uzlov listov | V strom B sa uzol listu nedá uložiť pomocou prepojeného zoznamu. | V stromu B + sú dáta uzlových bodov v zozname postupne prepojené. |
vyhľadávanie | Tu sa hľadanie v strome B stane ťažkým, pretože dáta nie je možné nájsť v uzle listov. | Vyhľadávanie akýchkoľvek údajov v strome B + je veľmi jednoduché, pretože všetky údaje sa nachádzajú v uzloch listov. |
Prístupnosť vyhľadávania | Tu v strome B nie je vyhľadávanie také ľahké v porovnaní so stromom B +. | Tu v strome B + je vyhľadávanie jednoduché. |
Redundantné tlačidlo | Neuchovávajú nadbytočný kľúč vyhľadávania. | Ukladajú redundantné vyhľadávacie tlačidlo. |
aplikácia | Sú to staršie verzie a nie sú také výhodné v porovnaní s stromami B +. | Mnoho implementátorov databázových systémov uprednostňuje štrukturálnu jednoduchosť stromu B +. |
