Czym jest B-Tree (drzewo zrównoważone)?

B-Tree (Drzewo zrównoważone) - to struktura danych, która jest używana w bazach danych do szybkiego wyszukiwania, wstawiania i usuwania rekordów. Jest zorganizowana w formie drzewa, gdzie każdy węzeł zawiera klucze i odnośniki do węzłów potomnych. Wszystkie klucze w jednym węźle są uporządkowane, a inne węzły zawierają same dane lub odnośniki do wierszy tabeli. Główną zaletą B-Tree jest balans: wysokość drzewa pozostaje minimalna, co zapewnia wyszukiwanie w czasie logarytmicznym.

Indeksy w bazach danych działają właśnie na podstawie B-Tree (w PostgreSQL i MySQL domyślnie). Kiedy tworzysz indeks na kolumnę, baza danych buduje drzewo na podstawie wartości tej kolumny. To pozwala szybko znajdować potrzebne rekordy bez pełnego skanowania tabeli. Na przykład zapytanie WHERE email = '[email protected]' wykorzystuje indeks, aby od razu przejść do węzła z odpowiednim emailem zamiast sprawdzać wszystkie wiersze.

W Rails indeksy są tworzone za pomocą migracji. Na przykład w PostgreSQL:

class AddIndexToUsersEmail < ActiveRecord::Migration[7.0]
  def change
    add_index :users, :email, unique: true
  end
end

Ten indeks zapewnia szybkie wyszukiwanie użytkownika po emailu i gwarantuje unikalność wartości. W MySQL składnia migracji jest taka sama, ponieważ Rails abstrahuje konkretną SGBD.

Wewnątrz baza buduje B-Tree na podstawie wartości kolumny email, a każde wyszukiwanie przez ten indeks przechodzi przez węzły drzewa, a nie przez całą tabelę. To znacznie zwiększa szybkość zapytań, szczególnie w dużych tabelach.

Jeśli krótko - tak. Ale jest pewien szczegół. Indeksy w bazie danych są widoczne, chociaż nie są przechowywane jako oddzielne tabele w tradycyjnym sensie. Każda SGBD udostępnia sposoby, aby zobaczyć, jakie indeksy istnieją na tabeli oraz ich właściwości.

W PostgreSQL można zobaczyć indeksy za pomocą polecenia:

\d users

lub przez katalogi systemowe:

SELECT indexname, indexdef
FROM pg_indexes
WHERE tablename = 'users';

To pokaże nazwy indeksów, kolumny, na których zostały utworzone, oraz typ indeksu (B-Tree domyślnie).

W MySQL indeksy można zobaczyć w ten sposób:

SHOW INDEX FROM users;

Tu będzie lista wszystkich indeksów tabeli users, kolumny, typ indeksu (BTREE lub inny), unikalność oraz porządek sortowania.

W Rails można zobaczyć indeksy przez konsolę:

ActiveRecord::Base.connection.indexes(:users)

Wynik pokaże tablicę obiektów z informacjami o każdym indeksie: nazwa, kolumny, unikalność.

To znaczy, że indeksy rzeczywiście istnieją w bazie, i można się do nich odwoływać oraz analizować ich strukturę, nawet jeśli nie są wyświetlane jako zwykła tabela.