B medis duomenų struktūroje: ieškokite, įterpkite, ištrinkite operacijos pavyzdį

Turinys:

Anonim

Kas yra B medis?

„B Tree“ yra savaime subalansuota duomenų struktūra, paremta konkrečiu taisyklių rinkiniu, kaip greičiau ieškoti, įterpti ir ištrinti duomenis. Norėdami tai pasiekti, laikydamiesi šių taisyklių sukurkite B medį.

B medis yra ypatinga medžio rūšis duomenų struktūroje. 1972 m. Šį metodą pirmą kartą pristatė McCreightas, o Bayeris pavadino jį „Height Balanced m-way Search Tree“. Tai padeda jums išsaugoti duomenis, surūšiuotus ir leidusius atlikti įvairias operacijas, pvz., Įterpimą, paiešką ir ištrynimą, per trumpesnį laiką.

Šioje „B-Tree“ pamokoje sužinosite:

  • Kas yra B medis?
  • Kodėl verta naudoti „B-Tree“
  • B medžio istorija
  • Paieškos operacija
  • Įterpti operaciją
  • Ištrinti operaciją

B-Tree taisyklės

Čia yra svarbios „B_Tree“ kūrimo taisyklės

  • Visi lapai bus sukurti tuo pačiu lygiu.
  • B medis nustatomas pagal laipsnio skaičių, kuris taip pat vadinamas „tvarka“ (nurodomas išorinio veikėjo, pvz., Programuotojo), vadinamas
    m
    pirmyn. Vertė
    m
    priklauso nuo disko, kuriame pirmiausia yra duomenys, bloko dydžio.
  • Kairiojo mazgo potemio reikšmės bus mažesnės nei dešiniojoje potemio pusėje. Tai reiškia, kad mazgai taip pat rūšiuojami didėjimo tvarka iš kairės į dešinę.
  • Didžiausias antrinių mazgų, šakninio mazgo ir jo antrinių mazgų skaičius gali būti apskaičiuojamas pagal šią formulę:
    m - 1
    Pavyzdžiui:
    m = 4max keys: 4 - 1 = 3

  • Kiekviename mazge, išskyrus šakninį, turi būti minimalus raktas
    [m/2]-1
    Pavyzdžiui:
    m = 4min keys: 4/2-1 = 1
  • Maksimalus vaikų mazgų, kuriuos mazgas gali turėti, skaičius yra lygus jo laipsniui, kuris yra
    m
  • Mažiausias vaikas, kurį mazgas gali turėti, yra pusė eilės, kuri yra m / 2 (imama lubų vertė).
  • Visi mazgo raktai yra rūšiuojami didėjančia tvarka.

Kodėl verta naudoti „B-Tree“

Čia pateikiamos B-Tree naudojimo priežastys

  • Sumažina disko skaitymų skaičių
  • B medžius galima lengvai optimizuoti, kad būtų galima koreguoti jo dydį (tai yra vaikų mazgų skaičių) pagal disko dydį
  • Tai specialiai sukurta didelių duomenų kiekio apdorojimo technika.
  • Tai naudingas duomenų bazių ir failų sistemų algoritmas.
  • Geras pasirinkimas, kai reikia skaityti ir rašyti didelius duomenų blokus

B medžio istorija

  • Duomenys laikomi diske blokais, šie duomenys, patekę į pagrindinę atmintį (arba RAM), vadinami duomenų struktūra.
  • Jei yra didžiuliai duomenys, ieškant vieno įrašo diske reikia perskaityti visą diską; tai padidina laiko ir pagrindinės atminties suvartojimą dėl didelio prieigos prie disko ir duomenų dydžio.
  • Norėdami tai įveikti, sukuriamos indeksų lentelės, kurios įrašo įrašų nuorodą pagal blokus, kuriuose jie gyvena. Tai žymiai sumažina laiko ir atminties sąnaudas.
  • Kadangi turime didžiulius duomenis, galime sukurti kelių lygių rodyklių lenteles.
  • Daugiapakopį indeksą galima sukurti naudojant „B Tree“, kad duomenys būtų rūšiuojami savaime subalansuotai.

Paieškos operacija

Paieškos operacija yra paprasčiausia „B Tree“ operacija.

Taikomas šis algoritmas:

  • Leiskite raktui (reikšmei) ieškoti „k“.
  • Pradėkite paiešką nuo šaknies ir rekursyviai pereikite žemyn.
  • Jei k yra mažesnis už šaknies vertę, ieškokite kairiajame potemyje, jei k didesnis už šaknies vertę, ieškokite dešiniajame medyje.
  • Jei mazge yra rastas k, paprasčiausiai grąžinkite mazgą.
  • Jei k nerandamas mazge, didesniu raktu pereikite prie vaiko.
  • Jei medyje nerandama k, grąžiname NULL.

Įterpti operaciją

