B+-trær og indekser

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

Et binærtre (hver node har 2 barn) i RAM har log₂ N nivåer — 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 (ingen rad-data), får de plass til mer per blokk → høyere fanout → kortere tre.
2. Bladene (de nederste nodene, der dataene faktisk ligger) kan lenkes sammen i en 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 = maks antall pekere (barn) hver node kan ha. Hver node må holde minst halve kapasiteten: ⌈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 (halverende søk i sortert array — log₂-tid) 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.

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?

Notatene påpeker en nyanse (se kompendium-kap. 10): 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 en 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 (loggen brukt til å gjenopprette etter krasj — kap 8) kan da ha én post for splitten og én for innsettingen — separat redo og atomicitet.

Verdt å huske: rekkefølgen påvirker hvilken nøkkel som propageres

Når den nye nøkkelen havner i midten av bladet, gir konvensjonen «splitt først, sett inn etterpå» et annet resultat enn «sett inn virtuelt, splitt midt på de 7». Eksempel: full løvblokk [10, 20, 30, 40, 50, 60] (kapasitet 6), insert 35.

• Bratsberg-konvensjon (splitt først): halvparten flyttes → [10, 20, 30] og [40, 50, 60]. 35 settes inn i venstre (35 < 40) → [10, 20, 30, 35] og [40, 50, 60]. Minste i høyre = 40, kopieres opp.
• Alternativ (sett inn først, splitt midt på 7): de 7 nøklene blir [10, 20, 30, 35, 40, 50, 60], splittet midt på → [10, 20, 30] og [35, 40, 50, 60]. Minste i høyre = 35, kopieres opp.

Begge er gyldige B+-trær, men de er ikke samme algoritme. På denne kursen følger vi Bratsberg — så 40 er det som propageres opp i eksempelet over. Innsetting-før-splitt-i-midten er en vanlig fallgrop fordi mange engelskspråklige lærebøker bruker den varianten.

Bygg ditt eget B+-tre

Nå som du kjenner splitt-algoritmen, prøv den selv. Sett inn nøkler og se hvordan blader fylles, splittes og hvordan separator-nøkler propagerer oppover. Treet har orden 4 — hver blokk holder maks 3 nøkler.

Tips: Kjør eksempel-sekvensen fra notatene 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 kompendiet viser.

Praktisk håndtering av sletting

Pensum behandler ikke detaljert sletting — notatene skriver eksplisitt at sletting ikke vises i detalj («we do not show deletions in B+-trees»). Du skal kjenne hovedideen om hvordan slettinger håndteres i praksis.

• Compaction-tråd: Vanligst i praksis. En bakgrunnsprosess kompaktérer nivåer i treet og fjerner tomme blokker. Bruker-spørringer fortsetter mens dette skjer.
• Delete-at-empty-block: Forskning har vist at det er nok å slette blokken først når den er helt tom — du trenger ikke en egen management-tråd. Forenkler implementasjon, gir litt dårligere fyllingsgrad.

Hvor ligger dataen — i indeksen eller ved siden av?

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

