B KOKS datu struktūrā: meklēšanas, ievietošanas, dzēšanas darbības piemērs

Satura rādītājs:

Anonim

Kas ir B koks?

B Tree ir pašbalansējoša datu struktūra, kuras pamatā ir īpašs noteikumu kopums datu meklēšanai, ievietošanai un dzēšanai ātrāk un atmiņā efektīvāk. Lai to panāktu, izveidojot B koku, tiek ievēroti šādi noteikumi.

B-koks ir īpaša veida koks datu struktūrā. 1972. gadā šo metodi pirmo reizi ieviesa Makreits, un Baiers to nosauca par Height Balanced m-way Search Tree. Tas palīdz īsākā laikā saglabāt datus, kas sakārtoti un ļāva veikt dažādas darbības, piemēram, ievietošanu, meklēšanu un dzēšanu.

Šajā B-Tree apmācībā jūs uzzināsiet:

  • Kas ir B koks?
  • Kāpēc izmantot B-Tree
  • B koka vēsture
  • Meklēšanas darbība
  • Ievietot darbību
  • Dzēst darbību

B-Tree noteikumi

Šeit ir svarīgi noteikumi B_Tree izveidošanai

  • Visas lapas tiks izveidotas vienā līmenī.
  • B-koku nosaka pēc pakāpes skaita, ko sauc arī par "kārtību" (ko norādījis ārējs dalībnieks, piemēram, programmētājs), ko sauc par 
    m
    uz priekšu. Vērtība 
    m
    atkarīgs no tā diska bloka lieluma, kurā dati galvenokārt atrodas.
  • Mezgla kreisajam apakškokam būs mazākas vērtības nekā apakškoka labajā pusē. Tas nozīmē, ka arī mezgli tiek sakārtoti augošā secībā no kreisās uz labo.
  • Maksimālo pakārtoto mezglu skaitu, saknes mezglu, kā arī tā pakārtotos mezglus var aprēķināt pēc šīs formulas: 
    m - 1
    Piemēram: 
    m = 4max keys: 4 - 1 = 3

  • Katrā mezglā, izņemot saknes, jābūt vismaz 
    [m/2]-1
    Piemēram: 
    m = 4min keys: 4/2-1 = 1
  • Maksimālais mezglā pieejamo bērnu mezglu skaits ir vienāds ar tā pakāpi, kas ir 
    m
  • Minimālais bērnu skaits, kas var būt mezglā, ir puse no kārtas, kas ir m / 2 (tiek ņemta griestu vērtība).
  • Visi mezgla taustiņi tiek kārtoti pieaugošā secībā.

Kāpēc izmantot B-Tree

Šeit ir B-Tree izmantošanas iemesli

  • Samazina diskā veikto lasījumu skaitu
  • B kokus var viegli optimizēt, lai pielāgotu to izmēru (tas ir, bērnu mezglu skaitu) atbilstoši diska izmēram
  • Tas ir īpaši izstrādāts paņēmiens, kā apstrādāt lielu daudzumu datu.
  • Tas ir noderīgs algoritms datu bāzēm un failu sistēmām.
  • Laba izvēle izvēlēties, kad runa ir par lielu datu bloku lasīšanu un rakstīšanu

B koka vēsture

  • Dati tiek glabāti diskā blokos, šos datus, ievedot galvenajā atmiņā (vai RAM), sauc par datu struktūru.
  • Milzīgu datu gadījumā, meklējot vienu ierakstu diskā, ir jāizlasa viss disks; tas palielina laika un galvenās atmiņas patēriņu, pateicoties lielam diska piekļuves biežumam un datu lielumam.
  • Lai to pārvarētu, tiek izveidotas indeksu tabulas, kas saglabā ierakstu atsauci uz blokiem, kuros tie atrodas. Tas krasi samazina laika un atmiņas patēriņu.
  • Tā kā mums ir milzīgi dati, mēs varam izveidot daudzlīmeņu indeksu tabulas.
  • Daudzlīmeņu indeksu var noformēt, izmantojot B Tree, lai datus sakārtotu pašbalansējošā veidā.

Meklēšanas darbība

Meklēšanas operācija ir vienkāršākā B Tree darbība.

Tiek izmantots šāds algoritms:

  • Ļaujiet atslēgu (vērtību) meklēt pēc "k".
  • Sāciet meklēšanu no saknes un rekursīvi virzieties uz leju.
  • Ja k ir mazāks par saknes vērtību, meklējiet kreiso apakškoku, ja k ir lielāks par saknes vērtību, meklējiet labo apakškoku.
  • Ja mezglā ir atrasts k, vienkārši atgrieziet mezglu.
  • Ja k nav atrodams mezglā, ar lielāku atslēgu dodieties uz leju pie bērna.
  • Ja k nav atrodams kokā, mēs atgriežam vērtību NULL.

Ievietot darbību

Tā kā B koks ir pašbalansējošs koks, nevar piespiest ievietot atslēgu jebkurā mezglā.

