индекс в базе данных это

Ответ от Голый Мужик[гуру]
Излагаю суть, не привязываясь к реализациям, чтоб понятней было. Грубо говоря, индексирование - сортировка данных по определённому набору полей заранее. Например, если у вас есть таблица Emloyee с полями Id, FirstName, LastName, Salary и индекс по полям FirstName и LastName, то при запросеselect * from Employee where (Salary > 1000) order by FirstName, LastNameто данные будут браться не из таблицы Employee, а из индекса, то есть поиск будет выполняться среди уже отсортированных данных. Выгода от использования индесксов значительна: если в неотсортированном массиве длиной N сложность поиска элемента составляет O(N), то в отсортированном - O(log(N)) и меньше (хотя, на самом деле, в СУБД применяется хеширование, при котором сложность поиска предельно приближается к O(1)). Сложность сортировки массива - O(N*log(N)), а при индексации необходимость в сортировке отпадает. По первичному ключу индекс создаётся СУБД автоматически.