Kapittel 6 · 6A · Forelesning 11

Lagring — records, blokker, buffer

Bratsbergs notater kap 1–8. Hvordan en rad faktisk er bytes på en disk — og hvordan DBMS-en ber om dem.

Notatmapping → §01 = Bratsberg-kap 1 · §02 = kap 2 · §03 = kap 3 · §04 = kap 4 · §05 = kap 5 · §06 = kap 6 · §07 = kap 7 · §08 = kap 8. Full mapping →

01 · DBMS-arkitektur

Komponentene i en SQL-DBMS

Et DBMS (databasesystem) er ikke ett program — det er et lag-på-lag-system hvor hver komponent har én jobb. Når du kjører en SQL-spørring vandrer den gjennom hele stakken før den når disken og tilbake. Du møter alle komponentene i tur og orden senere i del 2 — for nå er det selve laginndelingen som er poenget.

SQL-spørring fra klient til disk. SQL-laget kjenner bare rader; alt under buffer pool snakker bare i blokker.

SQL-kompilatoren parser teksten og slår opp i katalogen for å oversette til et internt algebra-tre med konkrete tabell- og kolonnereferanser.
Optimizeren genererer mange mulige kjøreplaner (med ulike join-rekkefølger og indekser) og velger den med lavest forventet diskaksess-kostnad (kalt I/O — Input/Output: lese/skrive blokker) basert på statistikk fra katalogen.
Executoren kjører planen — den ber om blokker fra buffer pool, tar låser via lock manager, og skriver til logfilen hvis den endrer noe.
Buffer pool er det eneste laget som faktisk leser/skriver disk. Alt over snakker kun med buffer pool.

Spørsmål 1 · Lett

Pipelinen har fire lag: SQL-kompilator → optimizer → executor → buffer pool. Hvorfor er det smart at kun buffer pool snakker direkte med disken, i stedet for at hver komponent leser blokker selv?

Fordi disk-I/O er den dominerende kostnaden. Når én komponent eier blokk-cachen, kan flere transaksjoner og spørringer dele samme blokk i RAM, og DBMS-en har ett sentralt sted å håndtere pinning, dirty-flag og WAL-koordinering. Hadde hver komponent lest blokker selv, ville samme blokk blitt lest fra disk flere ganger og ingen ville visst om noen andre var i ferd med å endre den. Separasjonen — at SQL-laget bare snakker rader og bare buffer pool kjenner blokker — er det som gjør at optimizeren bruker katalogen til å velge plan, mens executoren slipper å bekymre seg om hvordan en blokk faktisk hentes.

02 · Device og blokker

Hvor disken slutter og blokkene begynner

Et device er enten en hel disk («raw partition» — disk uten filsystem oppå) eller en stor fil i filsystemet. DBMS-en deler denne lange byte-strømmen inn i blokker (også kalt sider/pages) — sammenhengende biter, typisk 4–32 KiB store. Blokken er DBMS-ens grunnleggende lese- og skrive-enhet mot disk: når DBMS-en trenger én rad, henter den hele blokken raden ligger i (en diskaksess). Hver blokk får et nummer kalt en BlockId.

HDD — rotating disk

Mekaniske armer søker fysisk til riktig sektor. Random seek: ~10 ms. Sekvensiell I/O kan være 100× raskere enn random.

SSD — flash

Ingen mekaniske deler. Random read: ~100 µs. Skriving krever at flash-cellen først nullstilles, og en liten endring kan tvinge ny-skrivning av en større enhet (kalt write amplification). Begrenset levetid pr. celle.

Hvordan en BlockId er bygget opp

BlockId-en kombinerer hvilken disk og hvor i disken. Med 4 byte: 1 byte for deviceId + 3 byte for offset (posisjonen — hvor i disken, talt i blokker fra start) → 2²⁴ blokker per device. Med 16 KiB blokker blir det 256 GiB per device. 8-byte BlockIds spenner over alt vi trenger.

Spørsmål 2 · Lett

