B STROM v dátovej štruktúre: príklad vyhľadávania, vkladania, mazania

Obsah:

Anonim

Čo je to strom B?

B Tree je samovyvažujúca dátová štruktúra založená na konkrétnom súbore pravidiel pre vyhľadávanie, vkladanie a mazanie údajov rýchlejším a pamäťovo efektívnym spôsobom. Na dosiahnutie tohto cieľa sa pri vytváraní stromu B dodržiavajú nasledujúce pravidlá.

B-strom je špeciálny druh stromu v dátovej štruktúre. V roku 1972 túto metódu prvýkrát predstavil McCreight a spoločnosť Bayer ju pomenovala Výškovo vyvážený m-way Search Tree. Pomôže vám to uchovať dáta zoradené a umožnené rôzne operácie, ako je vkladanie, vyhľadávanie a mazanie, za kratší čas.

V tomto výukovom programe B-Tree sa dozviete:

  • Čo je to strom B?
  • Prečo používať B-Tree
  • História stromu B.
  • Vyhľadávacia operácia
  • Vložiť operáciu
  • Operácia odstránenia

Pravidlá pre B-strom

Tu sú dôležité pravidlá pre vytváranie B_Tree

  • Všetky listy budú vytvorené na rovnakej úrovni.
  • B-strom je určený počtom stupňov, ktoré sa tiež nazývajú „poradie“ (určené externým aktérom, napríklad programátorom), označované ako 
    m
    ďalej. Hodnota 
    m
    závisí od veľkosti bloku na disku, na ktorom sú primárne umiestnené dáta.
  • Ľavý podstrom uzla bude mať menšie hodnoty ako pravá strana podstromu. To znamená, že uzly sú tiež zoradené vzostupne zľava doprava.
  • Maximálny počet podradených uzlov, koreňový uzol aj jeho podradené uzly sa môže vypočítať podľa tohto vzorca: 
    m - 1
    Napríklad: 
    m = 4max keys: 4 - 1 = 3

  • Každý uzol, okrem root, musí obsahovať minimálne kľúčov 
    [m/2]-1
    Napríklad: 
    m = 4min keys: 4/2-1 = 1
  • Maximálny počet podradených uzlov, ktoré uzol môže mať, sa rovná jeho stupňu, ktorý je 
    m
  • Minimálny počet detí, ktoré uzol môže mať, je polovica objednávky, čo je m / 2 (použije sa maximálna hodnota).
  • Všetky kľúče v uzle sú zoradené podľa vzrastajúceho poradia.

Prečo používať B-Tree

Tu sú dôvody použitia B-Tree

  • Znižuje počet načítaní vykonaných na disku
  • Stromy B možno ľahko optimalizovať tak, aby sa upravila ich veľkosť (to je počet podradených uzlov) podľa veľkosti disku
  • Je to špeciálne navrhnutá technika na manipuláciu s objemným objemom údajov.
  • Je to užitočný algoritmus pre databázy a súborové systémy.
  • Dobrá voľba, keď sa rozhodnete pre čítanie a zápis veľkých blokov údajov

História stromu B.

  • Dáta sa na disk ukladajú v blokoch, tieto údaje sa po zavedení do hlavnej pamäte (alebo RAM) nazývajú dátová štruktúra.
  • V prípade obrovských údajov vyžaduje prehľadanie jedného záznamu na disku prečítanie celého disku; toto zvyšuje čas a spotrebu hlavnej pamäte v dôsledku vysokej frekvencie prístupu na disk a veľkosti dát.
  • Aby sa to prekonalo, vytvárajú sa indexové tabuľky, ktoré ukladajú referencie záznamov na základe blokov, v ktorých sa nachádzajú. To drasticky znižuje čas a spotrebu pamäte.
  • Pretože máme obrovské údaje, môžeme vytvárať viacúrovňové indexové tabuľky.
  • Viacúrovňový index je možné navrhnúť pomocou stromu B na udržiavanie údajov v automatickom vyvažovaní.

Vyhľadávacia operácia

Vyhľadávacia operácia je najjednoduchšia operácia na strome B.

Použije sa nasledujúci algoritmus:

  • Kľúč (hodnotu), ktorý má byť vyhľadaný, nechajte vyhľadať pomocou „k“.
  • Začnite hľadať od koreňa a rekurzívne prechádzajte dole.
  • Ak je k menšie ako koreňová hodnota, vyhľadajte ľavý podstrom, ak k je väčšie ako koreňová hodnota, vyhľadajte pravý podstrom.
  • Ak má uzol nájdené k, uzol jednoducho vráťte.
  • Ak sa k v uzle nenachádza, prechádzajte smerom dole k dieťaťu pomocou väčšieho kľúča.
  • Ak k nie je v strome nájdené, vrátime NULL.

