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

Databasteknik: Svar till övningar - kapitel 22, övning 2, Sökning på pid och sid

Vi antar för enkelhets skull att även sid är en nyckel, så att den andra frågan ger (högst) en enda rad i svaret.

Vi antar att en integer upptar 32 bitar, dvs 4 byte, och att en timestamp är lika stor. Hela posten upptar då 136 byte. Låt oss i övrigt anta att (logiska) blockstorleken är 8192 byte, att det tar 5 millisekunder att läsa ett godtyckligt block, och 1 millisekund att läsa ett block i följd.

Ordningen av B+-trädet blir (8192 - 4) / (4 + 4) + 1, dvs 1024, och den effektiva ordningen två tredjedelar av detta, dvs 683. Blockningsfaktorn för datablocken är 8192 / 136, dvs 60. Om de fyllts på utgående från B+-trädsprimärindexet är de två tredjedels fulla, dvs har den effektiva blockningsfaktorn 40. Med en miljard poster behövs 25000000 datablock.

select * from Telefonsamtal where pid  = 99181888;

Den här frågan använder primärindexet. Det finns 25000000 datablock. Den första nivån i indexet innehåller 25000000 / 683, dvs 36603, indexblock. Den andra nivån i indexet innehåller 36603 / 683, dvs 54 indexblock. Den tredje nivån i indexet består av ett rotblock. Indexet har alltså tre nivåer.

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

Den andra frågan:

select * from Telefonsamtal where sid = 21001999;

Här finns inget index vi kan utnyttja, så vi måste läsa hela tabellen. Vi har antagit att sid är unikt, så frågan her (högst) en enda rad i svaret, men det har vi inte talat om för databashanteraren! Den måste därför läsa igenom alla dataposterna även om den skulle hitta en matchande post.

Det finns 25000000 datablock. De är sammanlänkade med pekare, men vi kan inte räkna med att de ligger i följd. Därför tar vare blockläsning 5 millisekunder, eller totalt 125000 sekunder, dvs ca 35 timmar.

Sammanfattning

Sökningen på den indexerade kolumnen tar 2 hundradelar av en sekund, och sökningen på den oindexerade kolumnen tar 36 timmar. Så stora skillnader är precis vad man kan förvänta sig i stora tabeller.


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