Как устроены составные индексы? На примере PostgreSQL.
1,00
р.
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?
Ответ
Составной индекс, в отличие от "одинарного" индекса в качестве индексируемого значения использует не одно значение, а несколько значений то есть если есть 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.
Составной индекс полезен когда информация может быть кластеризована: скажем по этому принципу устроены словари/энциклопедии. Вам нужна статья на букву "Д" - вы находите по оглавлению раздел на букву "Д" и далее ищете нужную статью. А вот если нужна статья заканчивающаяся на "К" - то кластеризация уже не поможет - придется рыться во всей книге (сканировать индекс).
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?
Ответ
Составной индекс, в отличие от "одинарного" индекса в качестве индексируемого значения использует не одно значение, а несколько значений то есть если есть 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.
Составной индекс полезен когда информация может быть кластеризована: скажем по этому принципу устроены словари/энциклопедии. Вам нужна статья на букву "Д" - вы находите по оглавлению раздел на букву "Д" и далее ищете нужную статью. А вот если нужна статья заканчивающаяся на "К" - то кластеризация уже не поможет - придется рыться во всей книге (сканировать индекс).
