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 jedovatými a jedovatými

    Rozdiel medzi jedovatými a jedovatými

    Kľúčový rozdiel: Venózne organizmy majú špeciálnu žľaza a časť tela, ako sú zuby, ktoré sa používajú na podanie toxínu do tela obete. Jedovaté stvorenie, organizmus alebo rastlina nemajú špeciálne žľazy na produkciu tohto toxínu, sú produkované ich normálnymi telesnými procesmi. Termíny "jedovaté"
  • populárne porovnania: Rozdiel medzi strojom a motorom

    Rozdiel medzi strojom a motorom

    Hlavný rozdiel: Stroje spotrebúvajú energiu vyrobenú motormi. Slovo "stroj" je odvodené z latinského slova "machina". Rovnaký význam teraz vyjadruje odvodená termínová machinácia. Myšlienku jednoduchého stroja vznikol grécky filozof Archimedes . Okrem toho gréckí filozofi definovali klasické päť jednoduchých strojov, ktoré boli použité na hrubé vypočítanie mechanických výhod. Heron Alexandrie vo svojej
  • populárne porovnania: Rozdiel medzi Phonics a syntetická Phonics

    Rozdiel medzi Phonics a syntetická Phonics

    Kľúčový rozdiel: Phonic je efektívna metóda používaná na výučbu zručností čítania. Využíva vzťah medzi abecedami a zvukov, ktoré vytvorili. Syntetická Phonika je prístup, pri ktorom sa najprv vyučujú zvuky písmen a kombinácií písmen, a neskôr sa metóda učí tvoriť úplné slová. Syntetická Phonika je teda jedným
  • populárne porovnania: Rozdiel medzi baktériami a vírusom

    Rozdiel medzi baktériami a vírusom

    Kľúčový rozdiel: Baktérie sú jednobunkové a prokaryotické organizmy. Replikujú sa asexuálne. Môžu byť škodlivé, rovnako ako prínosné; závisí od druhu baktérií. Na druhej strane vírusy sú neživé patogény a sú acelulárne. Virus tiež potrebuje hostiteľskú bunku na reprodukciu. Väčšina vírusov nemá žiadny u
  • populárne porovnania: Rozdiel medzi RISC a CISC

    Rozdiel medzi RISC a CISC

    Hlavný rozdiel : Hlavný rozdiel medzi RISC a CISC je v počte výpočtových cyklov, ktoré každý z ich pokynov prijíma. Rozdiel v počte cyklov je založený na zložitosti a cieli ich pokynov. Termín RISC znamená "Počítač so zmenšeným počtom inštrukcií". Ide o stratégiu návrhu CPU založenú na jednoduchých inštrukciách a rýchlom výkone. RISC je malý alebo zmenšený súb
  • populárne porovnania: Rozdiel medzi iPhone 5S a iPhone 5C

    Rozdiel medzi iPhone 5S a iPhone 5C

    Hlavný rozdiel: iPhone 5S je najnovší smartphone od spoločnosti Apple. Je vybavený Apple OS 7 a je k dispozícii v 3 farbách: biela, čierna a zlatá. IPhone 5C je levnejšou variantou zariadenia iPhone 5S od spoločnosti Apple Inc. 10. septembra 2013 oznámila spoločnosť Apple najnovšie modely telefónov: iPhone 5S a iPhone 5C. Vedúci pracovn
  • populárne porovnania: Rozdiel medzi Dubajom a Spojenými arabskými emirátmi

    Rozdiel medzi Dubajom a Spojenými arabskými emirátmi

    Kľúčový rozdiel: Dubaj je mesto v Spojených arabských emirátoch a nachádza sa v rovnakom emiráte, zatiaľ čo Spojené arabské emiráty (SAE) sú arabské krajiny, ktoré sa nachádzajú na juhovýchode Arabského polostrova v Perzskom zálive a pozostávajú zo siedmich emirates vrátane Dubaja. Niekedy sa uvádza, že D
  • populárne porovnania: Rozdiel medzi akné a vady

    Rozdiel medzi akné a vady

    Kľúčový rozdiel: Akné je ochorenie kože, ktoré je charakterizované prítomnosťou pupienkov, čiernych hláv a bielych hláv. Poškodenie je stav pokožky, pri ktorej sa pokožka odfarbí alebo tmavšia. Mnoho ľudí považuje akné aj vady za rovnaké. Obaja sa však odvolávajú na rôzne veci. Akné je choroba alebo por
  • populárne porovnania: Rozdiel medzi Aikido a Hapkido

    Rozdiel medzi Aikido a Hapkido

    Hlavný rozdiel: Aikido je japonský, zatiaľ čo Hapkido je kórejská forma bojového umenia. "Aikido" je japonské formy bojového umenia, ktoré vyvinula Morihei Ueshiba (1883 - 1969) v roku 1942. Je to forma sebaobrany, v ktorej sa učiaci učia veľké pohyby a obracania, aby ich chránili. Názov "a

Redakcia Choice

Rozdiel medzi Priezvisko a Priezvisko

Kľúčový rozdiel: Priezvisko je známe aj ako priezvisko. Priezvisko je priezvisko, ktoré osoba zdieľa s ostatnými rodinnými príslušníkmi. Všeobecne sa prechádza z jednej generácie na druhú. Priezvisko tiež všeobecne označuje priezvisko. Vo väčšine spoločností je priezvisko, ktoré nasleduje po prvom mena. Táto logika určovania p