B-drevo reda m je m-smerno iskalno drevo ( urejeno drevo), ki je ali prazno ali višine vsaj 2.

B - drevesa visokega reda se uporabljajo za shranjevanje velikih baz podatkov na zunanjem pomnilniku oziroma trdem disku.

Ker je dostop do ene strani na trdem disku relativno zelo počasen v primerjavi z obdelavo podatkov v hitrem pomnilniku, lahko z B - drevesom visokega reda omogočimo dostop do ogromne količine podatkov z majhnim številom branj strani z diska.

Tipično se koren drevesa hrani v hitrem pomnilniku, eno vozlišče pa ustreza eni strani na disku.

Pogosto se v B-drevesu nahajajo samo naslovi elementov in ne njihova vsebina. Tako lahko povečamo red B-drevesa in močno zmanjšamo višino drevesa in s tem število dostopov do diska.

Slika1: B - drevo reda 5

• B- drevesa so posplošitev 2-3 drevesa.

• Število sinov posameznih vozlišč je navzgor in navzdol omejeno z redom drevesa m in sicer:

  • vsako vozlišče ima ≤ m sinov
  • vsako notranje vozlišče, razen korena, ima ≥ m/2 sinov
  • koren ima vsaj dva sinova, ali pa je list.

• Število elementov je navzgor in navzdol omejeno:

  • vsako vozlišče ima ≤m−1 ključev
  • vsako vozlišče, razen koren, ima ≥ m/2 - 1 elementov
  • notranje vozlišče, ki ima k sinov, vsebuje k −1 elementov

• Vsi listi so na istem nivoju, ki je višina drevesa.

Dokaz: slika1

Koren je na nivoju 1. Ker ima oče nivo 2, so listi A, B, C, D, E, F in G na nivoju 3. Višina je definirana z vozliščem z najvišjim nivojem, ki je 3.

• Podatki v B – drevesu so urejeni v naraščajočem vrstne redu.

vozlišče

pri čemer je k oznaka za elemente vozlišča in p oznaka za kazalce na sinove

Operacije na B - drevesih so:

• iskanje elementa

• dodajanje elementa

• brisanje elementa

Časovna zahtevnost

Vse operacije na B - drevesih se v najslabšem primeru izvedejo v času reda O(logn). Pri tem je m (red drevesa) konstanta.

Z iskanjem elementa v B-drevesu začnemo v korenu. Iskani element zaporedoma primerjamo z elementi v vozlišču dokler ne naletimo na naslednje primere:

• če imamo iskani element v vozlišču z iskanjem zaključimo.

• če iskanega elementa ni v vozlišču:

  • ter pri iskanju naletimo na element, ki je večji od iskanega, iskanje nadaljujemo v poddrevesu, na katerega kaže levi kazalec tega elementa.
  • ter so vsi elementi v tem vozlišču manjši od iskanega, z iskanjem nadaljujemo v poddrevesu, na katerega kaže kazalec zadnjega elementa. če takega poddrevesa ni, iskanega elementa nimamo v drevesu.

Če je pri iskanju elementa m (red drevesa) velik je smiselno (zaradi urejenosti podatkov znotraj vozlišča) ustrezno mesto, kje nadaljujemo iskanje, poiskati z bisekcijo.

V B - drevesu poišči element 27.

1. korak: Z iskanjem začnemo v korenu. Ker v korenu nimamo iskanega elementa 27, ter je element 13 manjši od elementa 27, element iščemo v desnem očetu.

2. korak: Z iskanjem nadaljujemo v očetu. Ker v očetu nimamo iskanega elementa 27, ugotovimo da mora bit podatek v poddrevesu na katerega kaže kazalec med elementoma 26 in 30.

3. korak: Iskanje nadaljujemo na sinovih. Ker imamo v vozlišču iskani element 27 z iskanjem zaključimo.

Element vedno vstavljamo v list drevesa v naraščajočem vrstnem redu. Potek vstavljanja je odvisen od števila elementov v vozlišču:

1. Če je v listu manj kot m-1 elementov , element dodamo v list drevesa tako, da so podatki v listu še vedno v naraščajočem vrstnem redu(prvi element manjši, drugi pa večji od vstavljenega elementa). Tako je postopek končan.

• Zgled: Vstavljanje elementa 7 v B - drevo.

  

2. Če v listu nimamo prostora, da bi dodali element, oziroma z dodajanjem elemnta bi v vozlišče dobili m elementov, vozlišče razbijemo na tri dele. vozlišče s prvimi [m/2]-1 elementi,[m/2]-ti element in vozlišče s preostalimi m-[m/2] elementi. Vozlišče po vstavljanju elementa razpolovimo, pri čemer srednji element vstavimo v očeta. V primeru, da imamo po vstavljanju v očetu preveč elementov postopek ponovimo na očetu. V najslabšem primeru lahko razpolovimo tolikokrat, kolikor je nivo drevesa. V primeru, da razpolovimo koren drevesa dobi drevo nov koren in nivo drevesa se poveča za 1. Postopek se izteče v prvi točki ali v korenu drevesa.

• Zgled: Dodajanje elementa 15 v B - drevo.

V B - drevesu elemente vedno odstranjujemo iz listov. Naletimo lahko na naslednje primere:

1. Če je element, ki ga odstranjujemo v listu. Če je v listu, kjer smo element odstranili še vedno vsaj m/2 -1 elementov je postopek končan .

• Zgled: Brisanje elementa 12 iz B - drevesa.