Kadangi „B Tree“ yra savaime balansuojantis medis, jūs negalite priversti įdėti rakto į bet kurį mazgą.

Taikomas šis algoritmas:

  • Atlikite paieškos operaciją ir raskite tinkamą įterpimo vietą.
  • Įdėkite naują raktą tinkamoje vietoje, bet jei mazge jau yra maksimalus raktų skaičius:
  • Mazgas kartu su naujai įterptu raktu atsiskirs nuo vidurinio elemento.
  • Vidurinis elementas taps tėvais kitiems dviem vaiko mazgams.
  • Mazgai turi pertvarkyti raktus didėjimo tvarka.

PATARIMAS

Tai nėra tiesa apie įterpimo algoritmą:

Kadangi mazgas yra pilnas, todėl jis suskaidys ir bus įterpta nauja reikšmė

Ankstesniame pavyzdyje:

  • Ieškokite tinkamoje rakto pozicijoje mazge
  • Įdėkite raktą į tikslinį mazgą ir patikrinkite, ar nėra taisyklių
  • Ar po įterpimo mazgas turi daugiau nei lygu minimaliam raktų skaičiui, kuris yra 1? Šiuo atveju taip, taip yra. Patikrinkite kitą taisyklę.
  • Ar įterpus mazgas turi daugiau nei maksimalų raktų skaičių, kuris yra 3? Šiuo atveju ne, taip nėra. Tai reiškia, kad B medis nepažeidžia jokių taisyklių, o įterpimas baigtas.

Ankstesniame pavyzdyje:

  • Mazgas pasiekė maksimalų raktų skaičių
  • Mazgas suskaidys, o vidurinis raktas taps likusių dviejų mazgų šakniniu mazgu.
  • Jei klavišų skaičius yra lyginis, vidurinis mazgas bus pasirinktas kairiuoju arba dešiniuoju.

Ankstesniame pavyzdyje:

  • Mazge yra mažiau nei maks. Raktų
  • 1 įterpiamas šalia 3, tačiau pažeidžiama didėjimo tvarka
  • Norėdami tai išspręsti, raktai yra rūšiuojami

Panašiai 13 ir 2 galima lengvai įterpti į mazgą, nes jie įvykdo mažiau nei maks. Raktų taisyklę mazgams.

Ankstesniame pavyzdyje:

  • Mazgo raktai yra lygūs maks.
  • Raktas įterpiamas į tikslinį mazgą, tačiau jis pažeidžia raktų maks. Taisyklę.
  • Tikslinis mazgas yra padalintas, o vidurinis raktas kairiuoju šališkumu dabar yra naujų vaiko mazgų tėvas.
  • Nauji mazgai išdėstyti didėjimo tvarka.

Panašiai, remiantis pirmiau pateiktomis taisyklėmis ir atvejais, likusias reikšmes galima lengvai įterpti į B medį.

Ištrinti operaciją

Ištrynimo operacijoje yra daugiau taisyklių nei įterpimo ir paieškos operacijose.

Taikomas šis algoritmas:

  • Paleiskite paieškos operaciją ir suraskite tikslinį raktą mazguose
  • Taikomos trys sąlygos, atsižvelgiant į tikslinio rakto vietą, kaip paaiškinta tolesniuose skyriuose

Jei tikslinis raktas yra lapo mazge

  • Tikslas yra lapų mazge, daugiau nei min raktai.
    • Tai ištrynus, „B Tree“ nuosavybė nebus pažeista
  • Tikslas yra lapų mazge, jame yra min raktų mazgai
    • Tai ištrynus bus pažeista „B Tree“ nuosavybė
    • Tikslinis mazgas gali skolintis raktą iš tiesioginio kairiojo mazgo arba tiesioginio dešiniojo mazgo (brolio ar sesers)
    • Brolis pasakys „ taip“, jei turi daugiau nei minimalų raktų skaičių
    • Raktas bus pasiskolintas iš pirminio mazgo, maksimali vertė bus perkelta tėvui, maksimali pirminio mazgo vertė bus perkelta į tikslinį mazgą ir pašalins tikslinę vertę
  • Tikslas yra lapų mazge, bet nė vienas brolis ar sesuo neturi daugiau nei min. Raktų
    • Ieškokite rakto
    • Susijungimas su broliais ir seserimis ir minimalus tėvų mazgų skaičius
    • Bendras raktų skaičius dabar bus didesnis nei min
    • Tikslinis raktas bus pakeistas minimaliu pirminiu mazgu