En sammensatt nøkkel som (dno, age) sorterer leksikografisk (som ord i en ordbok — 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

Når skriveytelse betyr alt

B+-trær er kongen for blandet read/write. Men når data strømmer inn raskere enn B+-treet klarer å absorbere — typisk i Big Data-systemer og NoSQL-databaser (ikke-relasjonelle datalagre, som Cassandra og MongoDB) — bruker man LSM-trær (Log-Structured Merge tree).

Hovedidé: skriv stort, sjeldent

• Memtable i RAM — alle nye inserts/updates havner først her, sortert (typisk implementert som en skiplist, en sortert datastruktur).
• WAL (Write-Ahead Log) — hver endring skrives også til en sekvensiell logg på disk for durability (varig lagring — endringer overlever krasj).
• Når memtable blir full: flush til disk som en SST-fil (Sorted String Table). SST-filer er immutable (uforanderlige — skrives én gang, slettes hele).
• Compaction (samling) i bakgrunnen: SST-filer flettes nedover i nivåer (L0 = nyeste/minste filer rett under memtable, L1 = nivået under, osv.) og dupliserte/slettede entries fjernes.

Resultatet er at de fleste skrivinger først treffer RAM, og disk-skrivinger skjer i store, sekvensielle bolker. Lav write amplification + høyere komprimering sammenlignet med B+-trær.

B+-tre vs LSM-tre

Brukt i Google BigTable / LevelDB, Apache HBase, RocksDB, MyRocks (MySQL-storage engine hos Facebook), Apache Cassandra, MongoDB WiredTiger, og SQLite (utvidelse).

Det studenter blander sammen i B+-tre-kapittelet

Disse feilene koster nesten alltid 5 % på eksamen. Les listen etter du har lest 01–10 over; hver punkt nedenfor svarer til ett konkret eksamen-traff fra de siste fem år.

1. 2/3 fyllgrad gjelder også interne noder. Mange bruker 2/3 på blader men 100 % på interne. Riktig: fanout = floor(blokkstr · 2/3 / indekspost-størrelse). Bruk samme regel på alle nivåer.
2. Indekspost-størrelse: nøkkel + RID i unclustered, nøkkel + BlockId i interne noder. Bladene i en unclustered B+ inneholder (nøkkel, RID). Interne noder (clustered eller unclustered) inneholder (nøkkel, BlockId) — pekere til underliggende blokker, ikke til records. RID er typisk 12 byte; BlockId 8. Bruk feil og du svarer 5 % feil.
3. Clustered er ikke raskere på SELECT *. Et clustered B+-tre har 2/3 fyllgrad og treet legger overhead på topp; flere blokker enn et heap-fil. Clustered shines på WHERE-, BETWEEN- og ORDER BY-spørringer, ikke på fullt scan.
4. Unclustered + range = potensiell katastrofe. Hvert indeks-treff peker til en tilfeldig blokk i heapen. Hvis 20 % av radene matcher → 20 % × N random aksesser. Ofte er full scan billigere — DBMS-en velger derfor å ignorere indeksen. Husk: clustered koster høyde + ⌈treff/leafcap⌉, unclustered koster høyde + treff.
5. Index-only scan: når kolonnen er indeksnøkkelen. SELECT navn ... ORDER BY navn med unclustered B+ på navn: optimal er å skanne kun bladnivået i indeksen (data ligger der). SELECT epost ... ORDER BY navn: må også til heapen for hver record. Denne distinksjonen er ren eksamenkruttkjegle.
6. Antall nivåer = antall blokker for likhetsoppslag i clustered. Hvis treet har 3 nivåer, koster ett likhetsoppslag i clustered B+ 3 blokker (ikke 4). Bladet inneholder selve recorden. I unclustered koster det 3 + 1 = 4 (en ekstra heap-aksess).
7. Komposittnøkkel-rekkefølge er prefiks-stiv. Indeks (A, B) støtter WHERE A=?, WHERE A=? AND B=?, og ORDER BY A, B — men ikke WHERE B=? alene. Det er som ordboka: sortert på første bokstav først.
8. Range-spørring: hvilken kolonne skal komme sist? For WHERE customerId = ? AND date BETWEEN ? AND ?, bygg indeksen som (customerId, date) — likhets-attributtet først, range-attributtet sist. Da kan B+-treet finne kunden (et punkt i treet) og scanne sidelengs i bladet for date-rangen. Bytt om → må scanne alle datoer.
9. Splitt forplanter seg oppover. Når en bladblokk splittes ved insert, oppdateres foreldrenoden med en ny separator + ny barn-peker. Hvis foreldrenoden også blir full, splittes den, og det forplanter seg helt opp til rota i verste fall. Dette er hvorfor en insert kan være dyr (men sjeldent er det).
10. Bladlenker er encrypted to leaf level only. Range-scan etter tre-traversering går sidelengs via leaf-link-pekere. Vi går ikke opp i treet igjen mellom blader. Dette er en kjernegrunn til at B+ slår vanlig B-tre på range — i et B-tre må du gå opp og ned for hver blad-overgang.

MCQ — i samme stil som vår 2025

Eksamen i 2026 er kun flervalg, og oppgavene rundt B+-trær og access paths utgjør den største regnedelen av eksamen. Disse 8 spørsmålene har distraktorer som matcher de vanligste regnefeilene fra Bratsberg-eksamenene. Svar — og bli en sikker B+-regner.

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.
• Designe en komposittnøkkel ut fra hvilke spørringer som skal være raske.
• Forklare når LSM-trær slår B+-trær — og hvorfor.