Peamine erinevus: arvutites on binaarpuud puude andmestruktuurid, mis salvestavad andmeid ja võimaldavad kasutajal andmeid algoritmilisel ajal pääseda, neid otsida, sisestada ja kustutada. Erinevus B ja B + puude vahel on see, et B-puus saab võtmeid ja andmeid salvestada nii sise- kui ka lehe sõlmedes, samas kui B + puus saab andmeid ja võtmeid salvestada ainult lehesõlmedes .
Binaarpuud on tasakaalustatud otsingupuud, mis on loodud töötama hästi otsese juurdepääsu sekundaarsetes salvestusseadmetes nagu magnetkettad. Rudolf Bayer ja Ed McCreight leiutasid B-puu kontseptsiooni.
B-puu on üldistatud binaarotsingupuu, kus igal sõlmel võib olla rohkem kui kaks last. Iga B-puu sisemine sõlm sisaldab mitmeid võtmeid. Need võtmed eraldavad väärtused ja moodustavad alampuid. B-puu sisemistel sõlmedel võib olla varieeruv arv lastesõlme, mis on paigutatud eelnevalt määratletud vahemikku. Ajal, kui mis tahes andmed sisestatakse või eemaldatakse mis tahes vastavatest sõlmedest, muutub laste sõlmede arv. Eelnevalt määratletud vahemiku säilitamiseks võib sisemise sõlme ühendada või jagada. B-puus on lubatud mitmed lastesõlmed, mille tõttu tuleb eelnevalt määratletud vahemik säilitada.
Erinevalt teistest ise tasakaalustavatest otsingupuudest ei pea B-puud sageli tasakaalustama. Nende puude sõlmed ei ole alati täis; seega tarbitakse ruume nendes puudes tarbetult, mis viib ruumi raiskamiseni. Konkreetse rakenduse jaoks on tavaliselt kindlaks määratud ainult laste sõlmede arvu alumine ja ülemine piir. Näiteks 2-3-B-puus (mida sageli nimetatakse lihtsalt kui 2-3-puu), võib igas sisemises sõlmes olla ainult 2 või 3 lastesõlme.
Lisaks on B-puu optimeeritud süsteemidele, mis loevad ja kirjutavad suuri andmeplokke. Seda kasutatakse tavaliselt andmebaasides ja failisüsteemides. B-puus hoitakse kõik sõlmed rootoritest samadel tasakaalustussügavustel. Need sügavused suurenevad aeglaselt, kui elementide arv suureneb; selle tulemuseks on, et kõik lehesõlmed on juurest kaugemal veel üks sõlme. Lisaks on B-puud parem võrreldes teiste rakendustega, mis on seotud andmetele juurdepääsu ajaga.
B + puu on n-array puu, millel on sõlm, mis koosneb suurest arvust lastest sõlme kohta. Juur võib olla leht või sõlme, mis sisaldab rohkem kui kahte last. B + puu koosneb juurest, sisemistest sõlmedest ja lehtedest.
B + puu on sama, mis B-puu; ainsaks erinevuseks on see, et B + puus on lisandunud lisa, mis on lisatud lehedega. Erinevalt B-puust sisaldab iga B + puu sõlme ainult võtmeid ja mitte võtmeväärtust paare.
Lisaks mõõdab B + puude tasakaalustustegur või järjekord puu sisemiste sõlmede võimsust, st nende sõlmede arvu, mida nad võivad omada. Sõlme tegelik laste arv on sisemiste sõlmede puhul piiratud. Juur on siiski erand, kuna on lubatud rohkem kui kaks last. Näiteks kui B + puude järjekord on 7, võib igal sisemisel sõlmel (välja arvatud juur) olla 4 kuni 7 last; kui juur võib olla vahemikus 2 kuni 7. B + puu esmane väärtus on andmete salvestamiseks tõhusaks otsinguks plokk-orienteeritud salvestuskontekstis ja eriti failisüsteemides.
B + puu esmane väärtus on andmete salvestamisel ja säilitamisel, nii et andmed ei kao. Seda lähenemist rakendatakse eriti plokk-orienteeritud salvestuskontekstis ja mõnes konkreetses failisüsteemis. Lehed, mis on B + puu kõige enam indekseerivad plokid, on omavahel seotud loendis; seega muudab see plokkide päringute või tellitud iteratsiooni lihtsamaks ja tõhusamaks. Lisaks ei raisata ruumi tegurit B + puudes. B + puu pakub efektiivset eluasemeandmete struktuuri vormi, mis muudab need lihtsaks juurdepääsuks ja salvestamiseks. B + puud on eriti kasulikud andmebaasisüsteemi indeksina, kus andmed tavaliselt asuvad kettal.
B puu ja B + puu võrdlus:
B puu | B + puu | |
Lühikirjeldused | AB puu on organisatsiooni struktuur teabe säilitamiseks ja otsimiseks puude kujul, kus kõik terminalisõlmed on baasist ühesuguses kauguses ning kõigil mitteterminaalsetel sõlmedel on n ja 2 n alampuude või osade vahel (kus n on täisarv). | B + puu on n-massiivne puu, millel on muutuv, kuid sageli suur hulk lapsi sõlme kohta. B + puu koosneb juurest, sisemistest sõlmedest ja lehtedest. Juur võib olla kas kahe või enama lapse leht või sõlm. |
Tuntud ka kui | Tasakaalustatud puu. | B pluss puu. |
Kosmos | O (n) | O (n) |
Otsing | O (log n) | O (log b n) |
Lisa | O (log n) | O (log b n) |
Kustuta | O (log n) | O (log b n) |
Ladustamine | B-puus, otsinguklahvid ja andmed, mis on salvestatud sise- või lehesõlmedesse. | B + puus salvestatakse andmeid ainult lehe sõlmedes. |
Andmed | Kolme kaupluse lehesõlmed osutavad pigem dokumentidele kui tegelikele kirjetele. | Puu lehed sõlmed salvestavad tegeliku rekordi, mitte viited dokumentidele. |
Kosmos | Need puud hävitavad ruumi | Puud ei raiska ruumi. |
Lehekülgede sõlmede funktsioon | B-puus ei saa lehesõlm salvestada linkide loendit. | B + puus tellitakse lehesõlmede andmed järjestikku seotud loendis. |
Otsimine | Siin muutub B-puu otsimine raskeks, kuna andmeid ei leita lehesõlmes. | Siin on igasuguste andmete otsimine B + puus väga lihtne, sest kõik andmed leitakse lehtteedes. |
Otsi kättesaadavust | Siin B-puus ei ole otsing B + -puuga võrreldes nii lihtne. | Siin on B + puus otsimine lihtne. |
Redundant võti | Nad ei salvesta üleliigset otsinguklahvi. | Nad salvestavad üleliigse otsinguklahvi. |
Rakendused | Need on vanemad versioonid ja ei ole nii soodsad kui B + puud. | Paljud andmebaasisüsteemi rakendajad eelistavad B + puidu struktuurilist lihtsust. |
