Как устроены составные индексы? На примере PostgreSQL.

#postgresql #sql

1) есть 2 поля - varchar 'text' и int 'value'. По ним создан индекс:

CREATE INDEX idx_index_value_and_text
ON index_test ( value, text )

Пишу:

select * from index_test r where
r.text='some value'

Анализатор говорит:

Index Scan using
idx_index_value_and_text on index_test

Вопрос: как он может искать по индексу, если первая колонка не указана? В терминах
 B-Tree - что представляет собой составной индекс: единое дерево, значения нод которого
есть concatenation строк значений входящих в него полей? 
2) Данный поиск в зависимости от распределения значений колонок имеет разные типы:
Bitmap Heap Scan и Bitmap Index Scan, либо Index Scan если распределение достаточное
ровное. Что означают Bitmap-типы, чем отличается Bitmap Index Scan от Index Scan? Кроме
того, есть ли в Postgres Index Range Scan?    

Ответы

Ответ 1

Составной индекс, в отличие от "одинарного" индекса в качестве индексируемого значения
использует не одно значение, а несколько значений то есть если есть 2 поля A и B то
составной индекс по ним будет выглядеть примерно так:
| A | B | 
---------
| 1 | 1 | 
| 1 | 2 | 
| 1 | 4 | 
| 2 | 2 | 
| 2 | 3 | 
| 2 | 5 |

Грубо говоря это сортировка по двум полям, а не одному полю. То есть это не индексирование
конкатенированных значений A+B.
На уровне BTree это выглядит как будто листочки BTree отвечающие за поле A, ссылаются
на вложенное дерево BTree отвечающее за поле B.
Сканирование индекса в вашем случае фактически означает, что поскольку первое поле
у вас не задано, то сервер сканирует все листочки дерева A, чтобы найти подходящее
значение поля B.
Составной индекс полезен когда информация может быть кластеризована: скажем по этому
принципу устроены словари/энциклопедии. Вам нужна статья на букву "Д" - вы находите
по оглавлению раздел на букву "Д" и далее ищете нужную статью. А вот если нужна статья
заканчивающаяся на "К" - то кластеризация уже не поможет - придется рыться во всей
книге (сканировать индекс).