Использование индекса b-tree для нескольких столбцов в таблице
Насколько мне известно, одним из наиболее распространенных индексов в базе данных является тот, который использует b-tree.
Если у меня есть индекс для целочисленного столбца
column1 column2
2 name2
3 name3
1 name4
он может создать индекс, который выглядит так
2
| |
1 3
Если я использую column2, он может создать его так
name2
| |
name1 name3
Но если у меня есть составной индекс с двумя полями, как он тогда его упорядочит? Будет ли это просто базовое сравнение для двух столбцов?
Есть ли какие-то другие дополнительные оптимизации, которые база данных выполняет для структуры индекса?
@jarlh ho, значит, в зависимости от поставщика индекс b-дерева может отличаться? Я думал, что все используют одни и те же алгоритмы
@jarlh Меня интересует общий обзор всех dbms. Хотя сам использую postgres
Что ж, возможно, они это сделают. Еще лучше получить ответы от людей, знающих Postgresql.
@jarlh Я не особо забочусь о вендоре. Я просто хочу посмотреть, как это вообще реализовано независимо от dbms
Наверное, самое подробное описание здесь: github.com/postgres/postgres/blob/master/src/backend/access/…
Ответы 1
Все несколько ключей используются вместе в индексе:
2,name2
| |
1,name4 3,name3
Сравнение производится по первому ключе. Только в случае завязки используется следующий ключ. Итак, если бы все числа были одинаковыми, у вас было бы:
2,name2
| |
2,name3 2,name4
Так что если я поставлю 2, name5 для первого случая, он отправит его вправо на лист 3, name3?
Если у вас 2, name5, то «2» равны, и name5> name2, поэтому он будет идти вправо.
Я понимаю. Но, в конце концов, это отдельная структура, на которую ссылается исходная таблица?
@lapots. . . да. Postgres даже не поддерживает кластерные индексы, поэтому структура всегда отдельная. В базах данных, поддерживающих кластерный индекс, конечные узлы кластерного индекса являются страницами данных. Но фактическая иерархия индекса всегда отделена от данных.
так иерархия - это отдельная сущность? Я думал, что он хранит все как единую структуру
@lapots. . . Индексы - это отдельные сущности. Являются ли они «частью стола» - вопрос скорее логичный. Данные для индекса не хранятся на страницах данных, используемых для таблицы.
Я понял, что индексы - это отдельные объекты, но я не уверен, что понимаю, как он хранит иерархию (насколько я понимаю, данные индекса хранятся как какой-то упорядоченный набор)
@lapots. . . Ключи дублируются в структуре индекса. Я думаю, что может быть документация по подробной структуре.
Какие СУБД вы используете? (Это вопрос, относящийся к конкретному продукту, поскольку в продуктах индексы реализуются по-разному.)