Et SQL-spørsmål som SELECT * FROM Employee WHERE empno = 4711 ser uskyldig ut. Bak kulissene må databasesystemet (forkortet DBMS — DataBase Management System) finne én rad blant millioner. Det kan ta 1 millisekund eller 10 sekunder — forskjellen ligger i hvordan dataene er lagret på disken og hvilke indekser (smarte oppslagsstrukturer) som finnes.
Et oppslag i RAM (arbeidsminnet) tar ~100 nanosekunder. Et tilfeldig oppslag på en HDD (mekanisk harddisk) tar ~10 millisekunder — fem størrelsesordener tregere. DBMS-en jobber derfor ikke med én rad om gangen mot disk; den henter blokker — sammenhengende bolker av bytes (typisk 4–32 KiB) som inneholder mange rader sammen. En slik henting kalles en diskaksess. Så regelen er enkel: tell antall blokker som må leses fra disken — det er nesten alltid den dominerende kostnaden. (En SSD — solid state drive — ligger et sted imellom RAM og HDD i fart.)
Samme rad på tre nivåer. SQL-laget jobber med rader; disken kjenner bare blokker; inni hver blokk ligger mange records pakket som bytes. DBMS-jobben er å oversette mellom disse verdenene med så få diskaksesser som mulig.
~100 nsRAM-aksess
~100 µsSSD random read
~10 msHDD random seek
Mental modell
Tenk på diskaksess som å sende en bud til arkivet i kjelleren — og RAM som å åpne en bok som ligger på pulten. Indekser er kort sagt smarte triks for å sende færrest mulig bud.
02 · Hierarkiet
Fra device til felt
Hele kapittelet henger på dette ene bildet. Hver «boks» kjenner bare boksene umiddelbart over og under seg. SQL-laget snakker om rader; lagringslaget snakker om blokker. Resten av kapittelet handler om hvordan disse to verdenene møtes.
De fire byggesteinene, fra grovest til finest:
Device — en hel disk (SSD eller HDD), eller en stor fil på filsystemet som DBMS-en bruker som lagring.
Blokk (også kalt side/page) — den minste enheten DBMS-en leser eller skriver. Typisk 4–32 KiB. Adresseres med en BlockId (deviceId + offset).
Record (rad) — én rad i tabellen, lagret som en sekvens bytes inne i en blokk. Adresseres med en RID (Record IDentifier — en stabil peker, definert nedenfor).
Felt (attributt/kolonne) — én verdi i en rad, for eksempel empno eller name. Kan ha fast lengde (INT, CHAR(20)) eller variabel (VARCHAR).
I tillegg viser figuren buffer pool (RAM-cache av blokker — gjennomgås grundig i 6A § 05) og SQL-laget som ser bare rader og ikke vet noe om blokker.
Lagringshierarkiet — fra fysisk device opp til logiske rader. Buffer pool og SQL-laget henger på siden: den ene cacher blokker, den andre ser bare rader.
Litt vokabular før vi går videre: En RID (Record IDentifier) er en stabil peker til én rad. Den er bygd opp som (BlockId, slot) — først hvilken blokk på disken, så hvor i den blokken raden ligger. Slot-nummeret slås opp i en liten slot directory bak i blokken som peker til faktisk byte-posisjon. Vi går grundig inn i begge i 6A nedenfor.
Sjekk forståelsen · Lett
En RID er definert som (BlockId, slot). Hvorfor brukes ikke bare en absolutt offset (byte-posisjon) i filen?
Fordi vi vil kunne flytte recorden inne i blokken. RID-en er semilogisk: BlockId-delen er fysisk (peker direkte til en blokk), men slot-delen er logisk — slot directory-en oversetter slot-nummeret til faktisk byte-posisjon i blokken. Da kan vi kompaktere blokken (fjerne hull etter slettinger) uten at RID-er ute i indeksene blir ugyldige.
03 · Reisen gjennom kapittelet
To halvdeler — fundament og søk
Kapittelet er delt i 6A og 6B. 6A bygger fundamentet (hvordan én rad lever på disk og i RAM); 6B bygger søkestrukturen oppå (hvordan databasen finner én rad blant millioner). Begynn alltid med 6A — du må forstå hvordan en rad ligger i en blokk før indekser gir mening.
6A bygger fundamentet (record · blokk · buffer); 6B bygger oppslag oppå (B+-tre · indekser). Begge handler om samme spørsmål — minimer antall blokker som må flyttes mellom disk og RAM.
6A · Lagring
Hvordan ser én rad ut på disk? Du tar med deg: hvordan en rad blir bytes, hvordan blokker flyter mellom disk og RAM, og hvorfor heap- og hash-filer finnes.
6B · B+-trær & indekser
Hvordan finne én rad av millioner? Du tar med deg: hvorfor 3 blokk-aksesser er nok for ett oppslag i en milliontabell, og hvordan range-scan og clustering virker.
04 · Deler
Utforsk kapittelet
Hver underside er bygd progressivt: konsept → figur → eksempel → quiz. Følg dem i rekkefølge første gang.
Hovedkilde: lagring.pdf + Bratsbergs notater kap. 1–11. («Bratsberg» er kursets håndskrevne lagrings-kompendium — du finner det i pensumlisten på forsiden.) Læreboka dekker ikke lagringsdelen — disse to filene er pensum.
05 · Nøkkelbegreper
Tolv ord som låser opp kapittelet
Du møter alle disse begrepene i 6A og 6B over. Bruk listen som ordliste-sjekkliste etter du har lest begge underkapitlene — hvis du forstår disse 12, har du forstått kjernen. Resten er detaljer.
Blokk (page)
Den minste enheten DBMS-en leser eller skriver. Typisk 4–32 KiB. All koblingen mellom disk og minne skjer i blokker — aldri på rad-nivå.
Record / RID
En rad lagret som bytes. RID = (BlockId, slot) er den faste pekeren som indekser bruker.
Slot directory
En vektor på slutten av blokken som peker inn i blokken. Lar deg flytte recordene uten å ugyldiggjøre RID-ene.
Buffer pool
RAM-arealet hvor blokker holdes mens de er i bruk (blokk-cache). Når bufferet er fullt må DBMS-en kaste ut noe — strategien kan være LRU (Least Recently Used: kast den eldste), MRU (Most Recently Used: kast den nyeste) eller clock (en billig tilnærming til LRU).
Heapfil
Tabell uten orden — radene ligger der det er plass. Insert er konstant tid (O(1) — like raskt uansett hvor stor tabellen er); søk er lineær tid (O(N) — vokser med antall rader). Brukes typisk når det finnes en separat indeks ved siden av.
Hashfil
Konstant-tid likhetsoppslag (lik = «empno = 4711»). Statisk hashing har fast antall blokker og blir treg når den fylles; extendible hashing løser det med et oppslagstabell-lag (directory) som kan vokse — detaljer i 6A.
B+-tre
Balansert flerveistre. Bladene (de nederste nodene) inneholder selve dataene; interne noder over dem fungerer bare som veivisere. Hver node har høy fanout (mange barn) → kort tre. Bladene er lenket sammen i en sortert rekke for raske «verdier mellom 50 og 70»-spørringer (range-scan).
Clustered indeks
Radene i tabellen er fysisk sortert etter indeksnøkkelen. Maks én per tabell (det finnes bare én fysisk rekkefølge). Drastisk raskere for range-spørringer.
Unclustered indeks
Indeksen peker (via RID) inn i en separat heapfil. Kan ha mange per tabell, men hver match krever ett ekstra disk-oppslag for å hente selve raden.
LSM-tre
Skriv-optimalisert alternativ til B+-treet. Bygd av en memtable (sortert tabell i RAM), SST-filer (Sorted String Tables på disk) og en WAL (Write-Ahead Log — endringer logges først for sikkerhet). Detaljer i 6B. Brukt i RocksDB, MyRocks, BigTable.
Fanout
Hvor mange barn (pekere til underliggende blokker) en node i treet kan ha. Høyere fanout → kortere tre → færre blokker å lese fra disk per oppslag.
Fyllingsgrad (fill degree)
Hvor full hver blokk er i snitt. I et B+-tre med tilfeldig innsetting blir det statistisk ~2/3. Når du regner kapasitet i en oppgave: floor(blokk · 2/3 / recsize) records per blokk.
Sjekk forståelsen · Middels
Du har en tabell med 1 million rader og legger til en B+-tree-indeks med fanout 200. Omtrent hvor mange diskaksesser trengs for ett likhets-oppslag?
3–4 blokker. Høyden er log200(1 000 000) ≈ 2.6, så vi runder opp til 3 nivåer i selve treet (treet må ha hele nivåer). Hvis indeksen er unclustered trenger vi i tillegg ett oppslag i heapfilen for å hente selve raden — totalt 4. Hvis den er clustered, ligger raden allerede i bladet — 3.
06 · Oppsummering
Et bilde du må kunne tegne
På eksamen må du kunne resonnere om antall blokk-aksesser. Skissen under gir deg de fire vanligste lagringsalternativene side om side.
Fire lagringsalternativer side om side. Tallene under er for samme tabell (100 000 rader, 80-byte records, 4 KiB-blokker).
Eksamen-trick
Når du regner kostnaden av en spørring, gjør det alltid for hver av de fire alternativene over og sammenlikn — det er nettopp det Bratsberg gjør i kompendium-kapittel 12 (kostnadsregning).
07 · Notatmapping
Hvor i Bratsbergs notater ligger hva?
Pensum i del 2 er Bratsbergs håndskrevne notatkompendium, ikke læreboka. Hver underseksjon på dette nettstedet svarer direkte til ett eller flere av notatkapitlene 1–11. Bruk tabellen som «to-veis-katalog» — finn et notatkapittel og hopp rett til riktig sted, eller motsatt.
Notat-kap.
Tema
Side hos oss
Eksamen-fokus
1
DBMS-arkitektur — komponenter, lagdeling, hvor blokker flyter
Bratsberg-eksamene er svært gjenbrukende. Mer enn 70 % av spørsmålene de siste fem årene har handlet om notatkapittel 9 og 10 (B+-trær og access paths). Hvis tida er knapp: les notat 9–10 grundig, tren på regneoppgaver, og lær begrepene i notat 1–8 godt nok til å gjenkjenne dem i flervalg.
08 · Vanlige feller
Ti feil studenter gjør på eksamen
Disse er ikke konsept-misforståelser men presisjons-feil — der to nøkkelbegreper blandes, en formel anvendes feil sted, eller en utregning glemmer en konstant. Les listen igjennom etter du har lest 6A og 6B; den viser hvor du må passe ekstra på.
2/3 fyllingsgrad gjelder også interne noder. Det er lett å bare bruke 2/3 på bladene og glemme det når man regner fanout. Riktig: fanout = floor(blokkstr · 2/3 / indekspost-størrelse). Bruk samme regel på alle B+-tre-nivåer.
Indekspost-størrelse er nøkkel + RID, ikke nøkkel + BlockId. I et unclustered B+-tre består hver indekspost av nøkkelverdien pluss en peker til selve raden — og peker er en RID = (BlockId, slot) som typisk er 12 byte (8 byte BlockId + 4 byte slot), ikke 8. På eksamen får du oppgitt RID-størrelsen — bruk den.
Clustered B+ er ikke raskere på SELECT *. En full scan i et clustered tre må lese alle bladblokkene — som på grunn av 2/3-fyllingsgraden er flere enn et tilsvarende heap-fil. Clustered shines på WHERE og BETWEEN, ikke på spørringer som leser hele tabellen.
Unclustered + range = potensiell katastrofe. Hvert indeks-treff peker til en tilfeldig blokk i heapen. Hvis 20 % av radene matcher, blir det opp mot 20 % × N random disk-aksesser. Ofte er full scan billigere — DBMS-en velger derfor ofte å ignorere indeksen.
«Antall nivåer» vs «høyde». Bratsberg-konvensjon: et tre med kun rotnoden har 1 nivå. Antall nivåer = antall blokk-aksesser for ett likhetsoppslag. Sjekk alltid hva oppgaven mener før du svarer.
SELECT EtterNavn ... ORDER BY EtterNavn trenger ikke heap-aksess. Hvis kolonnen du henter ut er indeksnøkkelen, holder det å skanne bladnivået i indeksen — du har alle dataene der. Dette kalles index-only scan og er et klassisk eksamen-traff.
Statisk hashing: antall bøtter er fast ved opprettelse. Hvis du regner antall bøtter for å ha plass til N records, og senere data dobles, vil bøttene fylles og overflow-kjeder oppstå. Det er nettopp dette extendible hashing løser ved å la directory-en vokse.
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. Samtidighetskontroll er en annen mekanisme (kap 8).
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. Ellers feiler recovery etter krasj. Detaljer i kap 8, men prinsippet trengs allerede her.
Komposittnøkkel-rekkefølge er prefiks-stiv. Indeks (A, B) støtter WHERE A=? og WHERE A=? AND B=?, men ikkeWHERE B=? alene. Tenk leksikografisk: ordboka sorterer på første bokstav først.
Sjekkliste før eksamen
Gå gjennom listen igjen og kryss av i hodet ditt: «Kan jeg forklare denne på 30 sekunder?» Hvis ikke — gå tilbake til seksjonen der den hører hjemme, ikke bare les feilen om igjen.
09 · Eksamensscenario
Bratsberg-stil walkthrough — én tabell, fem spørsmål
De fleste regneoppgavene på del 2 bygger på ett scenario som blir spurt 4–6 forskjellige ting om. Her er et komplett eksempel i samme form som vår 2025-eksamen, med utregningene synlig. Klikk «Se svar» for å avsløre — men gjør deg først selv et forsøk på papir.
Felles oppsett — gjelder alle fem spørsmål
Tabellen Student(studNr, navn, epost, snitt) har 20 200 studentposter, hver på 120 byte. Nøkkelen studNr er 4 byte. RID er 12 byte og BlockId er 8 byte. Blokkene er 4 KiB = 4096 byte.
Vi har en clustered B+-tre på studNr, og en unclustered B+-tre på navn. Begge har 2/3 fyllingsgrad.
Spørsmål 1 · Hvor mange blokker på løvnivå (level 0) i den clustered B+?
Regneoppgave · Lett
Regn antall bladblokker i den clustered B+-treet over studNr.
Records per bladblokk (2/3 fyllgrad, hele records ligger i bladene): floor(4096 · 2/3 / 120) = floor(22.76) = 22 records per blokk.
Antall bladblokker: ceil(20 200 / 22) = ceil(918.18) = 919. Fellen: hvis du glemmer 2/3 og regner floor(4096/120) = 34 per blokk, får du ceil(20200/34) = 595 — som er feil men finnes som distraktor på eksamen.
Spørsmål 2 · Hvor mange nivåer har den clustered B+?
Regneoppgave · Lett
Hvor mange nivåer (inkl. blader) har den clustered B+-treet?
Indekspost i intern node = (nøkkel + BlockId) = 4 + 8 = 12 byte (i interne noder peker vi til underliggende blokker, ikke til records, så vi bruker BlockId — ikke RID). fanout = floor(4096 · 2/3 / 12) = 227.
Nivå 1 (over bladene): ceil(919 / 227) = 5 blokker.
Nivå 2: ceil(5 / 227) = 1 (rot). 3 nivåer totalt (level 0 = blader, level 1, level 2 = rot).
Spørsmål 3 · Likhetsoppslag på studNr
Access path · Lett
SELECT navn FROM Student WHERE studNr = 12345; — hvor mange blokker aksesseres optimalt?
Vi bruker den clustered B+: 1 (rot) + 1 (nivå 1) + 1 (blad). I bladet ligger selve recorden (clustered = data i blader), så ingen ekstra heap-aksess. 3 blokker.
Spørsmål 4 · Likhetsoppslag på navn (unclustered)
Access path · Middels
SELECT epost FROM Student WHERE navn = 'Kari Nordmann'; — én treff. Hvor mange blokker aksesseres optimalt? (Den unclustered B+ på navn har også 3 nivåer.)
Unclustered B+: 3 (tre-traversering ned til bladet med RID-en) + 1 (følg RID til riktig blokk i clustered fila / heapen). 4 blokker. Felle: Studenter glemmer ofte +1 for selve datablokken. I clustered koster oppslaget 3, i unclustered 4.
Spørsmål 5 · ORDER BY på den unclustered indeksens nøkkel
Access path · Vanskelig
SELECT navn FROM Student ORDER BY navn DESC; — hvor mange blokker aksesseres optimalt? (Den unclustered B+ på navn har 3 nivåer; antall bladblokker beregnes nedenfor.)
Indekspost i unclustered B+ = nøkkel + RID. Anta navn er 28 byte (CHAR(28)) → indekspost = 28 + 12 = 40 byte.
Indeksposter per blokk: floor(4096 · 2/3 / 40) = 68.
Bladblokker: ceil(20 200 / 68) = 298.
Nå til selve spørringen: vi henter bare navn — som er indeksnøkkelen. Da kan vi bruke index-only scan: skann bare bladnivået i indeksen sortert (nedover, siden DESC). Ingen heap-aksesser nødvendig. 298 blokker. Fellen: Mange svarer 298 + 20 200 (et oppslag per record i heapen). Det stemmer for andre kolonner, men ikke når kolonnen er indeksnøkkelen.
Mønsteret
Legg merke til strukturen: bygg først opp scenarioet med tall (sp. 1–2), så svar på spørsmål om enkeltspørringer (sp. 3–5). Det er nøyaktig mønsteret på vår 2024 og vår 2025. Trener du på dette, sparer du 5–10 minutter på selve eksamen — du går rett til kalkulasjonen uten å lure på hva oppgaven mener.
MCQ — flervalg i eksamensformat
Samme stil som du møter på eksamen i år. Klikk på alternativet du tror er riktig.
Flervalg · Lett
For Student-scenarioet over: hvor mange records får plass i én bladblokk i den clustered B+ med 2/3 fyllgrad?
floor(4096 · 2/3 / 120) = floor(22.76) = 22. Distraktor 34 er svaret hvis du glemmer 2/3-faktoren; 227 er fanout for interne noder; 68 er bladblokk-kapasitet for unclustered indeksen på navn.
Flervalg · Middels
SELECT * FROM Student WHERE studNr = 12345; — hvor mange blokker aksesseres optimalt? (3 nivåer i clustered B+.)
Clustered B+: traverser ned 3 nivåer; bladet inneholder selve recorden — ingen +1 for heap. 3. Distraktor 4 er svaret for unclustered (+1 heap-aksess); 919 er antall bladblokker (full scan).
Flervalg · Vanskelig
SELECT navn FROM Student WHERE studNr BETWEEN 10000 AND 12000; — anta dette gir ~2200 treff. Hvor mange blokker aksesseres optimalt?
Clustered B+: 3 (traversering ned til første matchende blad) + ceil(2200/22) = 100 (sekvensielle blader via leaf-link). Vi går ikke opp i treet igjen. Distraktor 2203 er svaret hvis indeksen var unclustered (random-aksess per record). Distraktor 919 er full scan.
Flervalg · Vanskelig
Samme tabell, men nå SELECT epost FROM Student WHERE navn = 'Kari'; med unclustered B+ på navn (3 nivåer). Anta 1 treff. Hvor mange blokker aksesseres optimalt?
3 (unclustered tre-traversering) + 1 (følg RID til datablokk i clustered/heap). 4. Husk: epost ligger ikke i indeksen — vi må til datablokken. Hvis vi hadde spurt etter navn (indeksnøkkelen), hadde 3 vært nok (index-only scan).
10 · Test deg selv
Helhetsspørsmål
12 spørsmål som dekker hele kapittelet. Detaljerte spørsmål om lagring og B+-trær finner du på de respektive underkapitlene.
1 · Lett
Hva er den minste enheten DBMS-en leser eller skriver mellom disk og RAM?
En blokk (også kalt page), typisk 4–32 KiB. DBMS-en jobber aldri på rad-nivå mot disk — selv om du bare trenger én rad, må hele blokken den ligger i leses inn.
2 · Lett
Hva står RID for, og hva består den av?
Record IDentifier = (BlockId, slot). BlockId peker på en blokk fysisk; slot er en logisk indeks i slot directory inne i blokken. Indekser bruker RID som peker fra indeksposten til selve raden.
3 · Middels
Hvorfor velger DBMS-er typisk å bruke sin egen buffer pool i stedet for å la operativsystemet håndtere caching via virtual memory?
Fordi DBMS-en kjenner semantikken i dataene. Den vet når en blokk vil bli lest igjen snart, kan prefetche når den ser en table scan, vet hvilke blokker som må skrives før commit (recovery), og kan pinne blokker som er midt i en transaksjon. Operativsystemet ser bare anonyme sidefeil og bruker generiske heuristikker.
4 · Middels
En tabell har 1 000 000 rader, 80 bytes per record, blokkstørrelse 4 KiB. Den ligger i en heapfil. En likhets-spørring på en ikke-indeksert kolonne — hvor mange blokker leses i gjennomsnitt?
Records per blokk: floor(4096/80) = 51. Antall blokker: ceil(1 000 000/51) = 19 608. Uten indeks må vi gjøre full scan, men i snitt finner vi raden halvveis: ~9804 blokker. (Hvis kolonnen er unik kan vi stoppe på den treffes; hvis ikke, må vi skanne alt: ~19 608.)
5 · Middels
Hva er forskjellen på en clustered og en unclustered indeks, og hvor mange clustered indekser kan en tabell ha?
I en clustered indeks ligger radene fysisk sortert etter indeksnøkkelen — bladene i B+-treet inneholder selve radene. I en unclustered indeks peker indeksen via RID inn i en separat heapfil. En tabell kan ha maks én clustered indeks (siden det bare er én fysisk sortering), men kan ha mange unclustered.
6 · Vanskelig
Hvorfor er en hash-indeks ubrukelig for spørringer som WHERE age > 50, mens en B+-tree-indeks håndterer det effektivt?
En hash-funksjon spreder nøkler tilfeldig over blokkene — nærliggende verdier ender på helt forskjellige steder. For å finne alle med age > 50 må du hashe alle mulige verdier eller skanne hele filen. B+-treet derimot holder nøklene sortert; én traversering ned til 51, så følge bladlenkene (pekere mellom nabobladene) sidelengs til slutten. Range-spørringer er en av de viktigste grunnene til at B+-trær dominerer.
7 · Middels
I et B+-tre er fyllingsgraden statistisk 2/3. Hva betyr det praktisk når du regner kapasitet?
Når nøkler settes inn i tilfeldig rekkefølge, vil hver blokk i snitt være ~67 % full (resten er ledig fra splittinger). Når du regner antall bladblokker for N records: ceil(N / floor(blokkstørrelse · 2/3 / recsize)). Eksempel: 4 KiB blokk, 120-byte records → floor(4096 · 2/3 / 120) = 22 records per blokk.
8 · Vanskelig
En unclustered B+-tree-indeks for spørringen WHERE empno > 90000 hvor 20 % av radene matcher — hvorfor kan en full table scan faktisk være raskere?
Hver indekstreff på unclustered peker til en tilfeldig blokk i heapen. 20 000 treff = potensielt 20 000 oppslag spredt rundt om på disken (kalt random I/O — Input/Output, altså lese/skrive-operasjoner). En full scan leser bare ~20 000 blokker sekvensielt (rett etter hverandre på disken), og sekvensiell I/O er størrelsesordener raskere enn random på både HDD og SSD. Når mange rader matcher, vinner derfor full scan.
9 · Middels
Hvorfor heter det Bplus-tre, og hva er forskjellen fra et vanlig B-tre?
I et B-tre kan data ligge i interne noder. I et B+-tre ligger alle data i bladene; interne noder inneholder bare separator-nøkler som guide. Dette gir to fordeler: (1) interne noder blir mindre → høyere fanout → kortere tre; (2) bladene kan lenkes sammen for raske range-scans, noe som er umulig i et B-tre.
10 · Vanskelig
Hva er problemet med statisk hashing, og hvordan løser extendible hashing det?
Statisk hashing har et fast antall blokker N — hvis du undervurderer datamengden, fylles bøttene opp og du får lange overflow-kjeder (bøtter som peker til ekstra-bøtter) som dreper ytelsen. Extendible hashing bruker en oppslagstabell (directory) mellom hash-verdien og blokkene. Når en blokk blir full, dobler man directory-en (eller bare splitter blokken hvis local depth < global depth — to begreper som kommer i 6A) og rehasher kun den ene blokken. Vekstratet er smertefritt, og oppslag tar fortsatt 1 ekstra aksess (directory + datablokk).
11 · Middels
Hva betyr pinning av en blokk i buffer pool, og når brukes det?
Pinning markerer en buffer-frame som «ikke kandidat for eviction». Brukes mens en operasjon aktivt holder pekere inn i blokken — typisk under en B+-tree-traversering eller mens en transaksjon endrer recordene. Når operasjonen er ferdig, unpinnes blokken og kan kastes ut igjen.
12 · Vanskelig
Du designer skjemaet for en tabell Order(orderId, customerId, date, total). Spørringene er hovedsakelig WHERE customerId = ? AND date BETWEEN ? AND ?. Hvilken indeks anbefaler du, og hvorfor er rekkefølgen viktig?
En sammensatt indeks (customerId, date). Komposittnøkler sorteres leksikografisk (som ord i en ordbok: først på første kolonne, så innenfor like verdier på andre kolonne), så vi ønsker det mest selektive attributtet først (customerId — fast verdi i WHERE), deretter range-attributtet (date). Da finner B+-treet først alle rader for kunden, og innenfor den gruppen er datoene sortert — så vi kan skanne sidelengs i bladet til vi går utenfor range-en. Hvis vi snur til (date, customerId), må vi skanne alle datoer i intervallet og deretter filtrere på kunde, langt mindre effektivt.
11 · Kapittel-eksamen
Flashcards — hele pensum i kortform
43 kort som dekker alle begrepene og regneoppgavetypene i kapittelet. Klikk kortet for å snu det. Bruk piltastene ←→ til å bla, S for å shuffle, eller R for å resette rekkefølgen. Samme tone og vanskelighetsgrad som øvingseksamenene — men i blafrende form, så du kan bruke det som repetisjonsdrill rett før eksamen.
Tastatur: ← forrige · → neste · Enter/Space snu · S shuffle · R reset
1 / 0
Kap. 6A — Blokk & recordLett
Hva er en blokk (page) i et DBMS, og hvilken rolle spiller den i I/O?
En blokk er den minste enheten DBMS-en leser eller skriver mellom disk og RAM — typisk 4–32 KiB. All koblingen mellom disk og minne skjer i blokker, aldri på rad-nivå.
Selv om en spørring bare trenger én rad, må hele blokken som inneholder den raden leses inn. Det er derfor regelen i Del 2 er tell antall blokker: blokk-aksess dominerer kostnaden over CPU og lokal beregning, fordi diskoppslag er ~5 størrelsesordener tregere enn RAM-aksess.
BlockId peker på en blokk fysisk på disken. Slot er en logisk indeks i blokkens slot directory som oversetter til faktisk byte-posisjon i blokken. Slik er RID semilogisk: den fysiske delen identifiserer blokken, den logiske delen tillater at recorden flyttes inni blokken (f.eks. ved kompaktering) uten at RID-en må endres.
Indekser (B+-trær, hashing) bruker RID som peker fra indeksposten ned til selve raden.
Hva er en slot directory, og hvorfor brukes den i blokker med variabel-lengde records?
En slot directory (også kalt page directory) er en vektor som ligger på slutten av blokken; hvert slot peker innover til en byte-offset der en record begynner. Records vokser fra starten av blokken; slot directory vokser fra slutten — de møtes i midten.
To grunner: (1) Variable-lengde records har ikke fast offset, så vi trenger en peker per record. (2) Når vi sletter en record kan vi kompaktere blokken og flytte records uten at RID-er ute i indeksene blir ugyldige — slot directory-en oppdateres, RID-ene består.
Hva er flip/flop-stempelet i en blokk-header, og hvilket problem løser det?
Flip/flop er et atomisk lese/skrive-stempel som skrives i både starten og slutten av blokken. Tallene oppdateres før blokken skrives ut.
Når en blokk leses inn igjen, sammenlignes de to stemplene. Hvis de matcher, ble blokken skrevet helt; hvis de ikke matcher, har vi en halv-skrevet blokk — typisk fordi maskinen krasjet midt i en disk-skriving (på en HDD kan en blokk-skriving ta flere millisekunder, og en strømsvikt midtveis er en reell fare).
Flip/flop er en lav-nivå sjekk; recovery (kap. 8) bygger ovenpå med WAL og ARIES for å gjenopprette logiske inkonsistenser.
Beskriv record vector-formatet for variable-lengde records.
En liten header (med antall felt n) etterfulgt av n pekere til hvor hvert felt begynner i recorden, og deretter selve felt-byteene.
Fordeler: feltene kan være variable lengder og ligge i hvilken som helst rekkefølge; recorden er nesten selvbeskrivende. For å lese felt nr. i hopper vi til peker i og leser fra peker i til peker i+1. Ulempen er overhead for små records (4–8 byte per peker × antall felt).
Alternativene er fixed length (alle felt har kjent lengde, beregn offset i SQL-katalogen) og delimiter (spesialtegn markerer felt-/record-slutt — kompakt men sårbart).
Når kan fixed-length record-format brukes direkte, og når må man over til record vector eller delimiter?
Fixed-length virker når alle felt har kjent og fast lengde — typer som INT, CHAR(N), DATE, NUM(p). Da ligger feltene på faste offsets, og decoding er ren aritmetikk: hopp til offset, les k byte. Insert/update er rask og enkel.
Med VARCHAR, TEXT eller andre variable-lengde-typer faller dette: faktisk lengde varierer mellom rader, og man må enten nullpadde til maks-lengde (sløser plass), bruke record vector med pekere, eller bruke delimiter-tegn.
Hva er en heapfil, og hvordan organiseres blokkene i den?
En heapfil er den enkleste organiseringen av en tabell: records lagres uordnet — typisk i innsettingsrekkefølge — i blokker som er lenket sammen.
Vanlig variant: to lenkede lister — én med blokker som er fulle, og én med blokker som har ledig plass. Ved insert plukker DBMS-en en blokk fra ledig-listen (eller allokerer en ny). Ved sletting kan en full blokk flyttes tilbake til ledig-listen.
Konsekvenser: insert er O(1), men søk uten indeks er O(N) (full scan). En likhets-spørring på en ikke-indeksert kolonne leser i snitt halvparten av blokkene før treff (hvis kolonnen er unik) eller alle blokkene (hvis ikke).
Hvorfor velger DBMS-er typisk å ha sin egen buffer pool fremfor å la operativsystemet håndtere caching via virtual memory?
Fordi DBMS-en kjenner semantikken i dataene; OS-et ser bare anonyme sidefeil og bruker generiske heuristikker.
Konkret kan DBMS-en:
• Prefetche intelligent — når en table scan starter, kan flere blokker hentes i forveien.
• Pinne blokker som er midt i en transaksjon eller en B+-tre-traversering, slik at de ikke kastes ut.
• Vite at logg-blokker må skrives før commit (WAL — write-ahead logging).
• Velge bedre replacement-policy enn ren LRU, f.eks. ved store sekvensielle scans der LRU hadde forurenset bufferet.
Trenden i moderne DBMS-er er likevel hybrid: la OS-et stå for filsystem og direkte I/O, men beholde DBMS-styrt buffering oppå.
Hva betyr det å pinne en blokk i buffer pool, og når brukes det?
Pinning markerer en buffer-frame som «ikke kandidat for eviction». Buffer manager vil ikke kaste ut en pinnet blokk selv om LRU-policy peker på den.
Brukes mens en operasjon aktivt holder pekere inn i blokken — typisk:
• Under en B+-tree-traversering: noden må forbli i bufferet helt til vi har lest hva vi trenger.
• Mens en transaksjon endrer records i blokken — buffer-framen må ikke gjenbrukes før endringen er committed (eller minst logget).
• Under en seq scan: den aktuelle blokken pinnes mens den prosesseres, unpinnes når neste blokk hentes.
Når operasjonen er ferdig, unpinnes blokken og kan kastes ut igjen ved behov.
Hva er hovedidéen i statisk hashing, og hvilken hash-funksjon brukes typisk i pensum?
Hashing tilbyr O(1) likhetsoppslag: en hash-funksjon h(K) avbilder nøkkelen direkte til ett av N faste bøtte-blokker. For å finne en record med nøkkel K beregner vi h(K), leser én blokk, søker innenfor den.
Pensums kanoniske hash-funksjon er h(K) = K mod N der N er antall bøtter. (For ikke-numeriske nøkler hashes først til en heltallsverdi.) Statisk fordi N er fastsatt på forhånd.
Hovedproblemet er nettopp denne staticiteten: hvis datamengden vokser, fylles bøttene og du får lange overflow-kjeder som dreper ytelsen — løsningen er extendible hashing.
Hva er en overflow chain, og hvilke tre overflow-strategier finnes?
Når en hash-bøtte fylles opp, må nye records havne et annet sted. En overflow chain er en lenket liste av ekstra-blokker som henger etter hovedbøtten — alle med samme hash-verdi.
Tre strategier:
(1) Open addressing — prøv neste blokk (eller fast hopp). Enkelt, men sletting blir komplisert (tombstones). (2) Separat overflow — dedikerte overflow-blokker som hovedbøtter peker til. Kan være delt eller per-bøtte. Pensums vanligste skisse. (3) Multiple hashing — bruk en alternativ hash-funksjon ved kollisjon. Fordeler overflow utover.
Felles for alle: et oppslag som «skulle» vært én blokk-aksess kan ende opp med å følge en lang kjede — i verste fall lineær tid.
Hvorfor er hashing helt ubrukelig for WHERE empno BETWEEN 100 AND 200, mens et B+-tre håndterer det effektivt?
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 [100, 200] måtte vi enten hashe hver mulige verdi (101 oppslag) eller skanne hele filen — verre enn full scan uten indeks.
Et B+-tre, derimot, holder nøklene sortert. Vi traverserer ned til 100 (typisk 3 nivåer), og følger så bladlenkene (pekere mellom nabobladene) sidelengs til vi går forbi 200. For et clustered-tre er det ren sekvensiell I/O.
Konklusjon: hash er kun for likhet (=); range trenger en sortert struktur.
Hva er hovedidéen i extendible hashing, og hvordan løser den hovedproblemet til statisk hashing?
Extendible hashing legger inn et directory (oppslagstabell) mellom hash-verdien og blokken. Indeksen i directoriet er de d siste bitene av hashen.
Når en blokk fylles, gjøres ett av to ting:
• Hvis blokkens local depth er mindre enn global depth: bare splitt blokken, oppdater directory-pekerne. Rimelig.
• Hvis local depth = global depth: doble directoriet (øk d med 1), splitt så blokken.
Resultatet: smertefri vekst, ingen lange overflow-kjeder. Et oppslag tar fortsatt 1 ekstra blokk-aksess (directory + datablokk). Hovedproblemet (statisk N) er borte.
Hva er local depth (d'), og hva betyr det at d' < d for en blokk?
Local depth d' er antall bits den enkelte blokken faktisk skiller på. Det tilsvarer hvor mange directory-slots som peker til denne blokken.
Hvis d' < d: flere directory-slots deler samme blokk. Konkret peker 2d−d' slots til denne ene blokken — alle slots som har samme siste d' bits.
Konsekvens: når en slik blokk fylles og må splittes, trenger vi ikke doble directoriet. Vi splitter blokken i to, øker dens d' med 1 (slik at de to nye blokkene skiller på en bit til), og oppdaterer directory-pekerne så halvparten av de delte slotsene peker til hver. Veldig billig.
Først når d' = d og vi vil splitte må directoriet dobles.
Når en blokk fylles opp i extendible hashing, hvordan avgjøres det om bare blokken splittes, eller om hele directoriet må dobles?
Sammenlign local depth d' med global depth d:
Tilfelle 1 — d' < d: Flere directory-slots peker til blokken. Splitt bare blokken: ny blokk allokeres, recordene fordeles ut fra én bit ekstra, d' øker med 1, og de delte directory-slotsene oppdateres så halvparten peker til hver av de to nye blokkene. Directoriet endrer ikke størrelse.
Tilfelle 2 — d' = d: Bare én slot peker til blokken — det er ikke nok bits til å skille de to halvdelene. Vi dobler først directoriet (alle slots dupliseres, d → d+1), og deretter splittes blokken som i tilfelle 1.
Dette er asymmetrisk billig på de fleste innsettingene: doublings skjer logaritmisk sjelden.
Hva er forskjellen mellom et B-tre og et B+-tre, og hvorfor er B+-tre den dominerende indeks-strukturen i DBMS-er?
I et B-tre kan data ligge i interne noder. I et B+-tre ligger alle data utelukkende i bladene; interne noder inneholder kun separator-nøkler som «guides» under traversering.
To store fordeler ved B+:
(1) Høyere fanout. Siden interne noder ikke trenger å lagre data, får de plass til mange flere (key, BlockId)-par per blokk. Høy fanout → kortere tre → færre I/O per oppslag. (2) Bladlenker. Bladene lenkes sammen i en sortert liste, så range-scans gjøres med ren sekvensiell I/O. Det er umulig i et rent B-tre.
I praksis bruker InnoDB, MS SQL Server, PostgreSQL og Oracle alle B+-trær.
Hva betyr fanout i et B+-tre, og hvorfor avgjør den treets høyde?
Fanout er antall barn (eller (key, child)-par) en intern node kan ha — bestemmes av blokkstørrelse delt på indekspost-størrelse, ganget med fyllgrad 2/3.
Med 4 KiB blokk og 16-byte indekspost: floor(4096 · 2/3 / 16) = 170 barn per intern node.
Antall nivåer over bladene er ⌈logfanout(L)⌉ der L er antall bladblokker. For pensums kanoniske eksempel (100 000 records, 80 B/rad → ~2942 bladblokker), med fanout 170: ceil(log_170(2942)) = 2 nivåer over bladene. Totalt 3 nivåer (rot + 1 mellomnivå + blader).
Selv med 100× så mye data (10 millioner rader → ~294 000 bladblokker) blir totalen kun 4 nivåer. Det er derfor B+-trær gir 3–4 nivåer for praktisk talt alle databaser — én typisk spørring blir 3–4 disk-aksesser uavhengig av om tabellen har én million eller én milliard rader.
Hva betyr fyllingsgraden 2/3 i et B+-tre, og hvordan brukes den i regneoppgaver?
Når nøkler settes inn i tilfeldig rekkefølge i et B+-tre, ender hver blokk i snitt ~67 % full. Resten er ledig plass etter splittinger — en splitt halverer en full blokk, så den nye blokken er 50 % full, og over tid stabiliserer det seg rundt 2/3.
Praktisk: når du regner kapasitet bruker du 2/3 av blokkstørrelsen som «brukbar» plass:
• Records per bladblokk: floor(blokkstørrelse · 2/3 / record-størrelse)
• Indeksposter per intern node: floor(blokkstørrelse · 2/3 / indekspost-størrelse)
Eksempel fra pensum: 4 KiB blokk, 80-byte records → floor(4096 · 2/3 / 80) = 34 records per blokk.
Hva er bladlenkene i et B+-tre, og hvilken type spørringer gjør de raske?
Hver blad-node har en peker til neste blad (og ofte også forrige), så bladene danner en sortert dobbel-lenket liste på laveste nivå.
Det gjør range-scans superraske. For en spørring som WHERE k BETWEEN a AND b:
1. Traverser ned til bladet som inneholder a (3–4 I/O).
2. Følg blad-pekerne sidelengs gjennom så mange blader som intervallet spenner — én blokk-aksess per blad, men sekvensielt.
For 500 records i et clustered-tre med 34 rec/blad blir det 3 + ⌈500/34⌉ = 3 + 15 = 18 blokker.
Uten bladlenker måtte vi traversere fra rota for hver enkelt verdi — umulig dyrt.
Hva er forskjellen på clustered og unclustered B+-tre, og hvor mange clustered indekser kan en tabell ha?
I en clustered indeks ligger radene fysisk sortert etter indeksnøkkelen — bladene er tabellen. Bladposten inneholder hele raden.
I en unclustered indeks ligger raden i en separat heapfil. Bladposten er bare (nøkkel, RID) — en peker inn i heapen.
En tabell kan ha maksimalt én clustered indeks, fordi det kun finnes én fysisk sortering. Men man kan ha mange unclustered indekser oppå samme tabell — hver gir sin egen vei inn til radene.
Konsekvenser: clustered er superraskt for range-scans (sekvensiell I/O), unclustered er nær elendig for range når mange rader matcher (random I/O i heapen).
Hva betyr det at en komposittnøkkel sorteres leksikografisk, og hvilken praktisk konsekvens har det for indeks-design?
Leksikografisk sortering er det samme prinsippet som ord i en ordbok: først sammenligne på første kolonne; ved likhet, sammenlign på andre kolonne; ved likhet, gå videre til tredje, osv.
Konsekvens for indeks-design: rekkefølgen på kolonnene betyr alt. Et B+-tre på (customerId, date) kan effektivt svare på:
• WHERE customerId = 42 ✓
• WHERE customerId = 42 AND date BETWEEN ... ✓ (kjernemønsteret)
• WHERE customerId = 42 ORDER BY date ✓ (gratis sortering)
Men ikkeWHERE date BETWEEN ... alene — datoer er bare sortert innenfor hver customer-gruppe.
Beskriv hovedkomponentene i et LSM-tre: memtable, SST og compaction.
Memtable i RAM: alle inserts/updates havner først her, sortert (typisk implementert som en skiplist). Veldig rask skriving, men volatil.
SST (Sorted String Table): når memtablen blir full, flushes hele innholdet til disk som én sortert, immutable fil. Den skrives sekvensielt (én stor I/O), aldri oppdatert.
Compaction: i bakgrunnen flettes SST-filer nedover i nivåer (L0 = nyeste, L1, L2, …). Dupliserte og slettede entries fjernes underveis. Resultatet er færre, større, mer kompakte SST-filer.
Slik treffer de fleste skrivinger først RAM, og disk-skrivinger skjer i store sekvensielle bolker — lav write amplification, høy komprimering. Brukt i RocksDB, LevelDB, Cassandra, MongoDB WiredTiger.
Hvorfor trenger LSM-trær en WAL (Write-Ahead Log) selv om alle skrivinger først går til memtablen?
Memtablen ligger i RAM og er volatil — innholdet forsvinner ved krasj eller strømsvikt. Hadde vi bare hatt memtablen, ville alle skrivinger gjort etter forrige flush vært tapt.
WAL løser dette ved å gjøre to skrivinger per insert/update: én til memtablen (rask, RAM), og én sekvensiell append til en logg på disk. Loggen er kort på sekvens av skrivinger, så I/O-overhead er liten.
Ved oppstart etter krasj leser systemet WAL-en og replayer alle endringer som ennå ikke er flushet til en SST. Dermed gjenoppretter vi memtablen, og durability (D-en i ACID) er bevart.
Når en SST er skrevet og fsync-et, kan tilhørende WAL-segment trygt slettes.
Hva er et Bloom filter, og hvorfor er det spesielt nyttig for LSM-trær?
Et Bloom filter er en kompakt sannsynlighets-datastruktur (bit-array + flere hash-funksjoner) som svarer på «er nøkkel K i mengden?» med to mulige svar: «kanskje» eller «sikkert ikke». Det kan ha falske positiver, men aldri falske negativer.
I LSM-trær må et lookup potensielt sjekke memtable + L0 + L1 + L2 + … fordi en gitt nøkkel kan ligge hvor som helst. Hvis hver SST har et Bloom filter på sine nøkler, kan vi raskt eliminere de fleste SST-ene uten å gjøre disk-I/O — bare de som svarer «kanskje» må faktisk leses.
Det reduserer read amplification dramatisk; uten Bloom filters er reads i en LSM-database mye tregere enn writes. Med dem nærmer read-ytelsen seg B+-trær for vanlige lookups.
Når lønner det seg å bruke column store fremfor row store?
For analytiske spørringer som leser få kolonner men mange rader. Eksempel: SELECT AVG(salary) FROM Employee.
I row store ligger hele raden samlet — DBMS-en må lese alle kolonner i hver rad selv om bare salary brukes. I column store ligger hele salary-kolonnen sammenhengende: mindre I/O, og siden like verdier ligger ved siden av hverandre, mye bedre kompresjon (delta encoding, run-length encoding, dictionary encoding).
OLTP-arbeidslast (mange små inserts/updates på enkeltrader, SELECT *-spørringer) favoriserer fortsatt row store, fordi en hel rad hentes med én I/O og oppdateres in-place.
Hva skjer når en blad-blokk i et B+-tre splittes ved innsetting? Hvordan håndteres split-key forskjellig på blad-nivå vs. internt nivå?
Når en blad-blokk er full og en ny nøkkel skal inn:
1. Allokér en ny blad-blokk.
2. Fordel nøklene jevnt: typisk halvparten i den gamle, halvparten i den nye.
3. Oppdater bladlenkene (next/prev-pekere).
4. Kopier den minste nøkkelen i den nye bladen opp til foreldrenoden — som ny separator.
Forskjellen mellom blad og internt nivå: på blad-nivå kopieres split-key opp (originalen forblir i bladet, fordi alle data må ligge i blader). På internt nivå flyttes midt-nøkkelen helt opp — den fjernes fra den gamle interne noden.
Hvis foreldren også blir full, splittes den, og effekten kan forplante seg helt opp til rota — som da splittes og treet vokser ett nivå.
Hvilke fire hovedmoduler har en typisk DBMS-arkitektur, og hva gjør hver?
Storage manager — leser og skriver blokker mot disk eller raw devices, holder buffer pool, allokerer ledig plass.
Query processor — SQL-compiler oversetter SQL til en algebra-tre, optimizer omformer treet til en fysisk plan ved hjelp av statistikk fra SQL-katalogen, og executor kjører planen.
Buffer manager — selv om den ofte regnes som en del av storage manager, er den ofte tegnet for seg: holder blokker i RAM, håndterer pinning, replacement-policy, fsync ved commit.
Loggen (WAL) er en tverrgående modul som transaction manager og recovery (Kap. 8) bruker.
Hva er page replacement i en buffer pool, og hvorfor er ren LRU ikke alltid det beste valget?
Når buffer pool-en er full og en ny blokk skal hentes inn fra disk, må en eksisterende blokk-frame frigjøres. Page replacement policy avgjør hvilken.
LRU (Least Recently Used) kaster ut den blokken som ikke er brukt på lengst tid. Fungerer bra for typiske «working set»-mønstre der noen få blokker brukes mye.
Problemet: en stor seq scan leser hver blokk én gang og forurenser hele bufferet. Etter scan har LRU-listen en hale av lite verdifulle blokker som likevel ligger i front.
Praktiske DBMS-er bruker derfor varianter: LRU-K (kasterut basert på k-te-siste aksess, ikke siste), clock (lett-implementert tilnærming), eller å la seq scan bruke en separat liten buffer-region. Pinning gjør også at noen blokker er fritatt fra eviction uansett policy.
A (51) bruker hele blokken uten fyllgrad-justering — det gjelder for en heapfil, ikke et B+-tre. C (25) bruker fyllgrad 1/2 i stedet for 2/3 — pensum (Bratsberg) standardiserer på 2/3, som er det statistiske snittet for tilfeldige innsettinger. D (17) bruker en feil ekstra-divisjon (deler på 3 etter den vanlige pakkingen) — typisk slurv.
B (2942) ville vært riktig for et clustered B+-tre på blad-nivå (med fyllgrad 2/3), ikke en ren heap. C (1250) deler antall rader på record-størrelsen (100 000 / 80) — har glemt at det er antall records per blokk som teller, ikke recsize i seg selv. D (100 000) antar at hver rad får sin egen blokk — typisk feil hvis man glemmer at flere records pakkes sammen i én blokk.
Samme tabell (100 000 rader, 80 B/rad, 4 KiB blokker). Hvor mange blokker har et clustered B+-tre på blad-nivå?
A 1961 (samme som heap, fordi alle radene må lagres uansett)
B 589 (gjelder unclustered der bladene bare lagrer (key, RID))
C 1471 (deler 100 000 / 68, hvis vi feil dobler 34)
D 2942 (100 000 / 34 rundet opp, med fyllgrad 2/3)
Riktig svar: D
Riktig: D — 2942 blokker.
I et clustered B+-tre er bladene tabellen — hver bladpost er en hel rad. Med fyllgrad 2/3 får hver blad 34 records (se kort 30).
antall_blader = ceil(100 000 / 34) = 2942
A (1961) glemmer fyllgrad 2/3 og bruker heap-tallene — derfor færre blokker, men det stemmer ikke for et B+-tre. B (589) er antall blader for en unclustered indeks (16-byte (key, RID), 170 entries per blokk, 100 000/170 ≈ 589). C (1471) er en oppdiktet 2× pakking — vanlig misforståelse hvis man tror clustering dobler kapasiteten.
Totalt 3 nivåer (level 0, 1, 2). Likhetsoppslag krever 3 disk-aksesser (én per nivå ned til riktig blad).
A (2) er for få: 2942 blader passer ikke under én enkelt rot, fordi en rot kan ha maks 170 barn. Vi trenger et mellomnivå (18 blokker) som så summeres opp i rota. B (4) er for mange: fanouten på 170 er stor nok til at de 18 mellomblokkene får plass i én rot — vi trenger ikke et ekstra mellomnivå. D (5) overestimerer enda mer; krever mye større datamengder før det blir aktuelt (jf. kort om skalering).
Tabell: 100 000 rader, heap = 1961 blokker. Spørringen er WHERE empno = c der empno er primærnøkkel. Hvor mange blokker leses i snitt for (i) ren heapfil uten indeks, (ii) clustered B+ med 3 nivåer?
A (i) 981 blokker, (ii) 3 blokker
B (i) 1961 blokker, (ii) 4 blokker
C (i) 1961 blokker, (ii) 1 blokk
D (i) 100 000 blokker, (ii) 3 blokker
Riktig svar: A
Riktig: A — heap 981 i snitt, clustered 3.
(i) Heapfil: uten indeks må vi skanne lineært. Siden empno er unik treffer vi raden i snitt halvveis: 1961 / 2 ≈ 981 blokker.
(ii) Clustered B+: traverser ned tre nivåer (rot → mellom → blad). Bladet inneholder hele raden — ingen ekstra heap-aksess. 3 blokker.
B (1961, 4): 1961 ville krevd full scan av heapen (gjelder hvis empno ikke var unik — alle blokker må sjekkes for flere treff). Tallet 4 stemmer for unclustered B+ + heap (3 tre-aksesser + 1 heap-aksess), men vi har clustered her — ingen ekstra heap-aksess. C (1961, 1): 1 blokk gjelder kun direkte hash med null kollisjon — glemmer at B+-treet må traverseres ned. D (100 000, 3): 100 000 blander antall rader med antall blokker; clustered-tallet 3 er riktig der, men heap-tallet er feil dimensjon.
Samme tabell. Spørring: WHERE empno > c der 20 % av radene matcher (= 20 000 rader). Antall blokk-aksesser for (i) clustered B+, (ii) unclustered B+ + heap?
A (i) 591, (ii) 591
B (i) 588, (ii) 4
C (i) 20 000, (ii) 20 121
D (i) 591, (ii) 20 121
Riktig svar: D
Riktig: D — clustered 591, unclustered 20 121.
(i) Clustered B+:
• 3 blokker for å traversere ned til startbladet.
• 20 000 rader / 34 rec per blad = ~588 blader sekvensielt via bladlenker.
• Totalt: 3 + 588 = 591 blokker.
(ii) Unclustered B+ + heap:
• 3 (tre) + 118 (indeks-blader for rangen, 20 000/170) = 121 blokker for å samle alle RID-ene.
• For hver av de 20 000 RID-ene: én random heap-aksess. 20 000 blokker.
• Totalt: 121 + 20 000 = 20 121 blokker.
Det er 34× forskjell — kjernen i hvorfor optimizere ofte velger full scan over en sekundærindeks når mange rader matcher.
A og B blander tallene; C overvurderer clustered (600 vs 20 000).
Vi øker tabellen til 10 millioner rader (100× større, alt annet likt: 80 B/rad, 4 KiB blokk, fyllgrad 2/3, fanout 170). Hvor mange nivåer trenger nå et clustered B+-tre?
4 nivåer (level 0–3). Med 100× så mye data går vi kun fra 3 til 4 nivåer — det er styrken i høy fanout. Likhetssøk koster fortsatt 4 disk-aksesser, ikke 100×.
A og C overvurderer veksten; D undervurderer den (høy fanout demper, men eliminerer ikke ekstra nivå når antall blader passerer 170² = 28 900).
Tabell med 100 000 rader. Spørring: SELECT * FROM Employee WHERE empno BETWEEN 50000 AND 50500 (~500 rader matcher). Hvor mange blokker leses med (i) clustered B+, (ii) unclustered B+ + heap?
Statisk hashing med h(K) = K mod 4, kapasitet 3 records per bøtte. Vi setter inn nøklene 5, 8, 13, 10, 16, 14, 21, 22, 24, 26 i denne rekkefølgen. Hvor mange records havner i overflow?
A 1 record (kun 26 går til overflow)
B 0 records (alle får plass)
C 3 records (overflow på alle tre fulle bøtter)
D 2 records (24 og 26)
Riktig svar: A
Riktig: A — kun 1 record (26) i overflow.
Beregn h(K) = K mod 4 for hver:
• Bøtte 0: 8, 16, 24 → 3 records (full).
• Bøtte 1: 5, 13, 21 → 3 records (full).
• Bøtte 2: 10, 14, 22, 26 → 3 records (full) + 26 går til overflow.
• Bøtte 3: ingen treff (ingen av nøklene gir K mod 4 = 3 i lista).
10 nøkler totalt, 9 får plass i 3 bøtter à 3, og 26 er den som flommer over.
B er feil — bøtte 2 fylles før 26 setter inn.
C overteller — kun bøtte 2 har overflow, ikke alle tre fulle bøtter (de andre er full men uten overflow fordi vi stoppet på 9 nøkler i de bøttene).
D regner med at både 24 og 26 flommer over, men 24 → bøtte 0 som har plass.
Et B+-tre med ORDER=4 (maks 3 nøkler per blad). En full blad-blokk har nøklene [10, 14, 22]. Vi setter inn 16. Hvordan ser de to bladene ut etter splittingen, og hvilken nøkkel havner som separator i forelderen?
A Venstre [10, 14, 16], høyre [22]; 22 flyttes (ikke kopieres) opp som separator
B Venstre [10], høyre [14, 16, 22]; 14 kopieres opp som separator
C Venstre [10, 14], høyre [22]; 16 plasseres i forelderen i stedet
D Venstre [10, 14], høyre [16, 22]; 16 kopieres opp som separator
Algoritmen (samme som det interaktive treet i 6B-simulatoren):
1. Sett 16 inn sortert: [10, 14, 16, 22] — nå overskrider bladet maks 3 nøkler.
2. Splitt på mid = ceil(4/2) = 2: venstre beholder de første 2 nøklene [10, 14], høyre allokeres med de siste 2 [16, 22].
3. Den minste nøkkelen i den nye høyre-bladen — her 16 — kopieres opp som separator i forelderen. (Original 16 blir liggende i bladet.)
4. Bladlenkene oppdateres: venstre.next = ny høyre, ny høyre.next = forrige venstre.next.
Forskjellen blad ↔ internt: på blad-nivå kopieres separator opp (data må forbli i bladene). Hadde dette vært en intern node, hadde 16 blitt flyttet opp og fjernet fra de splittede nodene.
A: 22 er ikke separator — separator er minste nøkkel i ny høyre. B: ujevn fordeling i feil retning. C: blander — 16 er allerede i bladet, og må også havne i forelderen som separator.
Tabell Order(orderId, customerId, date, total). Hovedspørringen er WHERE customerId = ? AND date BETWEEN ? AND ?. Hvilken sammensatt indeks gir best ytelse?
A Indeks på (date, customerId) — datoen er det mest selektive feltet
B Indeks på (customerId, date) — likhets-kolonnen først, range-kolonnen sist
C Indeks på (orderId) alene — primærnøkkelen er alltid raskest
D To separate indekser, én på customerId og én på date — optimizer kan kombinere dem
Riktig svar: B
Riktig: B — (customerId, date).
Komposittnøkler sorteres leksikografisk. Med customerId først ligger alle radene for samme kunde sammen i bladene; innenfor samme kunde er radene sortert på dato. Spørringen blir:
1. Traverser ned til startbladet for customerId = ?, 3 nivåer.
2. Følg bladlenkene sidelengs så lenge customerId og dato er i intervallet — sekvensiell I/O, ferdig.
A:(date, customerId) ville krevd at vi skanner alle rader i datointervallet og deretter filtrerer på kunde — vesentlig dyrere. C:(orderId) hjelper ikke — verken customerId eller date er sortert etter den. D:Index intersection finnes i moderne DBMS-er, men er typisk dyrere fordi vi må slå opp og kombinere RID-mengder. En sammensatt indeks vinner som regel.
En unclustered B+-tree-indeks for spørringen WHERE empno > 90000 der 20 % av radene matcher. Hvorfor velger optimizeren ofte full table scan i stedet for indeks-traversering?
A Mange random I/O-er i heapen er tregere enn én sekvensiell scan av samme totalvolum
B Optimizer-en bruker aldri indekser for range-spørringer
C Indeks-traversering krever låsing av treet, mens full scan ikke gjør det
D Bladene i en unclustered indeks er ikke sortert, så indeks-tilgang er O(N²)
Riktig svar: A
Riktig: A — random I/O i heapen blir totalt sett dyrere enn én sekvensiell scan.
Hver indekstreff på unclustered peker til en tilfeldig blokk i heapen. 20 000 treff = potensielt 20 000 random heap-aksesser spredt over disken. Sekvensiell I/O er størrelsesordener raskere enn random I/O på både HDD og SSD (selv om gapet er mindre på SSD).
En full scan leser ca. 1961 blokker sekvensielt. Det er totalt sett mye mindre arbeid enn ~20 000 random I/O.
Tommelfinger: hvis > ~10–20 % av radene matcher, slår full scan ofte unclustered indeks for range-spørringer. Optimizeren bruker statistikk fra katalogen for å regne ut når kryssingspunktet er.
B er feil — optimizeren bruker indekser for selektive range-spørringer. C er ikke kjernepoenget; låsing er en helt annen problemstilling. D er feil; bladene er sortert, problemet er heap-aksessene som følger.
En blokk har 4 records med RID-er (B7, 0), (B7, 1), (B7, 2), (B7, 3). Vi sletter record på slot 1 og deretter kompakterer blokken. Hvilken effekt har det på de gjenværende RID-ene som ligger i indekser ute i systemet?
A RID-ene må oppdateres til (B7, 0), (B7, 1), (B7, 2) — slot-numrene rykker ned
B Alle indekser må gjenbygges fra bunnen siden RID-ene er ugyldige
C RID-ene består uendret — slot directory peker til de nye byte-posisjonene, men slot-numrene endres ikke
D RID-ene består, men kompaktering må aldri utføres på en blokk med eksterne referanser
Riktig svar: C
Riktig: C — RID-ene består uendret.
Det er nettopp derfor RID-en er semilogisk (BlockId + slot, ikke en absolutt byte-offset). Slot directory-en er en oversikt over hvor i blokken hver record ligger; ved kompaktering oppdateres pekerne i directory-en, men slot-numrene følger med uendret.
Konkret etter sletting og kompaktering:
• Slot 0 → peker til ny posisjon for record (B7,0)
• Slot 1 → markert som «slettet» (eller fjernet fra directory)
• Slot 2 → peker til ny posisjon for record (B7,2)
• Slot 3 → peker til ny posisjon for record (B7,3)
Indekser som peker til (B7, 2) finner fortsatt riktig record, fordi directory-en fortsatt har slot 2 — bare på en annen byte-posisjon i blokken.
A er feil — slot-numre er stabile RID-deler. Hvis de hadde rykket ned, ville indekser brutt sammen. B er for drastisk — det er hele poenget med slot directory at vi ikke trenger det. D er motsatt av sannheten — kompaktering er trygt og må utføres for å reklamere plass.