Hvorfor velger DBMS-er typisk en blokkstørrelse på 4–32 KiB i stedet for å lese mindre enheter — for eksempel en enkelt rad om gangen?

Disker er optimalisert for store sekvensielle overføringer. Selve seek-tiden (på HDD) eller flash-controllerens fixed cost (på SSD) er den dominerende kostnaden. Når du først er der, er det nesten gratis å lese mer. Å hente 16 KiB tar nesten samme tid som å hente 1 byte. Større blokker → bedre amortisering av seek-kostnaden.

Spørsmål 2b · Lett

En BlockId er bygd som (deviceId, offset). Hvorfor er det smart å adressere blokker logisk slik — i stedet for å bruke en absolutt byte-posisjon i en stor fil?

Fordi det skjuler hvor data faktisk ligger fysisk. DeviceId-en lar DBMS-en spre lagringen over flere disker uten at resten av systemet trenger å vite om det. Offset-en gir direkte adresse til en blokk, og operativsystemet/filsystemet oversetter til faktisk fysisk plassering. SQL-laget over snakker rader; lagringslaget snakker BlockIds; og hva som ligger hvor på den fysiske disken kan endres uten at noe annet brytes.

03 · Record-format

Tre måter å pakke en rad

En record (rad) er én rad i tabellen, lagret som en sekvens bytes inne i en blokk. Hver record består av flere felt (kolonneverdier som empno, name, age). Hvordan disse bytene legges ved siden av hverandre avhenger av datatypene.

Når en tabell har kun fixed-length attributter (INT, CHAR(N), DATE — alle med kjent og fast lengde), ligger hvert felt på fast offset (samme byte-posisjon i hver record). Da er det enkelt å plukke ut feltet — bare hopp til riktig posisjon. Men så kommer VARCHAR (variabel-lengde tekst)…

Format 1 — Fixed length

Format 2 — Record vector (variable length)

Format 3 — Delimiter

Row store vs column store

Tradisjonell DBMS bruker row store: hele raden som én record. Bra for OLTP-arbeidslast (Online Transaction Processing — typiske webapper med mange små inserts/updates på enkeltrader). Column store lagrer hver kolonne for seg — bra for analytiske queries (SUM(salary), AVG(age)) der man kun trenger få kolonner men mange rader. Komprimerer også bedre fordi like verdier ligger sammen.

Spørsmål 3 · Middels

Du har en tabell Person(name VARCHAR(50), age INT). Hvorfor kan ikke fixed-length-formatet brukes direkte?

VARCHAR betyr at navnet kan være alt fra 0 til 50 tegn — så faktisk lengde varierer mellom rader. Hvis vi reserverer 50 byte uansett, sløser vi diskplass for korte navn. Med record vector eller delimiter pakker vi tett. Alternativt kan VARCHAR-feltet nullpaddes til 50 byte for å bevare fixed-length-egenskapen — det gjør noen DBMS-er.

Spørsmål 4 · Middels

Når lønner det seg å bruke column store fremfor row store?

For analytiske spørringer som leser få kolonner men mange rader: SELECT AVG(salary) FROM Employee. I row store må DBMS-en lese alle kolonner i hver rad, selv om bare salary brukes. I column store er hele salary-kolonnen sammenhengende → mindre I/O og bedre kompresjon. OLTP-arbeidslast (SELECT * på enkelt-rader) favoriserer fortsatt row store.

04 · Block-format

Slot directory: anatomi av en blokk

For variable-length records trenger vi en mer fleksibel layout. Standardmønsteret er two-pointer-layout: records vokser fra starten, slot directory fra slutten. De møtes i midten — når det blir trangt, må man kompaktere eller splitte blokken.

Slot directory layout. Records vokser fra start, slots fra slutt. Ledig plass = avstand mellom dem.

Hvorfor er denne layouten genial?

Liten ordliste først: Hver slot er et lite par (pointer, lengde) som peker til startposisjonen til en record inne i blokken.

