Как устроены индексы в памяти и как они организованы
Что проверяют
Понимаете ли вы, что индекс это структура данных со своей формой и ценой, а не галочка в миграции. Для C#-разработчика вопрос обычно про SQL Server или PostgreSQL, с которыми вы работаете через EF Core, а следом спрашивают, почему конкретный запрос индекс не взял.
Как отвечать
Начните с того, как индекс лежит физически. Основная форма это B+-дерево из страниц по 8 КБ (так и в SQL Server, и в PostgreSQL по умолчанию):
- корень и промежуточные уровни: только ключи и ссылки на страницы ниже, поэтому дерево низкое, три-четыре уровня даже на миллионах строк;
- листовой уровень: отсортированные ключи, связанные в список, отсюда дешёвые диапазоны и
ORDER BY; - кластерный индекс: в SQL Server его листья и есть сама таблица, строки лежат в порядке ключа, поэтому такой индекс у таблицы один;
- некластерный индекс: в листьях ключ и ссылка на строку (ключ кластерного индекса или RID для кучи). Если нужных колонок в индексе нет, в плане появляется Key Lookup, лечится через
INCLUDE; - хэш-индекс: есть у memory-optimized таблиц In-Memory OLTP, работает только на точное равенство, важно правильно задать
BUCKET_COUNT.
«В памяти» здесь значит буферный пул: СУБД читает страницы индекса с диска и держит горячие в RAM, поэтому верхние уровни дерева почти всегда уже там.
Хорошо добавить аналогию из самого .NET: Dictionary<TKey,TValue> устроен как хэш-индекс, SortedDictionary как сбалансированное красно-чёрное дерево, и выбор между ними тот же: равенство против порядка. В EF Core индекс объявляется через HasIndex() или атрибут [Index].
Где спотыкаются
Путают кластерный индекс с первичным ключом. В SQL Server первичный ключ по умолчанию создаёт кластерный индекс, но это настраивается, а в PostgreSQL таблица всегда куча, и команда CLUSTER лишь один раз переупорядочивает строки.
Не учитывают порядок колонок в составном индексе: индекс по (LastName, FirstName) не поможет поиску по одному FirstName.
Пишут условие, которое мешает поиску по индексу: функция над колонкой, неявное приведение типов (параметр nvarchar против колонки varchar) или LIKE '%текст' с ведущим подстановочным знаком.