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

  • rozdiel medzi: Rozdiel medzi nadchádzajúcim a nadchádzajúcim

    Rozdiel medzi nadchádzajúcim a nadchádzajúcim

    Kľúčový rozdiel: Nadchádzajúce a blížiace sa pojmy sú z veľkej časti synonymá. Termín "blížiaci sa" má však širší rozsah definícií ako "blížiaci sa". Stručne povedané, blížiace sa prostriedky prinášajú alebo vychádzajú, zatiaľ čo nadchádzajúce znamená niečo, čo sa blíži. Nadchádzajúce a nadchádzajúce pojmy sú č
  • rozdiel medzi: Rozdiel medzi sladkovodnými a slanými vodnými perlami

    Rozdiel medzi sladkovodnými a slanými vodnými perlami

    Kľúčový rozdiel: Sladkovodné perly sa pestujú vo sláve, ktoré žijú v bezolovnatých vodách, ako sú jazerá a rieky. Perle soľnej vody sa pestujú v ustriciach vo fyziologickej vode, ako sú oceány a moria. Perly sú považované za zaujímavú vzácnosť vo svete šperkov, pretože sa vyrábajú iným spôsobom ako iné kamene. Kým iné kamene sa produkujú v
  • rozdiel medzi: Rozdiel medzi Sony Xperia P a iPhone 4S

    Rozdiel medzi Sony Xperia P a iPhone 4S

    Hlavný rozdiel: Sony Xperia P je vybavená 4-palcovou dotykovou obrazovkou TFT, ktorá umožňuje až 4-dotykové funkcie. Obrazovka je odolná proti poškriabaniu a má odolný proti rozbitiu. Dotyková obrazovka poskytuje približne 275 ppi hustoty pixelov spolu s technológiou WhiteMagic, ktorá pridáva extra biely pixel s už prítomnou červenou, modrou a zelenou farbou. IPhone 4S bola ak
  • rozdiel medzi: Rozdiel medzi whisky a ryžovou whisky

    Rozdiel medzi whisky a ryžovou whisky

    Kľúčový rozdiel: Whisky alebo whisky sú typom destilovaného alkoholického nápoja vyrobeného z akejkoľvek formy kvaseného zrna. V závislosti od zemepisnej oblasti alebo druhu whisky, ktorá sa vyrába, môže byť whisky vyrobená z jačmeňa, sladového jačmeňa, raže, sladu, raže, pšenice a kukurice. Režná whisky je typ whis
  • rozdiel medzi: Rozdiel medzi Asus FonePad a HP Slate 7

    Rozdiel medzi Asus FonePad a HP Slate 7

    Kľúčový rozdiel: Asus oznámila spustenie najnovšieho phabletu, Asus Fonepad. Fonepad je 7-palcový tablet s Androidom, ktorý umožňuje používateľom uskutočňovať aj telefonické hovory umiestnením zariadenia do uší. Fablet vyžíva 7-palcovú IPS LED podsvietenú dotykovú obrazovku, ktorá umožňuje multitouchové schopnosti až pre 10 osôb. Obrazovka má rozlíšenie 1280
  • rozdiel medzi: Rozdiel medzi Lager a plzeňským pivom

    Rozdiel medzi Lager a plzeňským pivom

    Kľúčový rozdiel: Všetky pivá spadajú pod dve hlavné kategórie: vole a ležiak. Lagers sú typom spodného kvasenia piva. Plzeň je typ ležiaka, ktorý vznikol v Plzni, mestečku nachádzajúcom sa v Čechách. Existuje mnoho rôznych druhov pív, ktoré sú rozdelené do kategórií a označené podľa spôsobu fermentácie a spracovania. Sú tiež rozdelené a klasifikov
  • rozdiel medzi: Rozdiel medzi kávou a čajom

    Rozdiel medzi kávou a čajom

    Kľúčový rozdiel: Čaj je odvodený od Camellia sinensis, zatiaľ čo káva pochádza z rastliny Coffea. Obidva sa líšia v procese, chuti a prínosoch pre zdravie. Čaj a káva sú dva najbežnejšie nápoje na svete, ktoré sú k dispozícii takmer všade v rôznych formách. Oba tieto nápoje sa môžu konzumovať kedykoľvek počas dňa a môžu byť horúce alebo studené. Tieto nápoje sa líšia od rastlín, z
  • rozdiel medzi: Rozdiel medzi rozpaky, hanbou a ponižovaním

    Rozdiel medzi rozpaky, hanbou a ponižovaním

    Kľúčový rozdiel : Škoda je bolestivý pocit, ktorý vyvstáva z vedomia, keď robí niečo nevhodné alebo nečestné, sám alebo iným. Rozpačitosť je tiež pocit sebauvedomenia, ktorý vzniká, keď je človek zachytený robiť niečo zlé, hlúpe alebo nezvyčajné v súkromí, zatiaľ čo poníženie je silný pocit mortifikácie. Naše pocity majú vo všeobecnosti úče
  • rozdiel medzi: Rozdiel medzi Alcatel One Touch Idol a Nokia Lumia 620

    Rozdiel medzi Alcatel One Touch Idol a Nokia Lumia 620

    Hlavný rozdiel: Alcatel One Touch Idol je oficiálny mobilný partner pre film Iron Man 3. Je vybavený 4, 7 palcovým IPS LCD kapacitným dotykovým displejom so 16 miliónmi farieb. Displej má rozlíšenie 540 x 960 pixelov. Telefón je napájaný Dual-core 1 GHz MediaTek MTK 6577+ a 512 MB RAM. Jedným z najnovších smartphonov pod značkou Lumia je Nokia Lumia 620. Nokia Lumia 620

Redakcia Choice

Rozdiel medzi hriankovačom a elektrickou rúrou

Kľúčový rozdiel: Hriankovacie pece sú pece, ktoré sú malé elektrické rúry s prednými dverami, odnímateľným drôteným nosičom a odnímateľnou panvicou. Tieto rúry sú často väčšie ako toastovače, ale menšie ako bežné pece. Elektrické pece alebo pece fungujú, rovnako ako názov napovedá, elektrinu. Prevádza elektrickú energiu na