Piemēro šādu algoritmu:

  • Palaidiet meklēšanas darbību un atrodiet atbilstošo ievietošanas vietu.
  • Ievietojiet jauno atslēgu pareizajā vietā, bet, ja mezglā jau ir maksimālais atslēgu skaits:
  • Mezgls kopā ar nesen ievietotu atslēgu sadalīsies no vidējā elementa.
  • Vidējais elements kļūs par vecāku pārējiem diviem bērna mezgliem.
  • Mezgliem ir jāpārkārto atslēgas augošā secībā.

PADOMS

Par ievietošanas algoritmu nav taisnība:

Tā kā mezgls ir pilns, tāpēc tas sadalīsies, un pēc tam tiks ievietota jauna vērtība

Iepriekš minētajā piemērā:

  • Meklējiet atslēgai atbilstošo pozīciju mezglā
  • Ievietojiet atslēgu mērķa mezglā un pārbaudiet kārtulas
  • Vai pēc ievietošanas mezglā ir vairāk nekā vienāds ar minimālo atslēgu skaitu, kas ir 1? Šajā gadījumā jā, tā arī notiek. Pārbaudiet nākamo kārtulu.
  • Vai pēc ievietošanas mezglā ir vairāk par maksimālo atslēgu skaitu, kas ir 3? Šajā gadījumā nē, tā nav. Tas nozīmē, ka B koks nepārkāpj nevienu noteikumu un ievietošana ir pabeigta.

Iepriekš minētajā piemērā:

  • Mezgls ir sasniedzis maksimālo atslēgu skaitu
  • Mezgls sadalīsies, un vidējā atslēga kļūs par pārējo divu mezglu saknes mezglu.
  • Pāra skaita gadījumā vidējais mezgls tiks izvēlēts ar kreiso vai labo slīpumu.

Iepriekš minētajā piemērā:

  • Mezglā ir mazāk par maksimālo taustiņu
  • 1 tiek ievietots blakus 3, bet tiek pārkāpts augošā secības noteikums
  • Lai to novērstu, atslēgas tiek sakārtotas

Līdzīgi 13 un 2 var viegli ievietot mezglā, jo tie izpilda mazāku nekā maksimālo atslēgu noteikumu mezgliem.

Iepriekš minētajā piemērā:

  • Mezglā ir atslēgas, kas vienādas ar maksimālajām atslēgām.
  • Atslēga tiek ievietota mērķa mezglā, taču tā pārkāpj maksimālo atslēgu likumu.
  • Mērķa mezgls ir sadalīts, un vidējais taustiņš ar kreiso aizspriedumu tagad ir jauno bērnu mezglu vecāks.
  • Jaunie mezgli ir sakārtoti augošā secībā.

Līdzīgi, pamatojoties uz iepriekš minētajiem noteikumiem un gadījumiem, pārējās vērtības var viegli ievietot B kokā.

Dzēst darbību

Dzēšanas operācijai ir vairāk noteikumu nekā ievietošanas un meklēšanas operācijām.

Piemēro šādu algoritmu:

  • Palaidiet meklēšanas darbību un mezglos atrodiet mērķa atslēgu
  • Trīs nosacījumi tika piemēroti, pamatojoties uz mērķa atslēgas atrašanās vietu, kā paskaidrots nākamajās sadaļās

Ja mērķa atslēga atrodas lapu mezglā

  • Mērķis ir lapu mezglā, vairāk nekā min taustiņi.
    • Izdzēšot, netiks pārkāpts B Tree īpašums
  • Mērķis atrodas lapu mezglā, tajā ir min galvenie mezgli
    • Izdzēšot, tiks pārkāpts B Tree īpašums
    • Mērķa mezgls var aizņemties atslēgu no tiešā kreisā mezgla vai tiešā labā mezgla (brālis vai māsa)
    • Brālis vai māsa teiks jā, ja tam ir vairāk nekā minimālais atslēgu skaits
    • Atslēga tiks aizņemta no vecāka mezgla, maksimālā vērtība tiks pārsūtīta vecākam, vecāka mezgla maksimālā vērtība tiks pārsūtīta uz mērķa mezglu un noņemt mērķa vērtību
  • Mērķis atrodas lapu mezglā, bet nevienam brālim vai māsai nav vairāk par min taustiņu
    • Meklēt atslēgu
    • Apvienošana ar brāļiem un māsām un vecāku mezglu minimums
    • Atslēgu kopsumma tagad būs lielāka par min
    • Mērķa atslēga tiks aizstāta ar vecāku mezgla minimumu

Ja mērķa atslēga atrodas iekšējā mezglā

  • Vai nu izvēlieties kārtīgu priekšgājēju, vai kārtīgu pēcteci
  • Gadījumā, ja priekšgājējs ir kārtībā, tiks izvēlēts maksimālais taustiņš no tā kreisās apakškokas
  • Kārtīgas pēctecības gadījumā tiks izvēlēta minimālā atslēga no tās labās apakškokas
  • Ja mērķa atslēgas kārtīgajam priekšgājējam ir vairāk nekā min taustiņi, tikai tad tas var aizstāt mērķa atslēgu ar kārtības priekšgājēja maksimumu
  • Ja mērķa atslēgas kārtīgajam priekšgājējam nav vairāk par min atslēgām, meklējiet kārtības pārņēmēja minimālo atslēgu.
  • Ja mērķa atslēgas kārtīgajam priekšgājējam un pēctecim abiem ir mazāk nekā min, tad apvienojiet priekšgājēju un pēcteci.

