Indeksowanie

Cześć, mógłby mi ktoś wytłumaczyć na czym polega indeksowanie bazy danych? Drugie pytanie czy wszystkie bazy danych SQLowe przedstawiają drzewiastą strukture danych?

Indeksowanie w skrócie polega na utworzeniu dla danej kolumny lub zbioru kolumn obiektu, który przyspiesza wyszukiwanie danej wartości w tejże kolumnie/kolumnach.
Najczęściej jest to tzw. B-drzewo, które można sobie wyobrazić jako pień i gałęzie. Podając jakąś wartość do wyszukania baza sprawdza czy od korzenia ma iść w lewo czy w prawo w strukturze drzewa (czyli czy podana wartość jest większa czy mniejsza niż element indeksu w danym węźle drzewa). Po tej decyzji idzie na kolejny poziom i znów sprawdza większe/mniejsze. Jak dojdzie do ostatniego poziomu to sprawdza już niewielką liczbę liści indeksu i znajduje właściwą wartość klucza indeksu (czyli tą podaną w WHERE). Wtedy pobiera adres fizyczny tego rekordu i przechodzi do tabeli zwracając ten rekord.
To tak w uproszczeniu :)

W porównaniu do sekwencyjnego dostępu do tabeli, wyszukiwanie po drzewie unikalnej wartości wymaga zaledwie kilku odczytów elementów indeksu. Przy nieunikalnej jest już więcej i zależy od liczby i rozkładu danych w kolumnie, bo trzeba wtedy przeszukiwać pewne zakresy indeksu, a nie od razu konkretne elementy.