RID forblir stabil ved kompaktering. Hvis vi sletter Record B og senere flytter C nedover for å fjerne hullet, oppdaterer vi bare slot[2].pointer. Indekser ute som peker til (BlockId, slot=2) virker fortsatt.
Slot directory kan sorteres etter nøkkel. Da kan vi binærsøke i directoriet — selv om de fysiske recordene ligger i innsettingsorden.
Flip/flop-stempel ved start og slutt: ved en torn write («revet skriving» — for eksempel hvis strømmen forsvinner midt i blokk-skrivingen, slik at halve blokken har gammel data og halve ny), vil de to stemplene være ulike. Da kan vi forkaste blokken som korrupt og hente fra log.

Interaktivt — sett inn og slett records

Slot directory simulator

Trykk på knappene for å se hvordan blokken endrer seg.

Klar. Blokken har 4 slots, fritt område på 220 byte.

Spørsmål 5 · Vanskelig

Hva er fordelen med flip/flop-stempel ved start og slutt av blokken — hva forhindrer det?

Det forhindrer at vi leser en halvskreven blokk (torn write). Hvis strømmen forsvinner midt under en blokk-skriving, kan halve blokken være ny og halve gammel. Stemplene oppdateres rett før hver skriving til samme verdi. Hvis vi etter en crash leser en blokk hvor stemplet i header ikke matcher stemplet i trailer, vet vi at den er korrupt og må gjenopprettes fra loggen — sikkerhetslagrede endringer i en eget loggfil; reglene heter WAL og kommer i kap 8.

Spørsmål 6 · Middels

Hvorfor kan slot directory-en sorteres etter nøkkelverdi mens selve recordene ligger i innsettingsrekkefølge?

Fordi slot directory bare inneholder pekere — ikke selve dataen. Å sortere slottene endrer rekkefølgen på pekerne, ikke posisjonene til recordene. Da kan vi gjøre binærsøk innenfor blokken: les slot[mid], følg peker, sammenlikn nøkkel. Recordene trenger ikke flyttes fysisk.

05 · Buffer pool

Den eneste broen mellom RAM og disk

Buffer pool-en er typisk svært stor — flere GB i serverdatabaser. Den fungerer som en cache (mellomlager) i RAM: én gang en blokk er lest inn fra disk, kan flere transaksjoner og spørringer dele den. For å finne en gitt blokk i bufferet brukes en hashtabell på BlockId — så lookup er konstant tid (O(1) — like raskt uansett hvor stort bufferet er).

Liten ordliste: Et frame er én plass i bufferet, akkurat stor nok til én blokk. pin-count = hvor mange aktive brukere holder blokken låst i bufferet (kan ikke kastes ut når > 0). Dirty = endret siden den ble lest fra disk; må skrives tilbake før den kastes. Eviction = å kaste en blokk ut for å gjøre plass til en ny.

Buffer pool er hash-indeksert på BlockId. Hvert frame holder én blokk pluss metadata: pin-count og dirty-flag.

Hva skjer når en blokk forespørres?

Slå opp BlockId i hash-indeksen. Hit → returner pekeren til frame, øk pin-count, ferdig.
Miss → må finne et ledig frame. Hvis ingen er tomme, velg en blokk å kaste ut («offer» eller eviction-kandidat) via erstatningsstrategien (LRU = kast eldste, MRU = kast nyeste, clock = billig tilnærming til LRU). Offerets pin-count må være 0.
Hvis offeret er dirty, må de endrede dataene først skrives ut til disk. Regelen som styrer dette heter WAL (Write-Ahead Logging) og forklares i kap. 8.
Les den ønskede blokken inn i frame. Oppdater hash-indeksen. Returner.

Erstatningsstrategier

Strategi	Velger ut	Bra for	Dårlig for
LRU	Lengst siden bruk	Hot data, lokalitet	Skanninger forurenser bufferet
MRU	Sist brukte	Repeterte scans	Hot working set
Clock	Tilnærmet LRU, billigere	Praktisk default	Skanninger (samme som LRU)

Interaktivt — LRU i aksjon

