Когда мы говорим про индексы в контексте дизайна распределенных систем, чаще всего подразумеваются индексы БД. При увеличении объема хранимых данных мы начинаем сталкиваться со слишком долгой обработкой запросов к БД. Чаще всего для решения задачи повышения производительности, мы можем использовать индексацию таблиц БД.
Индексы помогают нам увеличить скорость поиска данных в таблицах по определенным параметрам. Мы можем добавить индексы как для одной, так и для нескольких колонок в таблице.
При этом стоит помнить, что помимо существенного увеличения скорости получения данных, мы уменьшаем скорость добавления новых и изменения существующих.
Как работают индексы
Для того чтобы лучше разобраться с тем, как именно работают индексы, и как они увеличивают время чтения данных, рассмотрим простой пример.
Предположим, что у нас есть таблица events в которая имеет следующий вид:
В данной таблице у нас есть колонки event_type, description и triggered_by. У нас сотни миллионов событий. При этом мы знаем, что в нашей системе поиск событий происходит по комбинации колонок event_type + triggered_by.
Для увеличения скорости поиска по этим колонкам мы решаем добавить индекс IDX_EVENT_TYPE_TRIGGERED_BY.
Это означает, что мы создадим отдельную структуру данных в нашей БД, которая будет иметь следующий вид:
Таким образом, мы создаем структуру данных, в которой у нас есть записи, содержащие ключ поиска и указатель на место в памяти, где хранится эта запись. Порядок элементов для поиска, при этом, крайне важен. Т.е. petya@mail.com + ERROR не равен ERROR + petya@mail.com
Способ хранения и скорость поиска элемента в этой структуре данных зависит от его типа. Чаще всего, это:
- Бинарное дерево поиска (тип индекса по умолчанию во многих БД)
- B+ дерево
- Хэш-таблица
Запись данных при использовании индекса
При работе с индексами, мы должны индексировать изменения нашей таблицы. Т.е. данные записываются не только в исходную таблицу, но и структуру данных, которая хранит эти индексы. Например, при наличии индекса, который использует бинарное дерево поиска, вставка будет иметь временную сложность O(log N), вместо стандартной O(1). Таким образом мы получаем уменьшение производительности для операций:
- Вставки
- Изменения
- Удаления
Таблица, к которой часто обращаются на чтение и редко на запись данных лучше всего подходит для использования индексов.