Индексация

Применительно к БД.
Основная структура хранения в реляционной БД - таблица. Допустим, таблица сотрудников, в которой, помимо прочего, есть ссылка на подразделение, в котором они работают. Запрос на получение всех сотрудников подразделения с id = 10. Если нет индекса, то единственный способ выборки - т.н. full scan, т.е. полный просмотр всей таблицы. Если такие запросы выполняются часто, а таблица большая, то можно создать индекс по этому полю (колонке). Индекс в большинстве случаев - это бинарное дерево, в листьях которого содержится значение ключевого столбца (хотя м.б. индекс и по нескольким столбцам) и уникальный адрес соответствующей строки. Т.о. мы можем читать листья (блоки) индекса с нужными значениями (они обычно меньше, чем строки таблицы, поэтому читаются быстрее), по ним находить адрес нужной строки и уже по нему выбирать нужную строку. В каждом конкретном случае вопрос выбор способа доступа: full scan или с пом. индекса определяет оптимизатор СУБД. Обычно, если надо выбирать небольшой процент строк от общего числа (например, 10%), то выгоднее использование индекса, если большой - использовать full scan.
Там конечно еще куча всяких ньюансов, но в первом приближении так.

Что касаемо других индексов, то есть, например, массивы с индексами. Т.е. я к элементу могу обращаться не по имени, а по индексу, что позволяет использовать циклы в обработке массивов (цифры очень удобно в цикле наращивать).

1