Tre buffer frames, LRU-eviction

Skriv en BlockId og trykk «Hent». Den eldste blokken kastes ut når bufferet er fullt.

Hent en blokk for å starte.

Hvorfor egen buffer?

Operativsystemet har sin egen blokk-cache (page cache), men den vet ikke at en stor table scan «forurenser» cachen ved å fylle den med blokker som aldri leses igjen, eller at en mye-brukt rot-blokk i en indeks bør låses fast (pinnes) i bufferet. DBMS-en kjenner semantikken og kan prefetche (lese fram blokker den vet kommer), pinne, og tvinge skrivinger ved behov.

Spørsmål 7 · Middels

Hvorfor er LRU et dårlig valg når DBMS-en kjører en stor table scan?

En full scan leser hver blokk én gang. LRU vil gradvis kaste ut hot data (B+-tre-røtter, ofte brukte blokker) til fordel for skannet-blokker som aldri vil bli lest igjen. Bufferet «forurenses». MRU er bedre her: vi kaster ut den sist leste skann-blokken med en gang, så hot data forblir.

Spørsmål 8 · Vanskelig

En transaksjon endrer en blokk. Buffer pool-en velger denne blokken som offer i en eviction. Hva må DBMS-en gjøre før blokken skrives til disk, og hvorfor?

WAL — Write-Ahead Logging: DBMS-en må først tvinge ut alle loggposter som beskriver endringene (opp til høyeste LSN — Log Sequence Number — på blokken). Hvis ikke: en kræsj rett etter blokk-skrivingen ville etterlate datablokken med endringer som ikke ligger i loggen — recovery (gjenoppretting etter krasj) klarer da ikke å reprodusere transaksjonen. Loggen er sannhet, datablokken er bare en optimalisering. (Disse begrepene utdypes i kap. 8 — Recovery. Her holder det å forstå sekvensen: logg først, datablokk siden.)

06 · Heapfiler

Tabell uten orden

Heapfilen er den enkleste lagringsformen — bare en lenkeliste av blokker, og records legges inn der det er plass. Ingen sortering, ingen indeks-i-seg-selv.

Heapfilen organisert som to lenkelister: full og med ledig plass. Insert er O(1), søk uten indeks er O(N).

Fordeler

Trivielt enkelt å implementere
Insert er konstant tid
Ingen indeks-vedlikehold ved oppdatering
Velegnet for tabeller som likevel skal fullskannes

Ulemper

Søk er lineært i tabellstørrelsen
Range-spørringer er like dårlige
Blir spredt etter mange sletter — krever reorganisering
Brukes nesten alltid sammen med indekser

Spørsmål 9 · Lett

Hvorfor klarer en heapfil å sette inn nye records i konstant tid (O(1)) — uavhengig av om tabellen har 100 eller 100 millioner rader? Og hvorfor blir søk uten indeks O(N)?

O(1) insert: Free-list inneholder alle blokker med ledig plass. Insert tar første blokk i listen, putter recorden der, og flytter blokken til full-list hvis den ble full. Vi trenger aldri å lete etter en plass — blokken som har plass ligger alltid på toppen av free-list. Denne operasjonen er like billig på en stor som en liten tabell. O(N) søk: Recordene er ikke sortert eller hashet etter noe. For å finne en gitt verdi må vi i verste fall skanne alle blokker i både full-list og free-list. Det er derfor heap nesten alltid kombineres med en indeks ved siden av.

07 · Statisk hashing

Konstant-tid likhetsoppslag

Hashing leverer det heapfilen ikke kan: O(1) likhetssøk. Men den har en akilleshæl — du må bestemme antall blokker på forhånd.

Statisk hashing med separat overflow. Når en bøtte fylles opp, kobles overflow-blokker etter.

Tre overflow-strategier

Open addressing (åpen adressering): prøv neste blokk (eller fast hopp). Enkelt, men gjør sletting komplisert.
Separat overflow: dedikerte overflow-blokker som bøtte-blokker peker til. Kan deles eller være per-bøtte.
Multiple hashing: bruk en alternativ hash-funksjon ved kollisjon. Distribuert overflow.

