Сегодня, продолжая 3-ю главу, опять поговорим о том, какие бывают индексы и как их правильно использовать.

Индексы могут быть кластеризованными (по ключу хранятся все данные) или некластеризованными (по ключу хранится ссылка на данные). Например, InnoDB в MySQL - использует кластеризованные индексы, т.е. когда мы делаем запрос с индексом, сначала идёт поиск в memory-структуре, в зависимости от типа индекса, и затем, в случае успеха, мы сразу можем получить запрашиваемые данные. У некластеризованных индексов в случае успешно найденного значения, представляющего ссылку, нам потребуется выполнить переход по ней, считать значение и только потом его вернуть.
Бывает так же и компромисс между кластеризованным и некластеризованным - охватывающий индекс. Этот тип индекса хранит в себе не всю строку, а часть столбцов. Как правило, эта та часть, которая чаще всего запрашивается запросами.

Если мы запрашиваем сразу несколько столбцов строки, то нам могут потребоваться составные индексы. Самый частый тип составных индексов - сцепленные индексы: объединение нескольких полей в один ключ, например: имя-фамилия.
Второй по популярности тип составных индексов - многомерные индексы, особенно часто они используются при работе с пространственными данными, например, при работе с PostGIS от Postgres. Для многомерных пространственных индексов используются R-деревья, позволяющие производить поиск по многомерным данным.
Многомерные индексы применяются не только для работы с адресами. Например, можно использовать двумерный индекс (год, температура), чтобы одним запросом найти данные за 2013 год, когда температура была -20 градусов. Иначе, без многомерных индексов, нам придётся сначала найти все данные за 2013 год, а затем фильтровать их по температуре.

Интересная, в плане использования индексов, тема - полнотекстовый поиск. Например, известные индексы Lucene, лежащие в основе эластики, хранят словарь термов в SS-структуре (которую я описывал в прошлый раз), а рядом с этой структурой они хранят небольшой индекс, который описывает, как разбивается (на буквы, или на триграммы, или как-то иначе) каждый терм. На всё это накладываются различные алгоритмы, например конечный автомат в связке с расстоянием Левенштейна, что позволяет очень быстро искать слова по заданному соответствию.

Все описанные выше структуры так или иначе подразумевают запись на диск. Хотя основная работа происходит в оперативной памяти, в случае с LSM-таблицами на диске у нас хранятся уплотнённые сегменты, а в случае с B-деревьями на диске у нас хранится информация, куда ссылается B-дерево. И, само собой, на диске хранятся данные самих таблиц.
По мере удешевления RAM у дискового хранения остался 1 аргумент над хранением в оперативной памяти: надёжность. Хотя в последние годы, благодаря различным инструментам и подходам (репликации на разные сетевые копии; память, питаемая от отдельного аккумулятора; ротация журнала состояния на диск) появилась возможность хранить данные только в оперативной памяти. Уже существуют несколько РСУБД, которые работают в RAM: VoltDB, MemSQL, Oracle TimesTen.