B-trädindex och hur de hjälper

När en intervjuare säger 'den här frågan är långsam, vad gör du?' innehåller svaret de nästan alltid lyssnar efter ett index. Index är den enskilt största hävstången för läsprestanda, så de skiljer kandidater som har memorerat syntax från dem som förstår hur en databas faktiskt hittar rader.

I den här lektionen bygger ni en exakt mental modell av B-trädindexet: vad det lagrar, vilka operationer det snabbar upp och hur ni talar om det som en senior utvecklare.

Utan ett index måste databasen läsa varje rad i tabellen för att hitta rader som matchar ett villkor. Detta är en sekventiell skanning (eller fullständig tabellskanning). I en tabell med en miljon rader innebär det en miljon radkontroller, även om bara en rad matchar.

Ett index är en separat, sorterad datastruktur som låter databasmotorn hoppa direkt till matchande rader, på samma sätt som ett bokregister låter er hitta ett ämne utan att läsa varje sida.

Standardindexet i PostgreSQL, MySQL, SQL Server och de flesta andra databasmotorer är ett B-träd (balanserat träd). Det lagrar värdena i den indexerade kolumnen i sorterad ordning, organiserade i ett grunt träd av sidor.

• Varje lövnod innehåller indexnycklar samt en pekare till den faktiska tabellraden.
• Trädet förblir balanserat, så varje uppslagning berör bara några få sidor, oavsett tabellens storlek.

En uppslagning går från roten ner till ett löv i ungefär log(N) steg i stället för att skanna alla N rader.

Ni skapar ett B-trädindex med CREATE INDEX. Namnge det tydligt så att en granskare direkt ser vilken tabell och vilka kolumner det gäller.

När indexet finns kan en fråga som filtrerar på email använda det för att hitta den matchande raden med bara några få sidläsningar i stället för en fullständig skanning.

Eftersom ett B-träd håller värdena sorterade snabbar det upp betydligt mer än exakta matchningar. Intervjuare uppskattar när ni listar detta precist:

• Likhet: WHERE email = ?
• Intervall: WHERE age > 30, BETWEEN, <, >=
• Prefixmatchning: WHERE name LIKE 'Ada%' (men INTE '%da')
• ORDER BY på den indexerade kolumnen, vilket undviker en sortering
• MIN/MAX, eftersom de finns i ändarna av den sorterade strukturen

Föreställ er en orders-tabell med miljontals rader. En rapportfråga efterfrågar nya order. Med ett index på created_at söker databasmotorn upp intervallets början i det sorterade indexet och går framåt bara så långt som behövs.

Indexet omvandlar en fullständig tabellskanning till en begränsad intervallskanning som bara läser det kvalificerande utsnittet.

En aspekt som ofta förbises är att databasmotorn kan returnera raderna i indexordning och hoppa över ett separat sorteringssteg, eftersom indexet redan är sorterat. Detta är viktigt för ORDER BY och särskilt för top-N-paginering.

Om ni sorterar efter en kolumn som har ett matchande index kan optimeraren läsa indexet i rätt ordning och avsluta tidigt när den har fått tillräckligt många rader.

Ett vanligt B-trädindex lagrar bara den indexerade kolumnen samt en radpekare. När databasmotorn har hittat matchande poster måste den därför fortfarande gå till tabellen (heapen) för att läsa de andra kolumnerna som ni valde.

Det andra hoppet är en heap fetch. Det är billigt för några få rader men dyrt när en fråga matchar många rader, vilket är en anledning till att ett index med låg selektivitet ibland ignoreras. (Senare får ni se hur täckande index löser detta.)

Påstå aldrig att ett index används utan att bevisa det med EXPLAIN. När ni berättar om planen i en intervju visar ni att ni verkligen förstår den.

• Seq Scan betyder att indexet INTE användes.
• Index Scan eller Index Seek betyder att det användes.

Om ni har lagt till ett index men fortfarande ser en sekventiell skanning bedömde planeraren att skanningen var billigare, ofta eftersom frågan matchar en för stor andel av tabellen.

En vanlig intervjufälla är att deklarering av en PRIMARY KEY- eller UNIQUE-begränsning automatiskt skapar ett stödjande B-trädindex. Ni behöver inte, och bör inte, lägga till ett andra index på samma kolumn.

Det är därför joinningar och uppslagningar på primärnycklar redan är snabba, och därför frågan 'ska jag indexera id-kolumnen?' vanligtvis är en fälla: det är redan gjort åt er.

Knyt ihop det med en tydlig mening som intervjuaren kan nicka instämmande åt:

'Ett B-trädindex är en sorterad, balanserad struktur som låter databasmotorn hitta rader med log(N) sidläsningar i stället för att skanna hela tabellen. Det snabbar upp likhets-, intervall-, prefix- och ORDER BY-operationer på de indexerade kolumnerna, men varje träff medför fortfarande en heap fetch för kolumner som inte finns i indexet.'

Stöd sedan påståendet med EXPLAIN. Kombinationen av modell och belägg är det som ger poäng.

Viktiga slutsatser att ta med till nästa lektion:

• Ett B-träd lagrar indexerade värden sorterade i ett balanserat träd, vilket ger uppslagningar på log(N).
• Det snabbar upp likhet, intervall, prefix (inledande) LIKE, ORDER BY och MIN/MAX.
• Varje träff kräver fortfarande en heap fetch för kolumner som inte finns i indexet.
• Att omsluta en kolumn i en funktion eller använda ett inledande jokertecken inaktiverar indexet.
• Verifiera alltid med EXPLAIN; PRIMARY KEY- och UNIQUE-begränsningar indexeras automatiskt.

Nästa steg: hur ni ordnar kolumner när ett index täcker flera kolumner samtidigt.