Vložiť operáciu

Pretože strom B je samovyvažujúci strom, nemôžete vynútiť vloženie kľúča iba do ktoréhokoľvek uzla.

Použije sa nasledujúci algoritmus:

  • Spustite operáciu vyhľadávania a nájdite príslušné miesto vloženia.
  • Vložte nový kľúč na správne miesto, ale ak má uzol už maximálny počet kľúčov:
  • Uzol sa spolu s novo vloženým kľúčom rozdelí od stredného prvku.
  • Prostredný prvok sa stane rodičom pre ďalšie dva podradené uzly.
  • Uzly musia kľúče usporiadať vzostupne.

TIP

O algoritme vkladania neplatí toto:

Pretože je uzol plný, rozdelí sa a potom sa vloží nová hodnota

Vo vyššie uvedenom príklade:

  • Vyhľadajte kľúč na príslušnej pozícii v uzle
  • Vložte kľúč do cieľového uzla a skontrolujte pravidlá
  • Má uzol po vložení viac ako minimálny počet kľúčov, čo je 1? V takom prípade áno. Skontrolujte ďalšie pravidlo.
  • Má uzol po vložení viac ako maximálny počet kľúčov, čo sú 3? V takom prípade nie. To znamená, že strom B neporušuje žiadne pravidlá a vkladanie je dokončené.

Vo vyššie uvedenom príklade:

  • Uzol dosiahol maximálny počet kľúčov
  • Uzol sa rozdelí a prostredný kľúč sa stane koreňovým uzlom zvyšných dvoch uzlov.
  • V prípade párneho počtu klávesov bude stredný uzol vybraný predpätím vľavo alebo vpravo.

Vo vyššie uvedenom príklade:

  • Uzol má menej ako max. Kľúčov
  • 1 sa vkladá vedľa 3, ale je porušené pravidlo vzostupného poradia
  • Aby sa to napravilo, sú kľúče zoradené

Podobne je možné do uzla ľahko vložiť 13 a 2, pretože pre uzly spĺňajú pravidlo pravidla pre kľúče menšie ako max.

Vo vyššie uvedenom príklade:

  • Uzol má kľúče rovnajúce sa maximálnemu počtu kľúčov.
  • Kľúč sa vloží do cieľového uzla, ale porušuje pravidlo maximálneho počtu kľúčov.
  • Cieľový uzol je rozdelený a prostredný kľúč so skreslením zľava je teraz rodičom nových podriadených uzlov.
  • Nové uzly sú usporiadané vzostupne.

Podobne na základe vyššie uvedených pravidiel a prípadov možno ostatné hodnoty ľahko vložiť do stromu B.

Operácia odstránenia

Operácia mazania má viac pravidiel ako operácie vkladania a vyhľadávania.

Použije sa nasledujúci algoritmus:

  • Spustite operáciu vyhľadávania a nájdite cieľový kľúč v uzloch
  • Podľa umiestnenia cieľového kľúča sa uplatnili tri podmienky, ktoré sú vysvetlené v nasledujúcich častiach

Ak je cieľový kľúč v uzle listu

  • Cieľ je v listovom uzle, viac ako min. Kľúčov.
    • Jeho vymazanie neporuší vlastníctvo stromu B
  • Cieľ je v listovom uzle, má minimálne kľúčové uzly
    • Jeho vymazaním dôjde k porušeniu vlastníctva stromu B.
    • Cieľový uzol si môže požičať kľúč z bezprostredného ľavého uzla alebo okamžitého pravého uzla (súrodenec)
    • Súrodenec povie áno, ak má viac ako minimálny počet kľúčov
    • Kľúč bude vypožičaný z nadradeného uzla, maximálna hodnota sa prenesie do nadradeného prvku, maximálna hodnota nadradeného uzla sa prenesie do cieľového uzla a cieľová hodnota sa odstráni.
  • Cieľ je v listovom uzle, ale žiadni súrodenci nemajú viac ako minimálny počet kľúčov
    • Vyhľadajte kľúč
    • Zlúčte sa so súrodencami a minimom rodičovských uzlov
    • Celkový počet kľúčov bude teraz viac ako min
    • Cieľový kľúč bude nahradený minimom nadradeného uzla

