Zasady działania indeksów: struktura danych i algorytmy wyszukiwania

Dzisiaj zanurzymy się głębiej w architekturę indeksów i zobaczymy, jak one naprawdę działają pod maską. Bo wiedza o tym, jak działa indeks, pomaga nie tylko zrozumieć, czemu zapytania są szybsze, ale też jak wybierać optymalne indeksy do różnych zadań.

Kiedy mówimy o strukturze indeksu, chodzi o to, jak dane są zorganizowane wewnątrz indeksu, żeby zapewnić szybkie wyszukiwanie. Wyobraź sobie szafkę z dokumentami. Jeśli dokumenty są po prostu wrzucone do jednej kupy, znalezienie właściwego będzie trudne. Ale jeśli szafka jest ułożona alfabetycznie, szukanie staje się dużo prostsze. Indeksy działają właśnie tak: porządkują dane tak, żeby wyszukiwanie potrzebnych informacji było maksymalnie szybkie.

Struktura B-TREE indeksu

B-TREE (balanced tree — zbalansowane drzewo) to najczęściej używany typ indeksu w PostgreSQL. W skrócie, to drzewiasta struktura, gdzie dane są zorganizowane w węzły, a wyszukiwanie odbywa się przez nawigację od korzenia drzewa do liści.

Jak to wygląda:

         Korzeń
          /       |       \
      Węzeł 1    Węzeł 2    Węzeł 3
     /   \       |       /   \
Liść1 Liść2   Liść3  Liść4 Liść5

Każdy węzeł zawiera kluczowe wartości, które pozwalają kierować wyszukiwanie. Na przykład, jeśli korzeń zawiera wartości [10, 20, 30], to:

• Wszystkie dane mniejsze niż 10 są w Liściu 1.
• Wszystkie dane między 10 a 20 — w Liściu 2, i tak dalej.

Zalety B-TREE indeksu:

• Szybkie wyszukiwanie danych: złożoność wyszukiwania to O(log n), co jest dużo szybsze niż wyszukiwanie liniowe.
• Idealny do wyszukiwania po zakresach (np. znaleźć wszystkie wartości między 10 a 50).

Przykład: załóżmy, że mamy tabelę students z kolumną age. Gdy tworzymy B-TREE indeks na tej kolumnie:

CREATE INDEX age_idx ON students (age);

PostgreSQL tworzy zbalansowane drzewo dla wartości wieku, co pozwala szybko znaleźć studentów o określonym wieku lub w określonym zakresie wiekowym.

Algorytm wyszukiwania w B-TREE

Kiedy wykonujesz zapytanie, PostgreSQL używa indeksu do wyszukiwania danych w taki sposób:

1. Określa klucz wyszukiwania (np. wiek 25).
2. Zaczyna od korzenia drzewa.
3. Porównuje klucz z zakresami wartości węzła i przechodzi do odpowiedniego węzła potomnego.
4. Powtarza krok 3, aż dotrze do liścia.
5. Zwraca dane z liścia, które odpowiadają kluczowi.

Przykład zapytania:

SELECT * FROM students WHERE age = 25;

Indeks zmniejsza ilość danych do przeskanowania, zapewniając szybkie wyszukiwanie.

Algorytmy wyszukiwania i wydajność

Indeksy przyspieszają wyszukiwanie przez zmniejszenie liczby wierszy do przeskanowania. Bez indeksu PostgreSQL skanuje całą tabelę (to się nazywa skanowanie sekwencyjne, czyli Seq Scan). Z indeksem wykonywany jest skan indeksowy (Index Scan), co jest dużo szybsze.

Porównanie skanowania sekwencyjnego i indeksowego

• Skanowanie sekwencyjne (Seq Scan):

  • PostgreSQL czyta każdy wiersz tabeli, sprawdza warunki zapytania i zwraca pasujące wiersze.
  • Używane, jeśli nie ma indeksu lub jeśli zapytanie obejmuje prawie wszystkie wiersze tabeli.

• Skan indeksowy (Index Scan):

  • PostgreSQL używa indeksu do znalezienia pasujących wierszy, a potem sięga do tabeli tylko po nie.
  • Dużo szybsze dla dużych tabel, jeśli zapytanie dotyczy małej próbki danych.

Przykład: bez indeksu wyszukiwanie wieku

SELECT * FROM students WHERE age = 25;

rezultat może wymagać przeczytania 1 miliona wierszy. Z indeksem B-TREE system, na przykład, czyta tylko 100 wierszy.

Wpływ struktury indeksu na wydajność

Indeksy działają szybciej, bo zmniejszają ilość danych do przeskanowania. Na przykład, jeśli w tabeli są miliony wierszy, indeks organizuje je tak, że zapytanie musi przeczytać tylko kilka węzłów zamiast całej tabeli.

Bardzo ważne jest rozumienie struktury indeksu. Wiedza, jak dokładnie działają indeksy, pomaga zrozumieć, czemu niektóre zapytania są wolne i jak je przyspieszyć.

Poza tym ważne jest, jakie indeksy stosować. Do wyszukiwania po zakresach najlepszy jest B-TREE. Do tablic lub JSONB — GIN. Zły wybór indeksu może spowolnić bazę.

Prawdziwe przykłady

Zobaczmy, jak indeksy pomagają nam w pracy.

Indeks do sortowania

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

Z indeksem B-TREE PostgreSQL może zwrócić posortowane dane bezpośrednio z indeksu, bez dodatkowego sortowania.

Indeks do zakresów

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

Indeks B-TREE pozwala szybko znaleźć wiersze mieszczące się w zadanym zakresie.

Częste pytania i pułapki

Czemu nie zawsze warto używać indeksów? Indeksy zajmują miejsce na dysku i spowalniają operacje INSERT, UPDATE i DELETE, bo trzeba aktualizować strukturę indeksu. Dlatego warto tworzyć indeksy tylko dla często używanych kolumn.

Kiedy indeksy nie pomagają? Dla zapytań obejmujących większość tabeli (np. WHERE true), PostgreSQL wybierze Seq Scan, bo czytanie węzłów indeksu nie daje przewagi.