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.