Rozdiel medzi stromom B a stromom B +

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 +.

Odporúčaná

Súvisiace Články

  • populárne porovnania: Rozdiel medzi Samsung Galaxy S4 Mini a Samsung Galaxy S3

    Rozdiel medzi Samsung Galaxy S4 Mini a Samsung Galaxy S3

    Kľúčový rozdiel: Spoločnosť Samsung oficiálne oznámila malému bratovi svojej úplne novej vlajkovej lode: Samsung Galaxy S4 Mini. Telefón je vybavený 4, 3 palcovou kapacitou dotykovej obrazovky qHD Super AMOLED s kapacitou ~ 256 ppi. Hmotnosť telefónu bola tiež znížená na 107 gramov pre model 3G a 108 gramov pre model LTE. Galaxy S3 je mul
  • populárne porovnania: Rozdiel medzi manželkou a priateľkou

    Rozdiel medzi manželkou a priateľkou

    Hlavný rozdiel : Kľúčovým rozdielom medzi manželkou a priateľkou je to, že manželka je legálne vydatá za muža, zatiaľ čo priateľka môže byť priateľom, ale nie je s ním zobratá. Existuje veľa rozdielov medzi manželkou a priateľkou. Tento článok špecifikuje rozdiel medzi dvoma dámami. Manželka je ženským partne
  • populárne porovnania: Rozdiel medzi Hulu a Netflix

    Rozdiel medzi Hulu a Netflix

    Kľúčový rozdiel: Hulu je on-demand a internetová televízna sledovacia služba s väčším počtom televíznych relácií a menším počtom filmov. Netflix je on-demand a internetová televízna sledovacia služba so starými televíznymi reláciami a väčším počtom filmov. Late Trendom v televíznom vysielaní je sledovanie televízie pomocou internetového média na rôznych zariadeniach, ako sú televízia pripojená k internetu, Blu-ray prehrávače, set-top boxy, herná konzola, mobilné telefóny a tablety. Informácie o kompatibilite s prístrojmi s
  • populárne porovnania: Rozdiel medzi HP Envy X2 a Sony Xperia Z Tab

    Rozdiel medzi HP Envy X2 a Sony Xperia Z Tab

    Hlavný rozdiel: Envy X2 je hybridné zariadenie spoločnosti Hewlett-Packard (HP). Hybrid je v podstate krížom medzi tabletom a notebookom. Envy X2 je v prvom rade tabletu, ale ten, ktorý sa dá zakomponovať do fyzickej klávesnice. HP Envy X2 beží na operačnom systéme Windows 8, ktorý je napájaný z dvojjádrového procesora Intel Atom Processor Z2760 s procesorom 1, 80GHz a 2 GB 533 MHz LPDDR2 RAM. Spoločnosť Sony
  • populárne porovnania: Rozdiel medzi kruhom a elipsou

    Rozdiel medzi kruhom a elipsou

    Kľúčový rozdiel: Kruh a elipsa majú uzavreté zakrivené tvary. V kruhu sú všetky body rovnako ďaleko od stredu, čo nie je prípad elipsy; v elipse sú všetky body v rôznych vzdialenostiach od stredu. Matematicky, kruh je hlavným tvarom v oblasti geometrie a jeho definície: kruh je tvar so všetkými bodmi v rovnakej vzdialenosti od jeho stredu. Je pomenovaný pod
  • populárne porovnania: Rozdiel medzi Burger a Sandwich

    Rozdiel medzi Burger a Sandwich

    Kľúčový rozdiel: sendvič je varený všeobecným umiestnením výplne mäsa alebo zeleniny medzi dva plátky chleba (plochý chlieb), zatiaľ čo hamburger je varený umiestnením výplne mäsa alebo zeleniny medzi bunku nakrájaný na dva. Hlavným rozdielom je: sendvič používa plochý chlieb na viazanie a hamburger používa bunku na viazanie plnenia. Sendvič sa skladá z dvoch
  • populárne porovnania: Rozdiel medzi tukom a cholesterolom

    Rozdiel medzi tukom a cholesterolom

    Kľúčový rozdiel: Tuk je koncentrovaný zdroj energie. Poskytuje vankúš na ochranu našich životne dôležitých orgánov. Cholesterol je voskový, tukový materiál pripravený v pečeni a iných bunkách a nachádza sa v rôznych potravinách, ako sú potraviny zo zvierat, ako sú mliečne výrobky, vajcia a mäso. Tuky potrebujú telo na gen
  • populárne porovnania: Rozdiel medzi parakeety a Lorikeets

    Rozdiel medzi parakeety a Lorikeets

    Kľúčový rozdiel: Parakeety sú malé až stredne veľké a majú dlhé chvostové perie. Môžu sa pohybovať v rozmedzí od 7 "do 18". Lorikeety sú malé až stredne veľké stromové papagáje, ktoré spadajú do rôznych poddruhov kvôli ich špecializovaným jazýčkovým jazykom. Môžu mať veľkosť od 6 "do 16" a tiež majú jasné perie. Parakeety a Lorikeets sú vzájomne prep
  • populárne porovnania: Rozdiel medzi homogénnymi a heterogénnymi

    Rozdiel medzi homogénnymi a heterogénnymi

    Kľúčový rozdiel: Homogénny znamená riešenie, ktoré je úplne jednotnou zmesou dvoch alebo viacerých objektov. Heterogénny odkazuje na riešenia, ktoré nie sú úplne jednotné a vo väčšine prípadov sú zreteľne viditeľné pri prezeraní zmesi. Pojmy "homogénne" a "heterogénne" sú bežne používané slová v chémii a odkazujú na roztoky a zmesi. Každý typ zmesi možno rozdeliť ak

Redakcia Choice

Rozdiel medzi UHD a HD

Hlavný rozdiel: HD a Full HD sú formáty, ktoré sa používajú na vysielanie obrázkov a videa na rôznych multimediálnych zariadeniach. Významný rozdiel medzi oboma by bol ich príslušné uznesenia. High Definition alebo HD, ako je všeobecne známe, prinieslo definíciu zážitkov zo sledovania priemerného televízneho diváka. Jednoducho povedané,