2. Element, ki ga odstranjujemo je v notranjem vozlišču.Element, ki ga odstranjujemo zamenjamo s predhodnikom tj. maksimalni elementom ustreznega levega poddrevesa ali naslednikom tj. minimalnim elementom ustreznega desnega poddrevesa in ga nato odstranimo. Postopek je zaključek, če je v vozliščih dovolj elementov.

• Zgled: Brisanje elementa 17 iz B - drevesa.

2a) Če vsaj eden od sosednjih bratov tega vozlišča (levi ali desni) vsebuje m/2 ali več elementov, prestavimo enega izmed elementov v očeta, element iz očeta pa prestavimo v vozlišče, ki ima premalo elementov, tako da imata obe vozlišči vsaj m/2-1 elementov

• Zgled: Brisanje elementa 15 iz B - drevesa

2b) Če nobeden od bratov nima vsaj m/2 elementov, potem združimo vozlišče s premajhnim številom elementom, element iz očeta in enega brata v skupno vozlišče.Če ima po tem postopku oče premajhno število elementov se postopek rekurzivno ponovi. Rekurzija se ustavi pri 1 točki ali pri 2a točki, lahko pa tudi pri korenu. V slednjem primeru lahko koren zbrišemo in edino poddrevo postane novo drevo. Torej se v tem primeru nivo drevesa zmanjša za 1.

• Zgled: Brisanje elementa 17 iz B - drevesa

Vstavi elemente 2,26,7,9,29,23,1,20,3,42,12,27,18,25,4,22,11,8,17,13,34,30,16,44 v B - drevo reda 5( to pomeni da ima vozlišče največ 4 elemente in vsa vozlišča razen očeta, morajo imeti vsaj 2 elemanta)

1. korak: Vstavimo prve 4 elemente v koren drevesa v naraščajočem vrstnem redu.

2. korak: Element 29 dodamo na konec vozlišča, ker je to vozlišče že polno(max 4 elementi), srednji element 9 vstavimo v koren.

3. korak: Brez problema lahko vstavimo elemente 23, 1, 20 in 3, saj imamo dovolj prostora (max 4 elemente).

4. korak: Element 42 vstavimo v vozlišče, ker je to vozlišče že polno, srednji element 26 vstavimo v koren. Ker imamo v korenu sedaj 2 elementa, potrebujemo tri sinove. Dodatnega dobimo tako, da razdelimo vozlišče v katerega smo ravno vstavili podatek na dva dela. Razpade ravno tam, od kjer smo izločili srednji element. Vozlišče torej razpade v dva dela.

5. korak: Elemente 12, 27 in 18 lahko vstavimo brez problema.

6. korak: Za element 25 zmanjka prostora, če bi ga dodali bi bil 20 srednji element, zato ga damo v koren. Ker imamo sedaj v korenu 3 elemente, potrebujemo 4 sinove (tri že mamo). Dodatnega dobimo tako, da razdelimo vozlišče v katerega smo ravno vstavili podatek na dva dela. Razpade ravno tam, od kjer smo izločili srednji element. Vozlišče razpade v dva dela.

7. korak: Element 4 bi morali dodati med elementoma 3 in 7. Ker pa bi bilo s tem vozliščem polno, srednji element 3 vstavimo v koren. Ker imamo v korenu 4 elemente sledi razcep, sinove razdelimo na 5 delov.

8. korak: Elemente 22, 11, 8 in 17 lahko vstavimo brez problema.

9. korak: Element 13 bi morali vstaviti v 3 vozlišče, vendar je že povno. Če bi ga vstavili, bi bil element 13 srednji element, zato gre v koren.

Ker so v korenu že štirje elementi, moramo tudi koren razcepiti in določiti novega.

Če bi vstavili število 13, bi bilo število 13 srednji element, zato gre v koren. Ker imamo v korenu sedaj en element, potrebujemo 2 sinova. Sinova dobimo tako, da razdelimo vozlišče v katerega smo ravno vstavili podatek na dva dela. Razpade ravno tam, od kjer smo izločili srednji element. Vozlišče torej razpade v dva dela.

10. korak: Element 34 lahko brez problema vstavimo v drevo.

11. korak: Element 30 bi morali dodati med elementa 29 in 34. Ker pa bi bilo s tem vizlišče polno, srednji element 30 vstavimo v očeta. Ker imamo v očetu sedaj 4 elemente, sinove razdelimo na 5 delov.

12. korak: Element 16 lahko brez problema vstavimo v list drevesa.

Dano imamo B-drevo reda 5. Iz B-drevesa izbriši element 40.

B-drevo reda 5

1. korak: Ker je element, ki ga odstranjujemo notranji, ga po brisanju nadomestimo z predhodnikom (33).

2. korak: Ko prestavimo (33) predhodnika izbrisanega elementa(40) v koren, imamo v vozlišču, kjer smo element prestavili premajhno število elementov. Ker desni brat, vozlišča s premajhnim številom elementov, vsebuje več kot minimalno število elementov , prestavimo element 25 v očeta, element 26 iz očeta pa prestavimo v vozlišče, ki imam premalo elementov, v vozlišče z elementom 27.

Primer je predstavljen s pomočjo filma.

Preveri

Preveri

• Igor Kononenko, Marko Robnik Šikonja: Algoritmi in podatkovne strukture, Ljubljana 2003

http://wiki.fmf.uni-lj.si/wiki/B-drevo

http://penelope.fmf.uni-lj.si/psawiki/images/0/01/BDrevesa.pdf

http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html

http://en.wikipedia.org/wiki/B-tree

http://graph-srv.uni-mb.si/cgai/slo/IA_dokumenti/IA-6-B-drevesa.pdf