Hovedproblem

Statisk hashing antar at antall records er kjent på forhånd. I praksis varierer datamengden, og lange overflow-kjeder gjør at oppslag som skulle vært O(1) blir O(N).

Spørsmål 10 · Middels

Statisk hashing lover O(1) likhetsoppslag, men kan i praksis degenerere til O(N) over tid. Hva er det som skjer, og hvorfor?

Antall bøtter N er fastsatt på forhånd. Når datamengden vokser forbi det vi planla for, fylles bøttene opp og nye records havner i overflow-blokker som lenkes etter hovedbøtten (eller spres via en av de andre overflow-strategiene). Et oppslag som «skulle» vært én blokk-aksess må nå følge en lang kjede av overflow-blokker — og kjeden vokser lineært med datamengden. Det er nettopp denne akilleshælen extendible hashing er designet for å unngå.

Spørsmål 10b · Lett

Hvorfor egner statisk hashing seg dårlig for WHERE empno BETWEEN 100 AND 200, selv før overflow-problemet kommer inn i bildet?

Hash-funksjonen fjerner naboskapet mellom nøkkelverdier. Empno 100, 101, 102 ender på helt forskjellige bøtter etter mod N. For å finne alle i intervallet må vi enten hashe hver mulig verdi (101 oppslag) eller skanne hele filen. Hashing er kun for likhetssøk — range krever en sortert struktur som B+-tre.

08 · Extendible hashing

Hashing som vokser elegant

Extendible hashing introduserer et lag mellom hash-verdien og blokken — en directory (oppslagstabell). Når en blokk fylles, dobles directory-en (eller bare blokken splittes), uten å rehasher hele filen.

Hovedideen — global vs. local depth

Tenk på directoriet som et oppslagsbord der adressen er d siste bits av hashen.

