Хэш индекс что это
PostgreSQL поддерживает несколько типов индексов: B-дерево, хеш, GiST, SP-GiST, GIN и BRIN. Для разных типов индексов применяются разные алгоритмы, ориентированные на определённые типы запросов. По умолчанию команда CREATE INDEX создаёт индексы-B-деревья, эффективные в большинстве случаев. Выбрать другой тип можно, написав название типа индекса после ключевого слова USING . Например, создать хеш-индекс можно так:
хеш-индекс в MySQL
MEMORY - это особый тип механизма хранения в MySQL. Он использует содержимое, хранящееся в памяти, для создания таблицы, а все данные находятся в памяти. Эти характеристики сильно отличаются от двух предыдущих.
В механизме памяти по умолчанию используется хэш-индекс, а теоретическая временная сложность запроса хеша составляет O (1), что означает, что независимо от того, сколько данных вам нужно найти в хеш-индексе один раз, вы можете их найти.
Что такое хеш-индекс?
Проще говоря, хеш-индекс заключается в использовании определенного хэш-алгоритма для преобразования значения ключа в новое хеш-значение. При поиске нет необходимости искать от корневого узла до уровня листового узла по уровню, как в дереве B +, всего один алгоритм хеширования.Сразу найдите соответствующую позицию, скорость очень высокая.
Это схематическая диаграмма хеш-индекса в Интернете. Для поля устанавливается хеш-индекс. Затем значение ключа будет сгенерировано с помощью алгоритма хеширования, чтобы сгенерировать адрес для хранения значения ключа. Когда вы вернетесь в следующий раз, вам нужно только преобразовать значение ключа в хеш-адрес. Адрес принимает значение. Видно, что адрес сохраняется на диске нерегулярно.
Поскольку расположение данных, хранящихся в хеш-индексе на диске, является случайным, хеш-индекс имеет большие недостатки.
(1) Хеш-индекс может удовлетворять только запросам «=», «IN» и «» и не может использовать запросы диапазона.
Поскольку индекс хеширования сравнивает значение хеширования после операции хеширования, он может использоваться только для эквивалентной фильтрации и не может использоваться для фильтрации на основе диапазона, потому что после соответствующего
Не гарантируется, что соотношение размеров значения хеширования после обработки алгоритма хеширования будет точно таким же, как до операции хеширования.Например, поле возраста: 10, 20, 30, 40 и адрес хранения: 0x6aeb, 0x98f7, 0x652a, 0x74d1
Если я хочу найти людей старше 20 лет, этого легко добиться с помощью btree, потому что btree - это отсортированная структура, а хеш - неупорядоченный, а 20 обрабатывается алгоритмом хеширования. Адрес 0x98f7, но он не может найти данные больше 20, потому что они не в порядке.
(2) Хеш-индекс нельзя использовать, чтобы избежать операций сортировки данных.
Поскольку в индексе хеширования хранится значение хеша после вычисления хеша, а соотношение размеров значения хеширования не обязательно точно такое же, как значение ключа перед операцией хеширования, база данных не может использовать индексированные данные, чтобы избежать операции сортировки.
(3) Хеш-индекс не может использовать некоторые ключи индекса для запроса.
Для индекса с несколькими столбцами при вычислении значения Hash индекса Hash ключ индекса с несколькими столбцами объединяется, а затем значение Hash вычисляется вместе, а не вычисляется Hash отдельно.
, поэтому при запросе через первый или несколько индексных ключей многостолбцового индекса нельзя использовать хеш-индекс.Для индексов с несколькими столбцами, таких как (id, name), в btree, даже если индекс использует только id или name, адрес можно найти в дереве индекса. Но в хэш-индексе и id, и name преобразуются алгоритмом хеширования, поэтому, если вы используете только id или name, вы не можете найти местоположение данных.
(4) Хеш-индекс не может избежать сканирования таблицы в любое время.
Индекс хеширования предназначен для хранения значения хеширования результата операции хеширования и соответствующей информации указателя строки в таблице хеширования после того, как ключ индекса является операцией хеширования. Поскольку разные ключи индекса имеют одинаковое значение хеширования, даже если определенное значение ключа хеширования удовлетворяется Количество записей данных нельзя напрямую запросить из индекса хеширования. По-прежнему необходимо сравнить фактические данные в таблице и получить соответствующие результаты.
Проще говоря, даже алгоритм хеширования не гарантирует, что значение хеш-функции, полученное после обработки каждого значения, будет другим.
(5) Эффективность индекса хеширования не обязательно выше, чем у индекса B-дерева после обнаружения большого количества одинаковых значений хеширования.
Для индексных ключей с относительно низкой селективностью, если создается хеш-индекс, будет большой объем информации указателя записи, связанной с одним и тем же значением хеширования. Найти запись таким способом будет очень проблематично, и это приведет к потере множества обращений к данным таблицы, что приведет к низкой общей производительности.
11.2.1. B-дерево
B-деревья могут работать в условиях на равенство и в проверках диапазонов с данными, которые можно отсортировать в некотором порядке. Точнее, планировщик запросов PostgreSQL может задействовать индекс-B-дерево, когда индексируемый столбец участвует в сравнении с одним из следующих операторов:
При обработке конструкций, представимых как сочетание этих операторов, например BETWEEN и IN , так же может выполняться поиск по индексу-B-дереву. Кроме того, такие индексы могут использоваться и в условиях IS NULL и IS NOT NULL по индексированным столбцам.
Также оптимизатор может использовать эти индексы в запросах с операторами сравнения по шаблону LIKE и ~ , если этот шаблон определяется константой и он привязан к началу строки — например, col LIKE 'foo%' или col ~ '^foo' , но не col LIKE '%bar' . Но если ваша база данных использует не локаль C, для поддержки индексирования запросов с шаблонами вам потребуется создать индекс со специальным классом операторов; см. Раздел 11.10. Индексы-B-деревья можно использовать и для ILIKE и ~* , но только если шаблон начинается не с алфавитных символов, то есть символов, не подверженных преобразованию регистра.
B-деревья могут также применяться для получения данных, отсортированных по порядку. Это не всегда быстрее простого сканирования и сортировки, но иногда бывает полезно.
Темная сторона индексов
Если индексы такие крутые и так сильно помогают СУБД в работе, то почему бы нам не построить индексы на все поля для всех таблиц?
Вот сейчас мы и пришли к темной стороне индексов. Действительно это очень крутой инструмент, но он не бесплатен.
Индексы занимают место на диске и в памяти. К примеру на нашей тестовой таблице с 9 млн. записей хеш-индекс по полю salt занимает 256Мб, а b-tree индекс уже 507 Мб.
Индексы замедляют запись в таблицу, так как базе данных необходимо поддерживать индексы в консистентном состоянии, а для этого их нужно обновлять (перестраивать) в случае обновления данных.
Специфика структуры хеш-индекса, его Эффективность извлечения очень высока. Извлечение индекса может происходить одновременно. В отличие от индекса B-Tree, который требует многократного доступа ввода-вывода от корневого узла к узлу ветвления и, наконец, к узлу страницы, эффективность запроса индекса хеширования намного выше, чем у индекса B -Дерево указатель 。
У многих снова могут возникнуть вопросы: поскольку эффективность Hash index намного выше, чем у B-Tree, почему не все используют Hash index, а B-Tree index? У всего есть две стороны, и то же самое верно для индексов хеширования. Хотя хеш-индекс очень эффективен, сам хеш-индекс также приносит много пользы из-за своей специфики.Ограничения и недостатки, Есть в основном следующие.
(1) Хеш-индекс может удовлетворять только запросам «=», «IN» и «» и не может использовать запросы диапазона.
Поскольку индекс Hash сравнивает значение Hash после операции Hash , Поэтому его можно использовать только Эквивалентная фильтрация , Не может использоваться для фильтрации на основе диапазона, поскольку соотношение величин значения хеширования после обработки соответствующего алгоритма хеширования не обязательно будет точно таким же, как до операции хеширования.
(2) Хеш-индекс нельзя использовать, чтобы избежать операций сортировки данных 。
Поскольку индекс хеширования сохраняет значение хеширования после вычисления хеширования, и соотношение размеров значения хеширования не обязательно совпадает с значением ключа до операции хеширования. Следовательно, база данных не может использовать индексированные данные, чтобы избежать операций сортировки;
(3) Индекс хэша не может быть запрошен некоторыми ключами индекса.
Для составного индекса при вычислении значения Hash индекса Hash ключ составного индекса объединяется, а затем значение Hash вычисляется вместе, вместо того, чтобы вычислять значение Hash отдельно, поэтому При запросе через один или несколько предыдущих индексных ключей составного индекса нельзя использовать хэш-индекс.
(4) Индексы хеширования не могут избежать сканирования таблиц в любое время.
Я знал раньше,Хеш-индексОн предназначен для хранения значения хеширования результата операции хеширования и соответствующей информации указателя строки в таблице хеширования после того, как ключ индекса проходит операцию хеширования. Поскольку разные ключи индекса имеют одинаковое значение хэша , Следовательно, даже если берется количество записей данных, которые соответствуют определенному значению ключа хеширования, запрос не может быть выполнен напрямую из индекса хеширования, и необходимо получить доступ к фактическим данным в таблице для соответствующих сравнений и соответствующих результатов.
(5) Эффективность индекса хеширования не обязательно выше, чем у индекса B-дерева после обнаружения большого количества одинаковых значений хеширования.
за Селективность Для относительно низкого ключа индекса, если создается хеш-индекс, будет большое количество информации указателя записи, связанной с одним и тем же значением хеширования. Найти запись таким способом будет очень сложно, это приведет к потере множественного доступа к данным таблицы и снижению общей производительности.
2. Индекс B-дерева
Индекс B-Tree является наиболее часто используемым типом индекса в базе данных MySQL. Все механизмы хранения, кроме механизма хранения архивов, поддерживают индекс B-Tree. Не только в MySQL, но и во многих других системах управления базами данных индекс B-Tree также является наиболее важным типом индекса, потому что структура хранения индекса B-Tree находится в поиске данных из базы данных. Имеет очень хорошую производительность. Вообще говоря, физические файлы индекса B-Tree в MySQL в основном хранятся в структуре Balance Tree, то есть все фактически необходимые данные хранятся в Leaf Node дерева, а кратчайший путь к любому Leaf Node. Длина точно такая же, поэтому все мы называем это индексом B-дерева. Конечно, различные базы данных (или различные механизмы хранения MySQL) могут немного изменить структуру хранения при сохранении своих собственных индексов B-Tree. Преобразование. Например, структура хранения, фактически используемая индексом B-Tree подсистемы хранения Innodb, на самом деле является B + Tree, то есть небольшое преобразование выполняется на основе структуры данных B-Tree, и ключ индекса хранения создается на каждом конечном узле. В дополнение к соответствующей информации, он также сохраняет информацию указателя на следующий LeafNode, смежный с Leaf Node. Это в основном предназначено для ускорения эффективности извлечения нескольких соседних Leaf Node. В механизме хранилища Innodb существует две разные формы индекса: один - это индекс первичного ключа (первичный ключ) в форме кластера, а другой - обычный B-, который в основном совпадает с другими механизмами хранения (например, механизм хранения MyISAM). Индекс дерева, этот индекс называется вторичным индексом в механизме хранения Innodb. Давайте воспользуемся диаграммой ниже, чтобы сравнить форматы хранения этих двух индексов. Чтобы
На рисунке левая сторона - это первичный ключ, хранящийся в кластерном формате, а правая сторона - это обычный индекс B-дерева. Два корневых узла и ответвления по-прежнему точно такие же. Узлы листьев разные. В Prim в Leaf Nodes хранятся фактические данные таблицы, а не только данные поля первичного ключа, но также данные других полей в упорядоченном порядке на основе значения первичного ключа. Вторичный индекс мало чем отличается от других обычных индексов B-дерева.Листовые узлы не только хранят релевантную информацию о ключе индекса, но также хранят значение первичного ключа Innodb. Чтобы
Следовательно, в Innodb, если доступ к данным осуществляется через первичный ключ, эффективность очень высока, и если доступ к данным осуществляется через вторичный индекс, Innodb сначала использует соответствующую информацию вторичного индекса и извлекает конечный узел через соответствующий индексный ключ. Получите соответствующую строку данных через значение первичного ключа, хранящееся в Leaf Node, а затем через индекс первичного ключа. Разница между индексом первичного ключа и индексом непервичного ключа механизма хранения MyISAM очень мала, за исключением того, что индексный ключ индекса первичного ключа является уникальным и непустым ключом. Более того, структура хранения индекса механизма хранения MyISAM и вторичного индекса Innodb в основном одинакова.Основное отличие состоит в том, что механизм хранения MyISAM хранит информацию о ключах индекса на конечных узлах, а затем сохраняет соответствующие, которые могут быть непосредственно расположены в файле данных MyISAM Информация о строке данных (например, номер строки), но не хранит информацию о значении ключа первичного ключа.
Индексы - это наиболее распространенный инструмент, используемый в базах данных для повышения производительности. Все типы столбцов MySql могут быть проиндексированы. Индекс используется для быстрого поиска строки с определенным значением в определенном столбце. Если вы не используете индексы, MYSQL должен начинать с первой записи, а затем читать всю таблицу, пока не найдет соответствующие строки. Обычно используются индексы BTREE и HASH.
Удалить оператор индекса:
Правила построения индексов:
- Наиболее подходящий столбец для индексации - это столбец, который появляется в предложении where, или столбец, указанный в предложении соединения, а не столбец, который появляется в списке выбора после ключевого слова select.
- Чем выше мощность проиндексированного столбца, тем лучше индекс.
- Попробуйте использовать короткие индексы. Может сэкономить много места для индекса, а также ускорить выполнение запросов.
- Не переоценивайте. Индексы занимают дополнительное дисковое пространство и снижают производительность операций записи. При изменении содержимого таблицы индекс должен быть обновлен, а иногда может потребоваться его восстановление.
Сравнение индекса BTREE и индекса HASH
1. Индекс B-дерева
Значения, хранящиеся в индексе, упорядочены в столбце индекса. Вы можете использовать индекс B-Tree для поиска полных ключевых слов, диапазонов ключевых слов и префиксов ключевых слов. Если вы используете индекс, вы должны убедиться, что запрос выполняется по крайнему левому префиксу индекса. Поскольку узлы в B-дереве хранятся последовательно, результаты запроса можно упорядочить по.
1) Запрос должен начинаться с крайнего левого столбца индекса.
2) Определенный столбец индекса нельзя пропустить.
3) Механизм хранения не может использовать столбец справа от условия диапазона в индексе.
Например, если ваш запрос - WHERE last_name = ”Smith” AND first_name LIKE'J% 'AND dob =' 1976-12-23 ', запрос будет использовать только первые два столбца в индексе, потому что LIKE - это запрос диапазона .
2. Хеш-индекс
Только механизм хранения в памяти в MySQL показывает, что он поддерживает хэш-индекс, который является типом индекса по умолчанию, а также поддерживает индекс B-Tree.
Если несколько значений имеют один и тот же хэш-код, индекс сохраняет указатели на их строки в одной записи хеш-таблицы в связанном списке.
Поскольку сам индекс хранит только очень короткие значения, индекс очень компактен, и значение хеш-функции не зависит от типа данных столбца.
Индекс столбца int равен индексу столбца с длинной строкой.
- Индекс HASH подходит для операций сравнения на равенство. Его нельзя использовать для ускорения порядка по операциям, а также невозможно определить количество строк между двумя значениями, что повлияет на эффективность выполнения некоторых запросов. И только ключевое слово целиком может использоваться для поиска строки.
- Индекс BTREE можно использовать при использовании операторов больше, меньше, BETWEEN, не равно и LIKE. При выполнении запроса диапазона в поле индекса через индекс можно получить доступ только к индексу BTREE. Индекс HASH фактически представляет собой полное сканирование таблицы.
Если вы индексируете несколько столбцов, порядок столбцов очень важен, и MySQL может эффективно искать только крайний левый префикс индекса.
Предполагая, что существует составной индекс it1c1c2 (c1, c2), оператор запроса select * from t1, где c1 = 1 и c2 = 2 может
Используйте этот индекс. Оператор запроса select * from t1, где c1 = 1, также может использовать этот индекс.
Однако оператор запроса select * from t1, где c2 = 2, не может использовать индекс.
Поскольку в составном индексе нет ведущего столбца, то есть, если вы хотите использовать столбец c2 для поиска, c1 должен быть равен определенному значению.
Индекс реализован в механизме хранения, а не на уровне сервера. Следовательно, индекс каждого механизма хранения не
Он должен быть точно таким же. Не все механизмы хранения поддерживают все типы индексов.
Стратегия высокопроизводительного индексирования
1. Кластерный индекс
Кластерный индекс гарантирует, что физическое расположение кортежей с похожими значениями ключей также будет одинаковым (поэтому строковый тип не подходит для создания кластеризованного индекса,
В частности, случайные строки заставят систему выполнять множество операций перемещения), а таблица может иметь только один кластерный индекс.
Поскольку индекс реализуется механизмом хранения, не все механизмы поддерживают кластеризованные индексы.
В настоящее время поддерживаются только solidDB и InnoDB.
2. Индекс покрытия
Использование индекса
1) Индекс не будет содержать столбцов с нулевыми значениями
2) Попробуйте использовать короткие индексы, проиндексируйте список и, если возможно, укажите длину префикса. Короткий индекс может не только повысить скорость запросов, но также сэкономить дисковое пространство и операции ввода-вывода.
3) Операция типа Like: например, «% aaa%» не будет использовать индекс, но как «aaa%» может использовать индекс.
Ограничения на использование:
1) Поскольку индекс содержит только хэш-код и указатель записи, MySQL не может избежать чтения записей с помощью индекса. Но доступ к записям в памяти очень быстрый и не сильно повлияет на производительность.
2) Невозможно использовать хеш-индекс для сортировки.
3) Хеш-индекс не поддерживает частичное сопоставление ключей, потому что хеш-значение вычисляется по всему значению индекса.
4) Индекс хеширования поддерживает только сравнение равных значений, например использование =, IN () и . Если цена WHERE> 100 не ускоряет запрос.
Концепция индекса очень понятна в Интернете, личное понимание«Индекс - это структура данных для эффективного запроса». Например, мы используем словарь для поиска определенного человека. Мы не будем тупо пролистывать страницы. Сначала мы идем в каталог, чтобы искать. Найдя количество китайских иероглифов, мы перейдем прямо на указанную страницу. В этом процессе индекс можно сравнить с каталогом, а адрес данных, хранящихся на диске, можно сравнить с номером страницы китайских символов.
11.2.1. B-дерево
B-деревья могут работать в условиях на равенство и в проверках диапазонов с данными, которые можно отсортировать в некотором порядке. Точнее, планировщик запросов PostgreSQL может задействовать индекс-B-дерево, когда индексируемый столбец участвует в сравнении с одним из следующих операторов:
При обработке конструкций, представимых как сочетание этих операторов, например BETWEEN и IN , так же может выполняться поиск по индексу-B-дереву. Кроме того, такие индексы могут использоваться и в условиях IS NULL и IS NOT NULL по индексированным столбцам.
Также оптимизатор может использовать эти индексы в запросах с операторами сравнения по шаблону LIKE и ~ , если этот шаблон определяется константой и он привязан к началу строки — например, col LIKE 'foo%' или col ~ '^foo' , но не col LIKE '%bar' . Но если ваша база данных использует не локаль C, для поддержки индексирования запросов с шаблонами вам потребуется создать индекс со специальным классом операторов; см. Раздел 11.10. Индексы-B-деревья можно использовать и для ILIKE и ~* , но только если шаблон начинается не с алфавитных символов, то есть символов, не подверженных преобразованию регистра.
B-деревья могут также применяться для получения данных, отсортированных по порядку. Это не всегда быстрее простого сканирования и сортировки, но иногда бывает полезно.
11.2.6. BRIN
BRIN-индексы (сокращение от Block Range INdexes, Индексы зон блоков) хранят обобщённые сведения о значениях, находящихся в физически последовательно расположенных блоках таблицы. Поэтому такие индексы наиболее эффективны для столбцов, значения в которых хорошо коррелируют с физическим порядком столбцов таблицы. Подобно GiST, SP-GiST и GIN, индексы BRIN могут поддерживать определённые пользователем стратегии и в зависимости от них применяться с разными операторами. Для типов данных, имеющих линейный порядок сортировки, записям в индексе соответствуют минимальные и максимальные значения данных в столбце для каждой зоны блоков. Это позволяет поддерживать запросы со следующими операторами:
Классы операторов BRIN, включённые в стандартный дистрибутив, описаны в Таблице 68.1. За дополнительными сведениями обратитесь к Главе 68.
В одном из комментариев здесь была просьба рассказать подробнее об индексах, и так как, в рунете практически нет сводных данных о поддерживаемых индексах различных СУБД, в данном обзоре я рассмотрю, какие типы индексов поддерживаются в наиболее популярных СУБД
B-Tree
Семейство B-Tree индексов — это наиболее часто используемый тип индексов, организованных как сбалансированное дерево, упорядоченных ключей. Они поддерживаются практически всеми СУБД как реляционными, так нереляционными, и практически для всех типов данных.
Так как большинство, наверное, их хорошо знает(или могут прочесть о них например, здесь), то единственное, что, пожалуй, следует здесь отметить, это то, что данный тип индекса оптимален для множества с хорошим распределением значений и высокой мощностью(cardinality-количество уникальных значений).
Пространственные индексы
В данный момент все данные СУБД имеют пространственные типы данных и функции для работы с ними, для Oracle — это множество типов и функций в схеме MDSYS, для PostgreSQL — point, line, lseg, polygon, box, path, polygon, circle, в MySQL — geometry, point, linestring, polygon, multipoint, multilinestring, multipolygon, geometrycollection, MS SQL — Point, MultiPoint, LineString, MultiLineString, Polygon, MultiPolygon, GeometryCollection.
В схеме работы пространственных запросов обычно выделяют две стадии или две ступени фильтрации. СУБД, обладающие слабой пространственной поддержкой, отрабатывают только первую ступень (грубая фильтрация, MySQL). Как правило, на этой стадии используется приближенное, аппроксимированное представление объектов. Самый распространенный тип аппроксимации – минимальный ограничивающий прямоугольник (MBR – Minimum Bounding Rectangle) [100].
Для пространственных типов данных существуют особые методы индексирования на основе R-деревьев(R-Tree index) и сеток(Grid-based Spatial index).
Spatial grid
Spatial grid(пространственная сетка) index – это древовидная структура, подобная B-дереву, но используется для организации доступа к пространственным(Spatial) данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами(широтой и долготой). В этой структуре узлами дерева выступают ячейки пространства. Например, для двухмерного пространства: сначала вся родительская площадь будет разбита на сетку строго определенного разрешения, затем каждая ячейка сетки, в которой количество объектов превышает установленный максимум объектов в ячейке, будет разбита на подсетку следующего уровня. Этот процесс будет продолжаться до тех пор, пока не будет достигнут максимум вложенности (если установлен), или пока все не будет разделено до ячеек, не превышающих максимум объектов.
В случае трехмерного или многомерного пространства это будут прямоугольные параллелепипеды (кубоиды) или параллелотопы.
Quadtree
Quadtree – это подвид Grid-based Spatial index, в котором в родительской ячейке всегда 4 потомка и разрешение сетки варьируется в зависимости от характера или сложности данных.
R-Tree
R-Tree (Regions Tree) – это тоже древовидная структура данных подобная Spatial Grid, предложенная в 1984 году Антонином Гуттманом. Эта структура данных тоже разбивает пространство на множество иерархически вложенных ячеек, но которые, в отличие от Spatial Grid, не обязаны полностью покрывать родительскую ячейку и могут пересекаться.
Для расщепления переполненных вершин могут применяться различные алгоритмы, что порождает деление R-деревьев на подтипы: с квадратичной и линейной сложностью(Гуттман, конечно, описал и с экспоненциальной сложностью — Exhaustive Search, но он, естественно, нигде не используется).
Квадратичный подтип заключается в разбиении на два прямоугольника с минимальной площадью, покрывающие все объекты. Линейный – в разбиении по максимальной удаленности.
Hash-индексы были предложены Артуром Фуллером, и предполагают хранение не самих значений, а их хэшей, благодаря чему уменьшается размер(а, соответственно, и увеличивается скорость их обработки) индексов из больших полей. Таким образом, при запросах с использованием HASH-индексов, сравниваться будут не искомое со значения поля, а хэш от искомого значения с хэшами полей.
Из-за нелинейнойсти хэш-функций данный индекс нельзя сортировать по значению, что приводит к невозможности использования в сравнениях больше/меньше и «is null». Кроме того, так как хэши не уникальны, то для совпадающих хэшей применяются методы разрешения коллизий.
Bitmap
Bitmap index – метод битовых индексов заключается в создании отдельных битовых карт (последовательность 0 и 1) для каждого возможного значения столбца, где каждому биту соответствует строка с индексируемым значением, а его значение равное 1 означает, что запись, соответствующая позиции бита содержит индексируемое значение для данного столбца или свойства.
EmpID | Пол |
---|---|
1 | Мужской |
2 | Женский |
3 | Женский |
4 | Мужской |
5 | Женский |
Битовые карты
Значение | Начало | Конец | Битовая маска |
---|---|---|---|
Мужской | Адрес первой строки | Адрес последней строки | 10010 |
Женский | Адрес первой строки | Адрес последней строки | 01101 |
Основное преимущество битовых индексов в том, что на больших множествах с низкой мощностью и хорошей кластеризацией по их значениям индекс будет меньше чем B*-tree. (Подробнее стоит прочесть здесь или здесь)
Reverse index
Reverse index – это тоже B-tree индекс но с реверсированным ключом, используемый в основном для монотонно возрастающих значений(например, автоинкрементный идентификатор) в OLTP системах с целью снятия конкуренции за последний листовой блок индекса, т.к. благодаря переворачиванию значения две соседние записи индекса попадают в разные блоки индекса. Он не может использоваться для диапазонного поиска.
Пример:
Поле в таблице(bin) | Ключ reverse-индекса(bin) |
---|---|
00000001 | 10000000 |
… | … |
00001001 | 10010000 |
00001010 | 01010000 |
00001011 | 11010000 |
Inverted index
Инвертированный индекс – это полнотекстовый индекс, хранящий для каждого лексемы ключей отсортированный список адресов записей таблицы, которые содержат данный ключ.
1 | Мама мыла раму |
2 | Папа мыл раму |
3 | Папа мыл машину |
4 | Мама отполировала машину |
В упрощенном виде это будет выглядеть так:
Мама | 1,4 |
Мыла | 1 |
Раму | 1,2 |
Папа | 2,3 |
Отполировала | 4 |
Машину | 3,4 |
Partial index
Partial index — это индекс, построенный на части таблицы, удовлетворяющей определенному условию самого индекса. Данный индекс создан для уменьшения размера индекса.
Function-based index
Самим же гибким типом индексов являются функциональные индексы, то есть индексы, ключи которых хранят результат пользовательских функций. Функциональные индексы часто строятся для полей, значения которых проходят предварительную обработку перед сравнением в команде SQL. Например, при сравнении строковых данных без учета регистра символов часто используется функция UPPER. Создание функционального индекса с функцией UPPER улучшает эффективность таких сравнений.
Кроме того, функциональный индекс может помочь реализовать любой другой отсутствующий тип индексов данной СУБД(кроме, пожалуй, битового индекса, например, Hash для Oracle)
Сводная таблица типов индексов
MySQL | PostgreSQL | MS SQL | Oracle | |
B-Tree index | Есть | Есть | Есть | Есть |
Поддерживаемые пространственные индексы(Spatial indexes) | R-Tree с квадратичным разбиением | Rtree_GiST(используется линейное разбиение) | 4-х уровневый Grid-based spatial index (отдельные для географических и геодезических данных) | R-Tree c квадратичным разбиением; Quadtree |
Hash index | Только в таблицах типа Memory | Есть | Нет | Нет |
Bitmap index | Нет | Есть | Нет | Есть |
Reverse index | Нет | Нет | Нет | Есть |
Inverted index | Есть | Есть | Есть | Есть |
Partial index | Нет | Есть | Есть | Нет |
Function based index | Нет | Есть | Есть | Есть |
Стоит упомянуть, что в PostgreSQL GiST позволяет создать для любого собственного типа данных индекс основанный на R-Tree. Для этого нужно реализовать все 7 функций механизма R-Tree.
PS. Возможно я что-либо забыл упомянуть, пишите на личку или в комментарии — добавлю.
После прочтения этой статьи вы узнаете какие типы индексов есть в PostgreSQL. Какие есть способы построить индекс и в каких случаях использовать тот или иной тип индекса.
Самое главное, что нужно понять, так это то, что невозможно достичь высокой производительности без правильно подобранных индексов.
И так, подготовим таблицу для экспериментов:
Нашим тестовым запросом будет :
На моей машине такой запрос без индексов выполнялся 598 миллисекунд, а при построенном индексе по полю id уже 94 миллисекунды. Теперь понятно, что индексы — мощная штука. Но как их построить и как они устроены внутри мы пока не знаем? Давайте заполнять пробелы.
11.2.5. GIN
GIN-индексы представляют собой « инвертированные индексы » , в которых могут содержаться значения с несколькими ключами, например массивы. Инвертированный индекс содержит отдельный элемент для значения каждого компонента, и может эффективно работать в запросах, проверяющих присутствие определённых значений компонентов.
Подобно GiST и SP-GiST, индексы GIN могут поддерживать различные определённые пользователем стратегии и в зависимости от них могут применяться с разными операторами. Например, стандартный дистрибутив PostgreSQL включает класс операторов GIN для массивов, что позволяет применять индексы в запросах с операторами:
(Эти операторы описаны в Разделе 9.19.) Классы операторов GIN, включённые в стандартный дистрибутив, описаны в Таблице 67.1. В коллекции contrib и в отдельных проектах можно найти и много других классов операторов GIN. За дополнительными сведениями обратитесь к Главе 67.
11.2.2. Хеш
Хеш-индексы хранят 32-битный хеш-код, полученный из значения индексированного столбца, поэтому хеш-индексы работают только с простыми условиями равенства. Планировщик запросов может применить хеш-индекс, только если индексируемый столбец участвует в сравнении с оператором = . Создать такой индекс можно следующей командой:
Как построить индекс
Запрос на построение индекса к нашей тестовой таблице очень простой:
Круто, теперь мы умеем строить индексы по таблице, вот только есть пару но. Create index захватывает блокировку (про типы блокировок я напишу отдельную статью) на всю таблицу. Эта блокировка препятствует любым изменениям. Если у нас небольшая таблица, то ничего страшного, индекс построится достаточно быстро и мы ничего не заметим.
К примеру на моей машине для нашей тестовой таблицы индекс строился целых 9 секунд. А что делать, если таблица большая, а индекс построить нужно?
На помощь нам приходит create index concurrently . Данная операция не блокирует таблицу, но при этом и работает дольше чем create index . Все на том же примере у меня это действие заняло почти 13 секунд. Однако, PostgreSQL не дает гарантий, что create index concurrently выполнится успешно. В случае возникновения конфликтов при построении, то такой индекс просто будет помечен как недействительный и не будет участвовать в выполнении запросов.
Замечу еще один момент: параллельное построение индекса доступно только с версии PostgreSQL 11.
11.2.4. SP-GiST
Индексы SP-GiST, как и GiST, предоставляют инфраструктуру, поддерживающую различные типы поиска. SP-GiST позволяет организовывать на диске самые разные несбалансированные структуры данных, такие как деревья квадрантов, k-мерные и префиксные деревья. Например, стандартный дистрибутив PostgreSQL включает классы операторов SP-GiST для точек в двумерном пространстве, что позволяет применять индексы в запросах с операторами:
(Эти операторы описаны в Разделе 9.11.) Классы операторов SP-GiST, включённые в стандартный дистрибутив, описаны в Таблице 66.1. За дополнительными сведениями обратитесь к Главе 66.
Индексы SP-GiST, как и GiST, поддерживают поиск ближайших соседей. Для классов операторов SP-GiST, поддерживающих упорядочивание по расстоянию, соответствующий оператор указан в столбце « Операторы упорядочивания » в Таблице 66.1.
Внутреннее устройство индекса
Чтобы посмотреть, какие типы индексов доступны на вашей инсталяции PostgreSQL нужно выполнить вот такой запрос select * from pg_am . У меня в PostgreSQL версии 11.8 доступны следующие типы:
В данной статье я разберу только два, самый популярных, индекса: b-tree и hash. Другие типы индексов, такие как GIN, нуждаются в отдельном, более глубоком разборе.
B-tree
Данный тип индексов является типом по умолчанию в PostgreSQL и как показывает практика, в большинстве случаев b-tree будет достаточно.
В PostgreSQL используется b-tree Лемана-Яо. Что это за дерево такое? Дерево Лемана-Яо позволяет выполнять значительное количество операций чтения и записи над одним и тем же индексом. За более детальным описанием можете обратиться к научной статье Efficient Locking for Concurrent Operations on B-Trees.
B-tree хранит в себе данные в отсоритрованном виде, что дает нам возможность быстрого поиска нужного элемента (вспомните бинарный поиск). Еще одним немаловажным фактором является то, что b-tree в PostgreSQL можно читать как в прямом, так и в обратном порядке. Только вот что нам эта особенность дает?
К примеру такой запрос select min(id), max(id) from test есть ни что иное как простое чтение первого и последнего элемента в дереве. Это очень быстрая операция.
Мы знаем про индекс построенный на b-tree. Он выполняет свою задачу корректно и эффективно. Мы можем построить его параллельно, без блокировки таблицы. Лучше умы computer science трудились над оптимизацией b-tree. Тогда зачем нам другие типы индексов?
Помните, что я сказал про b-tree: эта структура данных хранит в себе элементы в отсортированном виде. А что делать, если какой то тип данных нельзя разумно отсоритровать? Или что делать, если нам ннужно отвеить на вопрос: содержит ли таблица такое значение или нет? Вот здесь нам помогут hash индексы.
Хеш-индексы можно представлять как табличку, где впервой колонке хеш от значения (где хеш это результат работы некоторой функции, которая преобразует переданное ей на вход значение в строку фиксированного размера), а вторая колонка самое значение.
Так же, как и у b-tree, хеш-индексы имеют ряд особенностей:
- хеш-индексы не подходят для сортировки, потому как хеш (по факту это строка) нельзя разумно отсортировать;
- поиск по частичному ключу не поддерживается
- доступны только операторы =, , IN()
оператор работает также, как и оператор =, только в случае, если оба операнда равны NULL, возврашает 1, а не NULL и 0, а не NULL, если один из операндов равен NULL.
индекс btree в mysql
MyISAM использует некластеризованный индекс, и адрес этой строки данных сохраняется в индексе. Когда адрес получается из индекса, выполняется поиск файла в файле данных на диске. Этот процесс называется линейным возвратом, что означает, что после получения адреса и последующего возврата к диску для поиска данных диск снова будет вводить-вывод.
InnoDB использует кластеризованный индекс. Все данные этой строки, хранящиеся в индексе первичного ключа, означают, что если вы найдете их в индексе, вам не нужно проходить через заднюю строку, но вы можете напрямую читать данные в строке. . Но это приведет к тому, что индексный файл станет слишком большим и потребует времени на запрос.
11.2.3. GiST
GiST-индексы представляют собой не просто разновидность индексов, а инфраструктуру, позволяющую реализовать много разных стратегий индексирования. Как следствие, GiST-индексы могут применяться с разными операторами, в зависимости от стратегии индексирования (класса операторов). Например, стандартный дистрибутив PostgreSQL включает классы операторов GiST для нескольких двумерных типов геометрических данных, что позволяет применять индексы в запросах с операторами:
(Эти операторы описаны в Разделе 9.11.) Классы операторов GiST, включённые в стандартный дистрибутив, описаны в Таблице 65.1. В коллекции contrib можно найти и другие классы операторов GiST, реализованные как отдельные проекты. За дополнительными сведениями обратитесь к Главе 65.
GiST-индексы также могут оптимизировать поиск « ближайшего соседа » , например такой:
который возвращает десять расположений, ближайших к заданной точке. Возможность такого применения индекса опять же зависит от класса используемого оператора. Операторы, которые можно использовать таким образом, перечислены в Таблице 65.1, в столбце « Операторы сортировки » .
Читайте также: