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

Databasteknik: Svar till övningar - kapitel 22, övning 4, En biljon telefonsamtal

Vi antar som tidigare att sid är en nyckel, så att sökningen på sid ger (högst) en enda rad i svaret, och sekundärindexet T2 på kolumnen sid finns kvar.

Den effektiva blockningsfaktorn för datablocken är fortfarande 40. Med en biljon poster behövs 25000000000 datablock (2.5*1010).

Första frågan:

select * from Telefonsamtal where pid  = 99181888;

Den här frågan använder primärindexet. Den första nivån i indexet innehåller 25000000000 / 683, dvs 36603221, indexblock. Den andra nivån i indexet innehåller 36603221 / 683, dvs 53592, indexblock. Den tredje nivån i indexet innehåller 53592 / 683, dvs 78, indexblock. Den fjärde nivån i indexet består av ett rotblock. Indexet har alltså fyra nivåer.

För att hitta en datapost baserat på dess pid-värde behövs det fem läsningar från disken: fyra 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 25 millisekunder att köra, dvs 0.025 sekunder.

Den andra frågan:

select * from Telefonsamtal where sid = 21001999;

Sökningen på sid 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 / 683, dvs 1464128843, indexblock. Den andra nivån i indexet innehåller 1464128843 / 683, dvs 2143673, indexblock. Den tredje nivån i indexet innehåller 2143673 / 683, dvs 3139, indexblock. Den fjärde nivån i indexet innehåller 3139 / 683, dvs 5, indexblock. Den femte nivån i indexet består av ett rotblock. Indexet har alltså fem nivåer.

För att hitta en datapost baserat på dess sid-värde behövs sex läsningar från disken: fem 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 30 millisekunder att köra, dvs 0.030 sekunder.

Sammanfattning

När antalet poster i datafilen blev tusen gånger större, behövdes i bägge sökningarna en extra diskläsning. Sökningen via sekundärindexet kräver fortfarande en diskläsning mer än sökningen via primärindexet.

Man kan dock inte vara säker på att ett sekundärindex alltid blir djupare än ett primärindex, men i genomsnitt blir det det. (Om vi jämför primär- och sekundärindex på kolumner som är lika breda.)

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

Ovanstående scenario är egentligen omöjligt. Kolumnen pid är deklarerad som nyckel, och har datatypen integer, som vi sa var 32 bitar stor. Men ett 32-bitars heltal kan bara anta 232 olika värden, eller 4294967296, dvs lite drygt fyra miljarder. Samtidigt skulle tabellen innehålla en biljon rader. Det går inte ihop!


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