Jaka jest najbardziej prawdopodobna złożoność czasowa (w notacji 'duże O') dla zapytania SELECT * FROM produkty WHERE status = 'dostepny', jeśli tabela produkty zawiera n wierszy, a kolumna status nie jest zindeksowana?

Poprawna odpowiedź: A (O(n))

Wskazana opcja O(n) jest poprawna. Dokładnie odpowiada zasadom i mechanizmom określonym w specyfikacji języka i technologii bazodanowych dla tego zagadnienia.

Dlaczego pozostałe opcje są nieprawidłowe?

• B: O(1) – Oznacza złożoność stałą. Taka złożoność jest charakterystyczna dla zapytań odwołujących się do jednego, konkretnego rekordu za pomocą unikalnego indeksu (np. klucza głównego: WHERE id = 123).
• C: O(log n) – Oznacza złożoność logarytmiczną. Jest to typowa i bardzo pożądana złożoność dla zapytań korzystających ze standardowego indeksu (np. B-drzewa). Indeks pozwala bazie danych bardzo szybko zlokalizować pasujące rekordy bez potrzeby skanowania całej tabeli.
• D: O(n²) – Oznacza złożoność kwadratową. Jest to bardzo słaba wydajność, rzadko spotykana w prostych zapytaniach SELECT na jednej tabeli. Może wystąpić przy bardzo nieefektywnych złączeniach (JOIN) wielu tabel bez odpowiednich indeksów.