B+-trær og indekser

Bredde-først, ikke dybde-først

Et binærtre i RAM har O(log₂ N) dybde — flott. Men på disk er hver tre-traversering en ny diskaksess, og log₂(1 000 000) = 20 disk-aksesser per oppslag er uakseptabelt. Løsningen: lag en node som er stor nok til å fylle en hel blokk, slik at den kan ha mange barn.

Hva skiller B+ fra et vanlig B-tre?

• I et B-tre kan en intern node holde data. Søket terminerer når det treffer nøkkelen, hvor som helst i treet.
• I et B+-tre ligger alle data i bladene. Interne noder er bare separatorer — guide nedover. Hver søk går alltid til bladet.

Hvorfor er det bedre? To grunner:

1. Mindre interne noder — siden de bare holder nøkler + pekere, får de plass til mer per blokk → høyere fanout → kortere tre.
2. Bladene kan lenkes sammen — sortert sekvens av alle records. Etter ett tre-oppslag kan vi følge bladlenkene sidelengs for å hente et range billig. Det kan ikke et B-tre gjøre.

Rot, interne noder, blader

Reglene som holder treet balansert

• Hver node er én blokk (én disk-aksess å lese).
• Orden d (= max antall pekere): ⌈d/2⌉ ≤ antall pekere ≤ d.
• Dermed har hver intern node ⌈d/2⌉ − 1 til d − 1 nøkler.
• Roten er unntak: kan ha så lite som 2 pekere (ellers ville ikke et tomt tre vært lov).
• Alle blader er på samme nivå — det gjør treet selvbalanserende.

Hva ligger i bladene? Avhenger av cluster-typen

Topp ned, alltid til bladet

Søkalgoritmen er ren rekursjon: i hver node, sammenlign nøkkelen med separator-nøklene og gå til riktig barn. Når du når bladet, gjør binærsøk innenfor blokken.

function search(node, key):
  if node er blad:
      return binarySearch(node.keys, key)   // finn key eller posisjon
  else:
      i ← første index hvor key < node.keys[i]   // (eller node.keys.length)
      return search(node.children[i], key)

Tre eksempler — på samme tre

Range-scan — den virkelige superkraften

For WHERE empno BETWEEN 14 AND 35:

1. Tre-traversering ned til 14 (3 blokker).
2. Lever ut alle records i bladet ≥ 14.
3. Følg leaf-link til neste blad. Lever ut. Stopp når en nøkkel > 35 møtes.

Total kostnad: 3 + ⌈(antall treff)/(records per blad)⌉ blokker. Helt minimal — vi leser bare blader som inneholder treff.

Bygg ditt eget B+-tre

Sett inn nøkler og søk i treet under. Treet har orden 4 — hver blokk holder maks 3 nøkler. Når en blokk fylles, splittes den; hvis dette propagerer opp til roten, vokser treet med ett nivå.

Tips: Kjør Bratsbergs eksempel-sekvens trinnvis (start med tilbakestilling, deretter sett inn 2, 5, 14, 22, 27, 33, 3, 7, 16, 24 i denne rekkefølgen) — du vil se nøyaktig de samme trinnene som notatene viser.

Splitting fra blad og oppover

Algoritmen i fire trinn

1. Søk nedover treet til riktig blad (akkurat som ved oppslag).
2. Plass i bladet? Sett inn sortert. Ferdig.
3. Ikke plass? Splitt bladet i to. Halvparten av nøklene flytter til ny høyre blokk. Lenk inn i bladkjeden.
4. «Promote» den minste nøkkelen i den nye blokken til foreldrenoden. Hvis foreldrenoden også blir full → splitt rekursivt. Hvis roten splittes → nytt rotnivå.

Det viktige skillet: copy vs move

Når en bladnode splittes, kopieres separator-nøkkelen oppover — den må fortsatt finnes i bladet (det er der dataene ligger).

Når en intern node splittes, flyttes den midterste nøkkelen oppover — den var bare en separator likevel, og det er ingen vits å duplisere den.

Hvorfor splittes blokken før innsettingen, ikke etter?

Bratsberg påpeker en nyanse: ved en split flyttes halvparten av nøklene til den nye blokken, deretter settes den nye nøkkelen inn i den blokken som har plass. Dette virker rart — hvorfor ikke bare splitte de 4 nøklene jevnt etterpå?

Grunnen er recovery og update-håndtering:

• Splittet er en strukturell endring, uavhengig av selve innsettingen.
• Hvis ein VARCHAR-update gjør en eksisterende record større slik at blokken blir for liten, må vi splitte uten at det er en ny nøkkel involvert.
• Recovery-loggen kan da ha ett record for splitten og ett for innsettingen — separat redo og atomicitet.

Underflow → låne eller slå sammen

Sletting er teorien speilbildet av innsetting. I praksis tar de fleste DBMS-er en enklere vei.

Den teoretiske algoritmen

1. Søk til bladet, fjern nøkkelen.
2. Hvis bladet fortsatt har ≥ ⌈d/2⌉−1 nøkler — ferdig.
3. Ellers: underflow. To valg: låne en nøkkel fra et søsken (redistribusjon), eller slå sammen med søsken (merge).
4. Merge fjerner en separator i foreldrenoden — som kan forårsake underflow der. Propagér oppover.
5. Hvis roten ender med kun ett barn — den nye roten er det barnet. Treet krymper.

Det praktiske kompromisset

Mange DBMS-er hopper over hele underflow-logikken og bare lar slettede slots være tomme. En egen compaction-tråd kjører i bakgrunnen og slår sammen blokker når de blir altfor tomme. Andre DBMS-er bruker delete-at-empty-block: blokken slettes kun når den er helt tom. Forenkler ekstremt mye men gir litt dårligere fyllingsgrad.

Hvor ligger dataen — i indeksen eller ved siden av?

Én oppføring per record, eller per blokk

To begreper som ofte forveksles, men dekker forskjellige ting:

Når nøkkelen består av flere attributter

En sammensatt nøkkel som (dno, age) sorterer leksikografisk: først på dno, deretter på age innenfor samme dno. Dette har enorm konsekvens for hvilke spørringer som er raske.

Regelen

Plasser det mest selektive attributtet først — eller mer presist: det som har likhets-betingelse i WHERE må komme før det som har range-betingelse.

For WHERE dno = 4 AND age > 50:

• Med (dno, age): traverser ned til (4, 50), skann sidelengs så lenge dno=4 og age stiger. Lite I/O.
• Med (age, dno): traverser ned til (51, …), skann sidelengs alle records med age > 50, filtrer ut de som har dno=4. Mye mer I/O.

Eksempelet du må kunne på eksamen

Dette er Bratsbergs kanoniske eksempel. Lær å regne det — alle eksamensoppgaver om B+-trær følger samme mønster.

1 · Heapfil

2 · Clustered B+-tre

3 · Heap + unclustered B+-tre

Kostnader for ulike spørringer

Du kan nå:

• Tegne et B+-tre etter en gitt innsettingssekvens, med splittinger.
• Regne høyde, antall blokker og forventet I/O for likhets- og range-spørringer.
• Velge mellom clustered og unclustered indeks ut fra spørringsmønstre.
• Forklare når sparse indeks er mulig og når den ikke er det.
• Designe en komposittnøkkel ut fra hvilke spørringer som skal være raske.