Galvenā atšķirība: datoros binārie koki ir koku datu struktūras, kas glabā datus, un ļauj lietotājam piekļūt, meklēt, ievietot un dzēst datus algoritmiskā laikā. Atšķirība starp B un B + koku ir tā, ka B kokā atslēgas un dati var tikt glabāti gan iekšējos, gan lapu mezglos, savukārt B + kokā datus un taustiņus var saglabāt tikai lapu mezglos .
Binārie koki ir sabalansēti meklēšanas koki, kas paredzēti darbam tiešās piekļuves sekundārajās atmiņas ierīcēs, piemēram, magnētiskajos diskos. Rudolfs Bayers un Ed McCreight izgudroja B-koka jēdzienu.
B-koks ir vispārināts binārs meklēšanas koks, kurā jebkuram mezglam var būt vairāk nekā divi bērni. Katrs iekšējais mezgls B kokā satur vairākus taustiņus. Šīs atslēgas atdala vērtības un tālāk veido apakškokus. Iekšējiem mezgliem B-kokā var būt mainīgs skaits bērnu mezglu, kas ir izvietoti iepriekš noteiktā diapazonā. Laikā, kad jebkurš attiecīgais mezgls tiek ievietots vai noņemts, mainās bērnu mezglu skaits. Lai saglabātu iepriekš definētu diapazonu, iekšējie mezgli var tikt savienoti vai sadalīti. B kokā ir atļauta virkne bērnu mezglu, kuru dēļ ir jāsaglabā iepriekš noteiktais diapazons.
B-kokiem nav nepieciešams līdzsvarot bieži, atšķirībā no citiem pašbalsojošiem meklēšanas kokiem. Šo koku mezgli ne vienmēr ir pilni; tātad šie koki šajos kokos tiek patērēti nevajadzīgi, radot telpu izšķērdēšanu. Konkrētai īstenošanai parasti tiek fiksētas tikai bērnu mezglu skaita apakšējās un augšējās robežas. Piemēram, 2-3 B-kokā (kas bieži tiek saukts par 2-3 kokiem), katrā iekšējā mezglā var būt tikai 2 vai 3 bērnu mezgli.
Turklāt B-koks ir optimizēts sistēmām, kas lasa un raksta lielus datu blokus. To parasti izmanto datu bāzēs un failu sistēmās. B kokā visi mezgli tiek saglabāti vienā un tajā pašā balansēšanas dziļumā no sakņu mezgliem. Šie elementi palielinās lēni, palielinoties elementu skaitam; tā rezultātā visi lapu mezgli ir vēl viens mezgls tālāk no saknes. Turklāt B-koki ir izdevīgāki, salīdzinot ar citām ieviešanām attiecībā uz laiku, kas nepieciešams, lai piekļūtu datiem.
B + koks ir n-masīvs ar mezglu, kas sastāv no liela skaita bērnu katrā mezglā. Sakne var būt lapa vai mezgls, kas satur vairāk nekā divus bērnus. B + koku veido sakne, iekšējie mezgli un lapas.
B + koks ir tāds pats kā B koks; Vienīgā atšķirība ir tā, ka B + kokā apakšā ir pievienots papildu līmenis ar saistītām lapām. Atšķirībā no B koka, katrs mezgls B + kokā satur tikai atslēgas, nevis atslēgu vērtības.
Turklāt balansēšanas faktors vai B + koku secība mēra koka iekšējo mezglu kapacitāti, ti, to mezglu skaitu, kas tiem var būt. Iekšējo mezglu faktiskais bērnu skaits mezglā ir ierobežots. Tomēr sakne ir izņēmums, jo ir atļauts vairāk nekā divu bērnu skaits. Piemēram, ja B + koku secība ir 7, katram iekšējam mezglam (izņemot sakni) var būt no 4 līdz 7 bērniem; kamēr saknei var būt no 2 līdz 7. B + koku primārā vērtība ir datu glabāšanai efektīvai atgūšanai bloka orientētā uzglabāšanas kontekstā un jo īpaši failu sistēmās.
B + koka primārā vērtība ir datu glabāšanā un uzturēšanā, lai dati netiktu pazaudēti. Šī pieeja ir īpaši piemērota uz bloka orientētu uzglabāšanas kontekstu un dažās konkrētās failu sistēmās. Lapas, kas ir B + koka indeksa bloki, bieži ir saistītas viena ar otru saistītā sarakstā; tādējādi tas padara diapazona vaicājumus vai pasūtīto iterāciju vienkāršāk un efektīvāk. Turklāt B + kokos netiek izšķiests kosmosa faktors. B + koks nodrošina efektīvu mājokļu datu struktūras formātu, kas padara tos vienkāršus piekļuvei un glabāšanai. B + koki ir īpaši noderīgi kā datu bāzes sistēmas indekss, kur dati parasti atrodas uz diska.
Salīdzinājums starp B koku un B + koku:
B koks | B + koks | |
Īsie tīmekļa apraksti | AB koks ir organizatoriska struktūra informācijas glabāšanai un izgūšanai koka formā, kurā visi termināla mezgli atrodas vienā attālumā no bāzes, un visiem ne-termināla mezgliem ir starp n un 2 n apakškokiem vai rādītājiem (kur n ir vesels skaitlis). | B + koks ir n-masīvs ar mainīgu, bet bieži vien lielu bērnu skaitu uz mezglu. B + koku veido sakne, iekšējie mezgli un lapas. Sakne var būt vai nu lapa, vai mezgls ar diviem vai vairākiem bērniem. |
Zināms arī kā | Līdzsvarots koks. | B plus koks. |
Kosmoss | O (n) | O (n) |
Meklēt | O (log n) | O (log b n) |
Ievietot | O (log n) | O (log b n) |
Dzēst | O (log n) | O (log b n) |
Glabāšana | B kokā meklēšanas taustiņi un dati, kas saglabāti iekšējos vai lapu mezglos. | B + kokā dati tiek glabāti tikai lapu mezglos. |
Dati | Trīs veikalu lapu mezgli norāda uz ierakstiem, nevis reāliem ierakstiem. | Koka lapu mezgli uzglabā faktisko ierakstu, nevis norādes uz ierakstiem. |
Kosmoss | Šie koki atstāj vietu | Tur koki nav atkritumi. |
Lapu mezglu funkcija | B kokā lapu mezgls nevar saglabāt, izmantojot saistīto sarakstu. | B + kokā lapu lapu mezglu dati tiek sakārtoti secīgā saistītā sarakstā. |
Meklēšana | Šeit meklēšana B-kokā kļūst sarežģīta, jo lapu mezglā nevar atrast datus. | Šeit jebkura datu meklēšana B + kokā ir ļoti vienkārša, jo visi dati ir atrodami lapu mezglos. |
Meklēt pieejamību | Šeit B kokā meklēšana nav tik vienkārša, salīdzinot ar B + koku. | Šeit B + kokā meklēšana kļūst vienkārša. |
Redundanta atslēga | Viņi nesaglabā lieku meklēšanas taustiņu. | Tie saglabā lieks meklēšanas taustiņu. |
Programmas | Tie ir vecāki un nav izdevīgi salīdzinājumā ar B + kokiem. | Daudzi datu bāzes sistēmas īstenotāji dod priekšroku B + koka strukturālajai vienkāršībai. |
