Kapittel 6 · Forelesning 11–12 · Del 2

Lagring og indekser

Hvor data faktisk ligger — fra rotende disk til en blokk i bufferet, og hvordan B+-treet finner riktig rad på 3 oppslag.

Bratsbergs notater 1–11 Forelesning 11–12 lagring.pdf
01 · Helhetsbilde

Hvorfor bryr vi oss om hvor dataen ligger?

Et SQL-spørsmål som SELECT * FROM Employee WHERE empno = 4711 ser uskyldig ut. Bak kulissene må DBMS-en 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 som finnes.

RAM-aksess tar ~100 nanosekunder. Et tilfeldig HDD-oppslag tar ~10 millisekunder — fem størrelsesordener tregere. Så regelen er enkel: tell antall blokker du må lese fra disken. Det er nesten alltid den dominerende kostnaden.

~100 ns RAM-aksess
~100 µs SSD random read
~10 ms HDD 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.

Lagringshierarki: device, blokk, record, felt DEVICE SSD eller HDD deviceId + offset BLOKK / SIDE ~16 KiB BlockId = (dev, idx) RECORD / RAD én rad i tabell RID = (BlockId, slot) FELT / ATTRIBUTT empno, name, ... fixed eller variable BUFFER POOL RAM-cache av blokker hash-indeksert SQL-LAGET ser bare rader vet ikke om blokker leses inn inneholder deles i tilbys som DBMS-jobben: minimer antall blokker som må flyttes mellom device og buffer pool. Indekser, clustering og smart bufring er alle svar på det samme problemet.
Lagringshierarkiet — fra fysisk device opp til logiske rader. Resten av kapittelet utdyper hver av disse boksene.
Sjekk forståelsen · Lett
En RID er definert som (BlockId, slot). Hvorfor brukes ikke bare en absolutt offset 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 offset i blokken. Da kan vi kompaktere blokken (fjerne hull etter slettinger) uten at RID-er ute i indeksene blir ugyldige.
03 · Nøkkelbegreper

Tolv ord som låser opp kapittelet

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. Hash-indeksert på BlockId. Erstatningsstrategi: LRU, MRU eller clock.

Heapfil

Tabell uten orden. Insert er O(1), søk er O(N). Brukes typisk når det finnes en separat indeks ved siden av.

Hashfil

Konstant-tid likhetsoppslag. Statisk hashing får overflow-problemer; extendible hashing løser det med en directory.

B+-tre

Balansert flerveistre med høy fanout. Alle data ligger i bladene; interne noder er bare guide. Bladene er lenket sammen for raske range-scans.

Clustered indeks

Radene i tabellen er fysisk sortert etter indeksnøkkelen. Maks én per tabell. Drastisk raskere for range-spørringer.

Unclustered indeks

Indeksen peker inn i en separat heapfil. Kan ha mange per tabell, men hver match krever ekstra blokkaksess.

Sparse vs dense

Dense = én indekspost per record. Sparse = én per blokk (kun mulig på clustered data). Sekundærindekser er alltid dense.

Fanout

Hvor mange barn en intern node har. Høyere fanout → færre nivåer → færre disk-I/O per oppslag.

Fill degree

Statistisk 2/3 i et B+-tre. Når du regner kapasitet i en oppgave: floor(blokk · 2/3 / recsize).

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, dvs. 3 nivåer i selve treet. Hvis indeksen er unclustered trenger vi i tillegg én aksess i heapfilen for selve raden — totalt 4. Hvis den er clustered ligger raden allerede i bladet — 3.
04 · Deler

Utforsk kapittelet

Kapittelet er delt i to halvdeler. Begynn med 6A — du må forstå hvordan en rad ligger i en blokk før indekser gir mening.

6A
Lagring — record-format, blokker, buffer, hashing
Notater kap. 1–8. Animasjoner av slot directory, buffer pool og extendible hashing. 8 quizer.
→ 6B
B+-trær og indekser
Notater kap. 9–11. Interaktivt B+-tre — sett inn nøkler og se tre-splitting. 9 quizer.
→
Slides og notater

Hovedkilde: lagring.pdf + Bratsbergs notater kap. 1–11. Læreboka dekker ikke lagringsdelen — disse to filene er pensum.

05 · 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 1 · HEAP 17, 4, 92, 8 31, 22, 14 5, 19, 73, 11 2, 47, 13 Insert: O(1) Søk: full scan 2 · HASH h=0 h=1 h=2 h=3 8, 16, 24 5, 13, 21 10, 14, 22 3, 11, 19 Likhet: O(1) Range: full scan 3 · CLUSTERED B+ 14|33 2,5,11 14,22,28 33,41 ← bladlenker → Likhet: 3 blokker Range: super-rask 4 · HEAP + B+ indeks k→RID k→RID k→RID heap (usortert) Likhet: 3 + 1 Range: random I/O Velg etter spørringsmønster: mange likhetssøk + få endringer → hash; range-spørringer → clustered B+; ad-hoc + flere indekser → heap + B+. På eksamen: regn ut antall blokker for hver av de fire alternativene før du velger.
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 kapittel 12.

06 · 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 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 random I/O-er. En full scan leser bare ~20 000 blokker sekvensielt, og sekvensiell I/O er størrelsesordener raskere enn random på både HDD og SSD. Optimalisatoren bruker selektivitet for å bytte til full scan over en terskel (typisk ~5–15 % treff).
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 som dreper ytelsen. Extendible hashing bruker en 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) 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, 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.