Omslaget. Klicka här för att gå till bokens hemsida.

Databasteknik: Svar till övningar - kapitel 22, övning 5: Index på kolumnen kommentar

För enkelhets skull antar vi här att frågan bara ger en enda rad i svaret.

Eftersom kolumnen kommentar har en annan bredd än pid och sid, kommer det nya sekundärindext TK på kolumnen kommentar att få en annan ordning på trädet. Ordningen av B+-trädet blir (8192 - 4) / (4 + 100) + 1), dvs 79, och den effektiva ordningen två tredjedelar av detta, dvs 53.

select * from Telefonsamtal
where kommentar = 'Avlyssnat av agent Karlsson';

Den här sökningen på kommentar använder sekundärindexet. Ett sekundärindex är inte ordnat i samma ordning som datafilen, och därför räcker det inte med att lövnoderna i indexet innehåller en enda pekare till varje datablock. I stället måste lövnoderna innehålla en pekare till varje datapost.

Det finns en biljon dataposter. Den första nivån i indexet innehåller 1000000000000 / 79, dvs 12658227848, indexblock. Den andra nivån i indexet innehåller 12658227848 / 79, dvs 160230732, indexblock. Den tredje nivån i indexet innehåller 160230732 / 79, dvs 2028237, indexblock. Den fjärde nivån i indexet innehåller 2028237 / 79, dvs 25674, indexblock. Den femte nivån i indexet innehåller 25674 / 79, dvs 325, indexblock. Den sjätte nivån i indexet innehåller 325 / 79, dvs 4, indexblock. Den sjunde nivån i indexet består av ett rotblock. Indexet har alltså sju nivåer.

För att hitta en datapost baserat på dess kommentar-värde behövs åtta läsningar från disken: sju indexblock och sen det utpekade datablocket. Eftersom läsning av ett block tar i genomsnitt 5 millisekunder, kan vi räkna med att hela SQL-frågan tar 40 millisekunder att köra, dvs 0.040 sekunder.

Sammanfattning

Sökningen via sekundärindexet på kommentar tar 40 millisekunder, vilket är längre än sökningen via sekundärindexet på sid. Det är precis vad man kan förvänta sig, eftersom kolumnen kommentar är bredare, och B+-trädet därför blir smalare och djupare. Det går ju in färre sökvärden i varje nod.

Men har du tänkt på det här!

Tabellen innehåller en biljon dataposter. Som vi sett i tidigare uppgifter är den effektiva blockningsfaktorn för datablocken 40. Det betyder att tabellens data upptar 25000000000 diskblock, vilket motsvarar 204800 gigabyte. Den största hårddisk jag just nu (juli 2005) hittar hos Dustin är på 500 gigabyte. Det går alltså åt över 400 sådana hårddiskar, till ett pris av sammanlagt över en miljon kronor, för att lagra tabellens data!

Indexet på kommentar innehåller enligt uträkningen ovan 12658227848 + 160230732 + 2028237 + 25674 + 325 + 4 + 1, dvs 12820512821 diskblock. Det är ytterligare 224 stycken 500-gigabytes hårddiskar, till ett pris av 644224 kronor.


Av Thomas Padron-McCarthy (e-post: boken@databasteknik.se)
Senaste ändring: 30 juli 2005