[fors]

Rent teoretiskt, tidskomplexiteten är O(log) vid sökning i en databas som är indexerad. Detta medför att det krävs 20 jämförelser för att söka upp ett värde när det är 1 miljon rader. När det är 25 miljoner rader så krävs det 25 jämförelser. Och för 1 miljard rader så krävs det 30 jämförelser. Som du ser så ökar inte antalet jämförelser särskilt mycket när datan växer. Detta är rent teoretiskt och det borde se ut någorlunda lika i verkligheten.

Ett problem som finns om indexdatan ligger på disk, då blir det höga söktider. Så det vore optimalt om indexfilen fick plats i minnet. Jag har en tabell på en site där antalet rader är 1,5 miljoner. Jag indexerar två stycken int-kolumner och storleken uppgår till knappt 28 kB.

Min poäng är alltså att om man har indexet i minnet och indexerar korrekt så gör det inte så mycket om det är en stor tabell. Jag är inte jätteinsatt i MySQL eller databaser i allmänhet rent praktiskt rörande prestanda på det här viset, så rätta gärna mig om jag har fel. Men tidskomplexiteten är i alla fall sådan rent teoretiskt. Det finns alltså en anledning till varför många faktiskt väljer att ha en tabell och inte flera tusen.