Ja mērķa atslēga atrodas saknes mezglā

  • Nomainiet ar kārtējā priekšgājēja apakškoka maksimālo elementu
  • Ja pēc dzēšanas mērķim ir mazāk nekā min atslēgas, mērķa mezgls aizņemsies maksimālo vērtību no sava brāļa / māsas, izmantojot brāļa / māsas vecākus.
  • Vecāku maksimālo vērtību ņems mērķis, bet ar brāļa / māsas maksimālās vērtības mezgliem.

Tagad sapratīsim dzēšanas darbību ar piemēru.

Iepriekš sniegtajā diagrammā ir parādīti dažādi dzēšanas operācijas gadījumi B kokā. Šis B-koks ir 5. kārtas, kas nozīmē, ka minimālais bērnu mezglu skaits, kāds var būt jebkuram mezglam, ir 3, un maksimālais bērnu mezglu skaits, kāds var būt jebkuram mezglam, ir 5. Tā kā jebkura mezgla minimālais un maksimālais atslēgu skaits var būt attiecīgi 2 un 4.

Iepriekš minētajā piemērā:

  • Mērķa mezglā ir mērķa atslēga, kas jāizdzēš
  • Mērķa mezglā ir atslēgas, kas pārsniedz minimālās atslēgas
  • Vienkārši izdzēsiet atslēgu

Iepriekš minētajā piemērā:

  • Mērķa mezglā ir atslēgas, kas vienādas ar minimālajām atslēgām, tāpēc to nevar tieši izdzēst, jo tas pārkāps nosacījumus

Tagad šajā diagrammā ir paskaidrots, kā izdzēst šo atslēgu:

  • Mērķa mezgls aizņemsies atslēgu no tiešā brāļa / māsas, šajā gadījumā kārtīgā priekšgājēja (kreisā brāļa / māsas), jo tam nav neviena kārtīga pēcteca (labā brāļa / māsas)
  • Iekšējā priekšgājēja maksimālā vērtība tiks pārsūtīta uz vecāku, un vecāks pārsūtīs maksimālo vērtību uz mērķa mezglu (skat. Diagrammu zemāk)

Šis piemērs parāda, kā izdzēst atslēgu, kurai nepieciešama vērtība no kārtības pēctecības.

  • Mērķa mezgls aizņemsies atslēgu no tiešā brāļa / māsas, šajā gadījumā kārtīgā pēctecīša (labā brāļa / māsas), jo tā kārtīgajam priekšgājējam (kreisais brālis) ir atslēgas, kas vienādas ar minimālajām atslēgām.
  • Minimālā kārtības pēctecības vērtība tiks pārsūtīta vecākam, un vecāks pārsūtīs maksimālo vērtību mērķa mezglā.

Šajā piemērā mērķa mezglam nav neviena brāļa / māsas, kas varētu nodot savu atslēgu mērķa mezglam. Tāpēc ir nepieciešama apvienošana.

Skatiet šādas atslēgas dzēšanas procedūru:

  • Apvienojiet mērķa mezglu ar kādu no tā tiešajiem brāļiem un māsām kopā ar vecāku atslēgu
    • Tiek izvēlēts vecāku mezgla atslēga, kuru brāļi un māsas atrodas starp diviem apvienotajiem mezgliem
  • Dzēsiet mērķa atslēgu no apvienotā mezgla

Dzēst darbību Pseido kods

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}}

Izeja :

Lielākais elements tiek izdzēsts no B-Tree.

Kopsavilkums:

  • B Tree ir pašbalansējoša datu struktūra, lai labāk meklētu, ievietotu un dzēstu datus no diska.
  • B koku regulē norādītā pakāpe
  • B Koka taustiņi un mezgli ir sakārtoti augošā secībā.
  • B Tree meklēšanas darbība ir vienkāršākā, kas vienmēr sākas no saknes un sāk pārbaudīt, vai mērķa atslēga ir lielāka vai mazāka par mezgla vērtību.
  • B Tree ievietošanas darbība ir diezgan detalizēta, kas vispirms atrod mērķa atslēgai atbilstošu ievietošanas pozīciju, to ievieto, novērtē B Tree derīgumu salīdzinājumā ar dažādiem gadījumiem un pēc tam attiecīgi pārstrukturē B Tree mezglus.
  • B koka dzēšanas darbība vispirms meklē dzēšamo mērķa atslēgu, izdzēš to, novērtē derīgumu, pamatojoties uz vairākiem gadījumiem, piemēram, mērķa mezgla, brāļu un māsu un vecāku minimālajām un maksimālajām atslēgām.