Ak je cieľový kľúč vo vnútornom uzle

  • Buď si vyberte, predchodca v poradí alebo nasledovník v poradí
  • V prípade predchodcu v poradí bude vybraný maximálny kľúč z jeho ľavého podstromu
  • V prípade nástupcu v poradí bude vybraný minimálny kľúč z jeho pravého podstromu
  • Ak má predchodca cieľového kľúča v poradí viac ako klávesov min, iba potom môže cieľový kľúč nahradiť maximom predchodcu v poradí
  • Ak predchodca cieľového kľúča v poradí nemá viac ako min. Kľúčov, vyhľadajte minimálny kľúč nástupcu v poradí.
  • Ak majú predchodca a následník v poradí cieľového kľúča kľúče menej ako min, zlúčte predchodcu a nástupcu.

Ak je cieľový kľúč v koreňovom uzle

  • Nahraďte ju maximálnym prvkom podstromu predchodcu v poradí
  • Ak má po odstránení cieľ menej ako min. Kľúčov, bude si cieľový uzol požičiavať maximálnu hodnotu od svojho súrodenca prostredníctvom súrodencovho rodiča.
  • Maximálnu hodnotu rodiča bude brať cieľ, ale s uzlami maximálnej hodnoty súrodenca.

Teraz si ukážeme operáciu odstránenia.

Vyššie uvedený diagram zobrazuje rôzne prípady operácie odstránenia v B-strome. Tento B-strom je rádu 5, čo znamená, že minimálny počet podradených uzlov, ktoré môže mať akýkoľvek uzol, je 3, a maximálny počet podradených uzlov, ktoré môže mať akýkoľvek uzol, je 5. Zatiaľ čo minimálny a maximálny počet kľúčov v ľubovoľnom uzle môžu mať 2, respektíve 4.

Vo vyššie uvedenom príklade:

  • Cieľový uzol má cieľový kľúč na odstránenie
  • Cieľový uzol má viac ako minimum kľúčov
  • Kľúč jednoducho vymažete

Vo vyššie uvedenom príklade:

  • Cieľový uzol má kľúče rovnajúce sa minimálnemu počtu kľúčov, takže ho nemožno priamo vymazať, pretože by to porušilo podmienky

Nasledujúci diagram teraz vysvetľuje, ako tento kľúč odstrániť:

  • Cieľový uzol si požičia kľúč od bezprostredného súrodenca, v tomto prípade predchodcu v poradí (ľavý súrodenec), pretože nemá žiadneho následníka v poradí (pravého súrodenca)
  • Maximálna hodnota predchodcu inorder sa prenesie do nadradeného objektu a nadradený parameter prenesie maximálnu hodnotu do cieľového uzla (pozri diagram nižšie).

Nasledujúci príklad ilustruje, ako odstrániť kľúč, ktorý vyžaduje hodnotu od svojho nasledovníka v poradí.

  • Cieľový uzol si požičia kľúč od bezprostredného súrodenca, v tomto prípade od nasledovníka v poradí (pravého súrodenca), pretože má predchodcu v poradí (ľavého súrodenca), ktorý má kľúče rovnaké ako minimálne kľúče.
  • Minimálna hodnota následníka v poradí sa prenesie na nadradenú položku a nadradená osoba prenesie maximálnu hodnotu do cieľového uzla.

V príklade nižšie cieľový uzol nemá žiadneho súrodenca, ktorý by mohol dať jeho kľúč cieľovému uzlu. Preto je potrebné zlúčenie.

Pozrite si postup odstránenia takéhoto kľúča:

  • Zlúčte cieľový uzol s ktorýmkoľvek z jeho bezprostredných súrodencov spolu s nadradeným kľúčom
    • Je vybraný kľúč z nadradeného uzla, ktorý je súrodencom medzi dvoma zlučujúcimi sa uzlami
  • Odstráňte cieľový kľúč zo zlúčeného uzla

Vymazanie pseudo kódu operácie

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Výstup :

Najväčší prvok je odstránený z B-stromu.

Zhrnutie:

  • B Tree je samovyvažujúca dátová štruktúra pre lepšie vyhľadávanie, vkladanie a mazanie údajov z disku.
  • Strom B je regulovaný stanoveným stupňom
  • B Kľúče a uzly stromu sú usporiadané vzostupne.
  • Vyhľadávacia operácia stromu B je najjednoduchšia operácia, ktorá vždy začína od koreňa a začína kontrolovať, či je cieľový kľúč väčší alebo menší ako hodnota uzla.
  • Operácia vloženia stromu B je dosť podrobná, ktorá najskôr nájde vhodnú pozíciu vloženia pre cieľový kľúč, vloží ju, vyhodnotí platnosť stromu B proti rôznym prípadom a potom podľa toho reštrukturalizuje uzly stromu B.
  • Operácia mazania stromu B najskôr vyhľadá cieľový kľúč, ktorý sa má vymazať, vymaže ho, vyhodnotí platnosť na základe niekoľkých prípadov, ako sú minimálne a maximálne kľúče cieľového uzla, súrodencov a rodiča.