Jei tikslinis raktas yra vidiniame mazge

  • Arba pasirinkite tvarkingą pirmtaką arba tvarkingą įpėdinį
  • Jei pirmtakas yra tvarkingas, bus pasirinktas maksimalus raktas iš jo kairiojo potemio
  • Tvarkingo įpėdinio atveju bus pasirinktas minimalus raktas iš jo dešiniojo potemio
  • Jei tikslinio rakto pirmtakas tvarkingas, turi daugiau nei min raktus, tik tada jis gali tikslinį raktą pakeisti maksimaliu tvarkos pirmtaku
  • Jei tikslinio rakto pirmtakas turi ne daugiau kaip min raktus, ieškokite eilinio įpėdinio minimalaus rakto.
  • Jei tikslinio rakto pirmtakas ir įpėdinis turi mažiau nei min raktus, sujunkite pirmtaką ir įpėdinį.

Jei tikslinis raktas yra šakniniame mazge

  • Pakeiskite maksimaliu eilės pirmtako poskyrio elementu
  • Jei po ištrynimo taikinyje yra mažiau nei min raktai, tada tikslinis mazgas skolinsis didžiausią vertę iš savo brolio per brolio ar sesers tėvus.
  • Maksimalią tėvų vertę ims taikinys, bet su brolio ir sesers maksimalios vertės mazgais.

Dabar supraskime ištrinimo operaciją su pavyzdžiu.

Pirmiau pateiktoje diagramoje pateikiami įvairūs B medžio ištrynimo atvejai. Šis „B-Tree“ yra 5 eilės, o tai reiškia, kad mažiausias vaikų mazgų skaičius, kurį gali turėti bet kuris mazgas, yra 3, o maksimalus antrinių mazgų skaičius, kurį gali turėti bet kuris mazgas, yra 5. Kadangi mažiausias ir maksimalus raktų skaičius yra bet kuriame mazge gali būti atitinkamai 2 ir 4.

Ankstesniame pavyzdyje:

  • Tikslinis mazgas turi tikslinį raktą, kurį reikia ištrinti
  • Tikslinio mazgo raktai yra daugiau nei minimalūs
  • Tiesiog ištrinkite raktą

Ankstesniame pavyzdyje:

  • Tikslinio mazgo raktai yra lygūs minimaliems raktams, todėl jo negalima tiesiogiai ištrinti, nes tai pažeis sąlygas

Dabar šioje diagramoje paaiškinta, kaip ištrinti šį raktą:

  • Tikslinis mazgas skolins raktą iš tiesioginio brolio, šiuo atveju, tvarkingo pirmtako (kairysis brolis), nes jis neturi tvarkingo įpėdinio (dešinysis brolis).
  • Didžiausia užsakyto pirmtako vertė bus perkelta tėvams, o tėvai maksimalią vertę perkels į tikslinį mazgą (žr. Toliau pateiktą diagramą)

Šiame pavyzdyje parodyta, kaip ištrinti raktą, kuriam reikalinga vertė, iš eilės įpėdinio.

  • Tikslinis mazgas skolinsis raktą iš tiesioginio brolio, šiuo atveju tvarkingo įpėdinio (dešiniojo brolio / sesers), nes jo pirmtako (kairysis brolis) raktai yra lygūs minimaliems raktams.
  • Minimali eilinio įpėdinio vertė bus perkelta tėvams, o tėvai maksimalią vertę perkels į tikslinį mazgą.

Toliau pateiktame pavyzdyje tikslinis mazgas neturi nė vieno brolio ar sesers, galinčio suteikti raktą tiksliniam mazgui. Todėl reikia sujungti.

Žr. Tokio rakto ištrynimo procedūrą:

  • Sujunkite tikslinį mazgą su bet kuriuo iš jo tiesioginių brolių ir seserų kartu su tėvų raktu
    • Pasirenkamas raktas iš pirminio mazgo, kurį broliai ir seserys turi tarp dviejų sujungiamų mazgų
  • Ištrinkite tikslinį raktą iš sujungto mazgo

Ištrinti operacijos pseudo kodą

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

Išvestis :

Didžiausias elementas išbraukiamas iš B medžio.

Santrauka:

  • „B Tree“ yra savaime subalansuota duomenų struktūra, skirta geriau ieškoti, įterpti ir ištrinti duomenis iš disko.
  • B medį reguliuoja nurodytas laipsnis
  • B Medžių klavišai ir mazgai išdėstyti didėjimo tvarka.
  • „B Tree“ paieškos operacija yra paprasčiausia, kuri visada pradedama nuo šaknies ir pradedama tikrinti, ar tikslinis raktas yra didesnis ar mažesnis už mazgo vertę.
  • „B Tree“ įterpimo operacija yra gana išsami, kuri pirmiausia suranda tinkamą tikslinio rakto įterpimo vietą, ją įterpia, įvertina „B Tree“ pagrįstumą skirtingais atvejais ir atitinkamai pertvarko „B Tree“ mazgus.
  • „B Tree“ ištrynimo operacija pirmiausia ieško ištrinamo tikslinio rakto, jį ištrina, įvertina galiojimą pagal kelis atvejus, pvz., Minimalius ir maksimalius tikslinio mazgo raktus, brolius ir seseris bei tėvus.