Global depth (d): hvor mange bits av hashen som directory-en bruker for å indeksere — altså hvor mange rader oppslagsbordet har (2^d).
Local depth (d'): hvor mange bits den enkelte blokken faktisk skiller på (siden flere directory-slots kan dele samme blokk).
Når d' < d for en blokk: flere directory-slots peker til samme blokk. Splitting skjer uten directory-doubling.
Når d' = d og blokken splittes: directory må først dobles.

Hvorfor de siste d bitene?

Det er ingen tilfeldighet — det er det som gjør doublingen elegant. Når d vokser fra 2 til 3, splittes hver gamle slot i to nye: slot 01 blir 001 og 101. Begge ender fortsatt på 01, så records som før hashet til slot 01 kan nå fordeles mellom de to nye slottene basert på den nye mest-signifikante biten — uten at vi må røre records i andre blokker. Direktoriet kan vokse uten at filen rehashes.

Med "siste d bit"-konvensjonen betyr en directory-fordobling rett og slett: kopier hele tabellen og lim den under seg selv. Så bare blokken som overflyttet trenger å splittes.

Extendible hashing etter 11 innsettinger med h(K) = K mod 16. Directory bruker 3 bit, men noen blokker har bare local depth 2.

Bygg din egen — interaktiv simulator

Sett inn nøkler én og én, og se hvordan directoriet vokser, hvilke slots som deler samme blokk, og når blokk-splitting utløser directory-doubling. Hash-funksjonen er h(K)=K — vi tar de siste d bitene direkte fra nøkkelen. Prøv eksempelet, eller dine egne nøkler.

Extendible hash-simulator

Kapasitet:

Klar. Tom struktur: d=0, ett slot pekende til en tom blokk A. Kapasitet 2 records per blokk.

Tips: gul = slot/blokk som ble brukt sist · grønn = nylig opprettet ny blokk fra splitt.

Søk i extendible hashing — alltid 2 blokk-aksesser

Beregn h(K), ta de siste d bitene → finn directory-slot.
Les den datablokken slot-en peker til.
Søk i blokken (lite, kan være lineært eller binær).

Sammenliknet med statisk hashing er ekstrakostnaden én directory-aksess. Til gjengjeld blir ytelsen ikke kvalt av lange overflow-kjeder.

Steg-for-steg trase — fra tom til 2 doublings

Vi setter inn nøklene 4, 5, 6, 12, 7, 11 i en extendible hash med kapasitet 2 records per blokk. Vi indekserer på de siste d bitene av nøkkelens binære representasjon. Start: d = 0, én slot som peker til én tom blokk A (d'=0).

#	Op	Tilstand etter	Hva skjedde
1	insert 4	d=0; A=[4] (d'=0)	Plass — sett inn.
2	insert 5	d=0; A=[4,5] (d'=0)	A blir full.
3	insert 6	d=1; slot 0→A=[4,6], slot 1→B=[5]; d'(A)=d'(B)=1	Doubling #1. A var full og d'=d=0 → doble katalog (d: 0→1), splitt A på siste bit. 4 (...0), 6 (...0) → A; 5 (...1) → ny B.
4	insert 12	d=2; slot 00→A=[4,12], slot 10→C=[6], slots 01,11→B=[5]; d'(A)=d'(C)=2, d'(B)=1	Doubling #2. 12 (...0) → A (full), d'(A)=d=1 → doble (d: 1→2), splitt A på siste 2 bit. 4 (...00), 12 (...00) → A; 6 (...10) → ny C. B uendret — d'(B)=1, så slot 01 og 11 deler B.
5	insert 7	d=2; B=[5,7]	7 (...11) → B. Plass.
6	insert 11	d=2; slot 01→B=[5], slot 11→D=[7,11]; d'(B)=d'(D)=2	Splitt uten doubling. 11 (...11) → B (full). d'(B)=1 < d=2 → splitt B på siste 2 bit, men ingen ny doubling. 5 (...01) → B; 7 (...11), 11 (...11) → ny D.

Resultat: 2 directory-doublings, 4 datablokker (A, B, C, D), endelig d = 2.

To-regelen for splitting

Full blokk og d'(blokk) = d: doble katalogen først (d → d+1), deretter splitt blokken. Full blokk og d'(blokk) < d: splitt bare blokken — flere katalogslots pekte før til denne ene blokken, nå deler de seg på to.

Spørsmål 11 · Vanskelig

Hva betyr det at en blokk har local depth 2 mens directoriet har global depth 3?

At flere directory-slots peker til samme blokk. Med local depth 2 skiller blokken bare på de 2 siste bitene. Slots 000 og 100 har samme 2 siste bit (00) og peker derfor til samme blokk. Når denne blokken senere splittes (uten å fylle opp directoriet) blir det to blokker, hver med local depth 3.

Spørsmål 12 · Middels

Hvilken klar ytelse-fordel og hvilken klar ulempe har extendible hashing fremfor B+-tre for likhetssøk?

Fordel: 2 blokk-aksesser uavhengig av filstørrelse (directory + datablokk). B+-tre har 3–4 nivåer for store tabeller. Ulempe: ingen sortering — range-søk og ORDER BY er ubrukelige. Også: directoriet kan bli stort hvis dataene er sterkt skjeve, og verken ORDER BY eller foreign key-traversering har noen hjelp av strukturen.

Spørsmål 13 · Anvend trasen

Etter steg 6 i trasen ovenfor: vi setter inn nøkkelen 9 (siste 2 bit = 01). Hva blir resultatet?

9s siste 2 bit = 01 → B (som bare holder [5]). Plass — sett inn. Etter: B = [5, 9]. Ingen splitt, ingen doubling, ingen ny blokk. Etter steg 6 var B ledig (kun [5] etter splittingen), så enkle innsettinger landet rolig før neste eventuelle splitt.

09 · Oppsummering

Det du må huske

Konsept	Hva	Når
Blokk	4–32 KiB enhet for I/O	Alltid — ikke noe mindre
RID	(BlockId, slot)	Indeks → rad-peker
Slot directory	Pekere på slutten av blokk	Variable-length, sletting/kompaktering
Buffer pool	RAM-cache + hash-indeks	Minimere disk-I/O
Heapfil	Usortert lenkeliste av blokker	Sammen med en eller flere indekser
Statisk hash	h(K) mod N → blokk	Faste datamengder, kun likhet
Extendible hash	directory + lokal/global depth	Voksende datamengder, kun likhet

Neste steg

Nå vet du hvordan en rad ligger i en blokk og hvordan blokker går mellom RAM og disk. Neste skritt: B+-trær — den indeksstrukturen som gjør raske søk og range-spørringer mulige på tabeller med milliarder rader.

10 · Vanlige feller

Det studenter blander sammen i lagringskapittelet

Disse er ikke konseptfeil — de er presisjonsfeil. Les listen etter du har lest 01–09 over; den viser hvor presisjonen må sitte når du leser et MCQ-alternativ.

BlockId vs RID. BlockId = (deviceId, offset) peker på en blokk. RID = (BlockId, slot) peker på én rad inne i blokken. Indekser bruker RID; buffer pool bruker BlockId. Bratsberg-eksamene oppgir alltid begge byte-størrelser separat — sjekk hvilken som hører hjemme i utregningen din.
Slot directory ≠ indeks. Slot directory er internt i én blokk og oversetter slot-nummer til byte-offset i samme blokk. En B+-tre-indeks er en separat struktur som peker på rader på tvers av blokker. Begge bruker «directory»-ordet, men gjør helt forskjellige jobber.
Pinning er ikke låsing. Pinning hindrer at en blokk kastes ut av buffer pool, men hindrer ikke at andre transaksjoner endrer dataen i blokken. Lock manager er en helt separat komponent (kap 8). En blokk kan være pinnet uten å være låst, og omvendt.
WAL-regelen: logg ut før datablokk. Når en dirty blokk evictes, må alle tilhørende loggposter (opp til blokkens høyeste LSN) være tvunget til disk først. Hvis du svarer at «buffer pool kan skrive datablokken når som helst» — feil. Loggens skriving må komme først.
LRU er ikke alltid best. Standardvalget er LRU/Clock, men ved store table scans «forurenser» de bufferet med blokker som aldri leses igjen. MRU er bedre der. Bratsberg-eksamen tester gjerne nettopp dette mønsteret: «hvilken strategi er optimal når DBMS-en gjør en full scan av en stor tabell?» — svar: MRU.
Statisk hashing skalerer ikke. Når du vurderer tradeoffs mellom statisk og extendible hashing: statisk har fast antall bøtter ved opprettelse. Vokser dataene, fylles bøttene og overflow-kjeder oppstår — søketiden går fra O(1) til O(N/N₀). Extendible løser dette ved å la directory-en vokse.
Hashing støtter kun likhet. Hash-funksjonen sprer nøkler tilfeldig — naboer i nøkkelrommet ender på vidt forskjellige bøtter. WHERE empno BETWEEN 100 AND 200 krever full scan i hash-fila. Hvis spørringene har ranges, må du velge B+-tre.
Heapfil + indeks ≠ clustered. En heap med en B+-tre-indeks ved siden av er unclustered. Bare når radene er fysisk sortert etter indeksnøkkelen og bladene er data-blokkene, har du en clustered indeks. Maks én clustered per tabell.
Flip/flop-stempel beskytter mot torn write, ikke krasj. Stempelet sjekker at hele blokken ble skrevet ferdig fysisk. Det gjenoppretter ikke innholdet — det varsler bare at blokken er korrupt. Det er recovery via WAL (kap 8) som faktisk gjenoppretter dataene.
Local depth ≤ global depth, alltid. Et klassisk extendible-hashing-spørsmål: hva skjer ved en split? Hvis local depth (på blokken) < global depth (på directory), splitter vi bare blokken og oppdaterer to directory-pekere — ingen directory-vekst. Hvis local depth = global depth, må directory dobles før split. Bytt om disse to og du svarer feil.

Sjekkliste før eksamen

Klarer du å forklare alle ti på 30 sekunder hver? Da er du i god form på 6A. Hvis ikke — gå tilbake til seksjonen ved siden av nummeret og les den én gang til.

11 · Flervalg-trening

MCQ — i samme stil som eksamen i år

Eksamen i 2026 er kun flervalg. Disse spørsmålene er konstruert med distraktorer som matcher de vanligste feilene fra Bratsberg-eksamenene. Klikk det alternativet du tror er riktig — du får forklaring etter første feil.

Flervalg · Lett · 6A § 02

Hva er den minste enheten DBMS-en leser eller skriver mellom disk og RAM?

Blokk er DBMS-ens grunnenhet for I/O. Selv om du spør etter én rad, leses hele blokken raden ligger i. Dette er hvorfor «antall blokker» er kostnadsmålet i alle regneoppgaver.

Flervalg · Lett · 6A § 04

Hva er en RID?

RID = Record IDentifier = (BlockId, slot). BlockId-delen peker fysisk på blokken; slot-delen er logisk og oversettes via slot directory. Dette gjør at vi kan flytte recorden inni blokken (kompaktering) uten at indekser blir ugyldige.

Flervalg · Middels · 6A § 04

Hva forhindrer flip/flop-stempelet i blokk-headeren og -traileren?

Stempelet oppdateres til samme verdi i header og trailer ved hver skriving. Hvis vi etter en krasj leser en blokk hvor de to ikke matcher, vet vi at skrivingen ble avbrutt midtveis. Det er recovery via WAL som faktisk gjenoppretter dataene — flip/flop oppdager bare problemet.

Flervalg · Middels · 6A § 05

DBMS-en kjører en stor table scan over en tabell som er mye større enn buffer pool. Hvilken erstatningsstrategi er optimal?

Ved en sekvensiell scan blir hver blokk lest én gang. LRU/Clock vil kaste ut «hot» data (B+-tre-røtter, ofte brukte blokker) til fordel for skanne-blokker som aldri leses igjen — bufferet «forurenses». MRU kaster ut den sist leste skanne-blokken med en gang, så hot data forblir.

Flervalg · Middels · 6A § 06

En tabell har 100 000 rader, hver record er 100 byte, blokk er 4096 byte (uten 2/3 fyllgrad — heap er pakket fullt). Hvor mange blokker leses i snitt for SELECT * FROM Employee WHERE empno = ? hvis empno ikke er indeksert og er unik?

Records per blokk = floor(4096/100) = 40. Antall blokker = ceil(100 000/40) = 2500. Uten indeks = full scan, men siden empno er unik kan vi stoppe når vi finner den; i snitt halvveis: ~1250. Distraktor 2500 er svaret hvis empno ikke er unik (må skanne alt).

Flervalg · Vanskelig · 6A § 07–08

Hva er hovedproblemet med statisk hashing, og hvordan løser extendible hashing det?

Statisk hashing krever forhåndskjent N. Underestimeres N, fylles bøttene og overflow-kjeder ødelegger ytelsen. Extendible hashing bruker et oppslagstabell (directory) som kan dobles ved behov, og splitter kun den fulle blokken — vekst er smertefritt og oppslag tar fortsatt directory + datablokk = 2 aksesser.

Flervalg · Vanskelig · 6A § 08

I extendible hashing: en blokk har local depth = 2, directory har global depth = 3. Hva skjer når blokken blir full og en ny record skal settes inn?

Når local depth < global depth peker flere directory-slots til samme blokk (her: 4 av dem). En split kan da skje uten å vokse directory: vi splitter blokken på neste bit, og to av de fire pekerne flyttes til den nye blokken. Begge nye blokker får local depth = 3. Distraktor A er svaret når local depth = global depth.

Etter 6A

Klarte du flesteparten? Bra. Hvis flere enn to bommet — gå tilbake til den tilsvarende seksjonen før du går videre til 6B (B+-trær).