В одном из комментариев здесь была просьба рассказать подробнее об индексах, и так как, в рунете практически нет сводных данных о поддерживаемых индексах различных СУБД, в данном обзоре я рассмотрю, какие типы индексов поддерживаются в наиболее популярных СУБД

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) .
Для пространственных типов данных существуют особые методы индексирования на основе 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-индексы были предложены Артуром Фуллером, и предполагают хранение не самих значений, а их хэшей, благодаря чему уменьшается размер(а, соответственно, и увеличивается скорость их обработки) индексов из больших полей. Таким образом, при запросах с использованием HASH-индексов, сравниваться будут не искомое со значения поля, а хэш от искомого значения с хэшами полей.
Из-за нелинейнойсти хэш-функций данный индекс нельзя сортировать по значению, что приводит к невозможности использования в сравнениях больше/меньше и «is null». Кроме того, так как хэши не уникальны, то для совпадающих хэшей применяются методы разрешения коллизий.

Bitmap

Bitmap index – метод битовых индексов заключается в создании отдельных битовых карт (последовательность 0 и 1) для каждого возможного значения столбца, где каждому биту соответствует строка с индексируемым значением, а его значение равное 1 означает, что запись, соответствующая позиции бита содержит индексируемое значение для данного столбца или свойства.

Reverse index

Reverse index – это тоже B-tree индекс но с реверсированным ключом, используемый в основном для монотонно возрастающих значений(например, автоинкрементный идентификатор) в OLTP системах с целью снятия конкуренции за последний листовой блок индекса, т.к. благодаря переворачиванию значения две соседние записи индекса попадают в разные блоки индекса. Он не может использоваться для диапазонного поиска.
Пример:
Как видите, значение в индексе изменяется намного больше, чем само значение в таблице, и поэтому в структуре b-tree, они попадут в разные блоки.

Inverted index

Инвертированный индекс – это полнотекстовый индекс, хранящий для каждого лексемы ключей отсортированный список адресов записей таблицы, которые содержат данный ключ.

В упрощенном виде это будет выглядеть так:

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.
Дополнительно можно прочитать здесь:

Платформа Oracle позволяет с помощью инструкции CREATE INDEX создавать индексы по таблицам, секционированным таблицам, кластерам и индекс-таблицам (index-organized tables), а также скалярным атрибутам объектов объектных таблиц (typed table) и столбцам вложенных таблиц. Платформа Oracle также позволяет использовать несколько типов индексов, в том числе обычные иерархические (B-tree) индексы, индексы на основе битовых карт (BITMAP) (используются для столбцов, в которых каждое значение повторяется 100 и более раз), секционированные индексы, индексы, связанные с функцией (основанные на выражении, а не на значении в столбце), и предметные индексы (domain index).

Имена индексов Oracle должны быть уникальны в пределах схемы, а не только в пределах таблицы, с которой они связаны.

Платформа Oracle также поддерживает инструкцию ALTER INDEX. Она используется для изменения или перестройки существующего индекса без его удаления и повторного создания.

Синтаксис инструкции CREATE INDEX в Oracle следующий.

CREATE INDEX имя_индекса {ON

{имя_таблицы ({столбец | выражение} [, …]) [{INDEXTYPE IS

тип_индекса | NOPARALLEL] | CLUSTER имя_кластера |

FROM имя_таблицы WHERE условие } [{LOCAL секционирование |

GLOBAL секционирование}] [параметры_физических_атрибутов] [{LOGGING | NOLOGGING}]

[{TABLESPACE имя_табличного_пространства DEFAULT}] [{COMPRESS int | NOCOMPRESS}] [{NOSORT |

SORT}] [{PARALLEL | NOPARALLEL}]

Синтаксис инструкции ALTER INDEX следующий.

ALTER INDEX имя_индекса

{{ENABLE | DISABLE} | UNUSABLE | RENAME TO новое_имя_индекса COALESCE] MONITORING USAGE | UPDATE BLOCK REFERENCES |

PARAMETERS ("параметры_00С1") | параметры_изменения_секционирования_индекса | параметры_перестройки |

)] ] [{PARALLEL | NOPARALLEL}] [{LOGGING | NOLOGGING}]

[параметры_физических_атрибутов]}

Где предложения, не входящие в стандарт ANSI, таковы:

Вместо индексирования каждой строки для каждого значения индекса создается битовая карта. Битовые карты лучше всего использовать для таблиц с небольшим числом конкурентных запросов, например таблиц с высокой интенсивностью чтения. Индексы на основе битовых карт несовместимы с индексами с глобальным секционированием, предложением INDEXTYPE и индекс-таблицами (index-organized table) без связи с таблицей соответствия (mapped table).

ASC | DESC

Определяет расположение значений индекса в восходящем (ASQ или нисходящем (DESQ порядке. Если предложение опущено, по умолчанию принимается ASC. Однако помните, что Oracle считает индексы с предложением DESC индексами, основанными на функции, так что между индексами с предложением ASC и индексами с предложением DESC есть некоторые функциональные различия. Предложения ASC и DESC нельзя использовать совместно с предложением INDEXTYPE. Предложение DESC игнорируется при использовании индексов на основе битовых карг (BITMAP).

INDEXTYPE IS munjuidenca

Создается индекс определенного пользователем типа тип_индекса. Предметные индексы (domain index) требуют, чтобы пользовательский тип уже существовал (обращайтесь к разделу «Инструкция CREATE/ALTER TYPE»). Если для пользовательского типа требуются аргументы, их можно передать с помощью предложения PARAMETERS. При желании можно параллелизировать создание типизированного индекса с помощью предложения PARALLEL, которое подробно рассматривается ниже.

CLUSTER имя_кластера

Объявляется кластерный индекс с указанием существующего имени_клаетера. В Oracle кластерный индекс физически совмещает две таблицы, которые часто опрашиваются по одинаковым столбцам, обычно столбцам первичного и внешнего ключей. (Кластеры создаются специфической для Oracle командой CREATE CLUSTER.) Таблицы и столбцы в кластерном индексе не нужно объявлять, поскольку таблицы и индексированные столбцы уже объявлялись в ранее выполненной команде CREATE CLUSTER.

Таблицы могут иметь большое количество строк. А, так как строки не упорядочены, то поиск по указанному значению может потребовать значительного времени. Использование индексов позволяет ускорить процесс чтения требуемых записей. INDEX - это упорядоченный список определенных столбцов или групп столбцов в таблице. Когда создается индекс по одному или нескольким полям, то сервер БД формирует соответствующий упорядоченный список. Таблица, конечно же, должна уже быть создана и должна содержать имена индексируемых столбцов.

Синтаксис CREATE INDEX

CREATE INDEX ON table_name ( [,]...);

Добавление индекса снижает производительность запросов, связанных с добавлением, изменением или удалением данных, поскольку каждый раз при выполнении транзакции данные индекса также обновляются, что требует выполнения от сервера дополнительной работы. Однако выполение запросов SELECT по индексируемым полям существенно перевешивают эти недостатки. Не следует создавать индексы по каждому столбцу таблицы, не определив, какие запросы будут выполняться.

Уникальный индекс, UNIQUE INDEX

Индекс может быть уникальным unique index , что не позволяет иметь в таблице дублированных записей с одинаковыми значениями индексируемых полей.

ПРИМЕЧАНИЕ: при создании уникального индекса транзакция будет отклонена, если уже имеются идентичные значения в записях таблицы по индексируемым полям. Для уникального индекса таблицы с несколькими полями комбинация значений должна быть единственной, но каждое из значений поля может и не быть уникальным.

Отличие PRIMARY KEY и UNIQUE INDEX

Ограничения "primary key" и unique index обеспечивают уникальность значений полей таблицы, в которой они определены. По умолчанию primary key создает кластерный индекс на столбце, а "unique index" - некластерный. Другим отличием является то, что "primary key" не может иметь нулевых записей, т.е. поле NOT NULL, в то время как "unique index" допускает только одну нулевую запись (NULL). Таблица может иметь только один первичный ключ, но несколько "unique index".

Удаление DROP INDEX

Удаление индекса не воздействует на содержание полей. Синтаксис оператора удаления индекса drop index:

DROP INDEX ;

ALTER INDEX

В разных СУБД имеются существенные различия по использованию оператора alter index . Так например MySQL не поддерживает данный оператор, в Interbase можно использовать данный оператор для отключения и повторного включения индекса, в результате чего будет выполнена переиндексация данных.

В СУБД PostgresSQL индекс можно переименовать с использованием оператора alter index . Синтаксис переменования индекса:

Переименование индекса в СУБД PostgresSQL ALTER INDEX index_name RENAME TO index_name_new;

ALTER INDEX в Oracle

Платформа Oracle также поддерживает инструкцию alter index . Данный оператор используется для изменения или перестройки существующего индекса без его удаления и повторного создания.

Синтаксис оператора для переименования индекса в Oracle имеет следующий вид:

Переименование индекса в СУБД Oracle ALTER INDEX index_name RENAME TO index_name_new;

Для переиндексации данных необходимо использовать следующий синтаксис оператора alter index :

ALTER INDEX index_name [ coalesce | [ rebuild | rebuild online ] ];

COALESCE

При использовании coalesce таблица не блокируется и переиндексация выполняется online. При этом индекс размещается в пределах существующей индексной структуры - соединяет блоки листа в пределах имеющихся ветвей дерева. Индексные листовые блоки быстро освобождаются для использования и не требуется много дискового пространства.

Однако coalesce генерирует много записей в журналах повторного выполнения (redo). При этом данный операнд может вызвать ошибку ORA-01555 (coalesce определяет "работу" Oracle с листовыми блоками, определенных количеством малых транзакций. А много малых транзакций, выполненных одной сессией, могут вызвать у другой сессии, выполняющей продолжительную транзакцию, эту ошибку). Кроме этого coalesce не опускает HWM индекс, т.е. место на диске не освобождает и не может переместить индекс в другое табличное пространство.

REBUILD

Использование rebuild позволяет быстро перемещать индекс в другое табличное пространство. Кроме этого "rebuild" создает новое дерево и уменьшает его высоту при необходимости. А также дает возможность быстро изменять storage и tablespace параметры, без необходимости удалять индекс. Может быть использован для уменьшения расходования ресурсов - передвигается отметка HWM.

Однако rebuild связан с более высокими издержками - требуется больше дискового пространства, чтобы разместить старый и новый индекс в соответствующем табличном пространстве. Кроме этого rebuild может вызвать ошибку ORA-01410: Invalid ROWID.

Rebuild "offline" может использовать существующий индекс для создания новой версии индекса, но блокирует таблицу во время выполнения.

Rebuild "online" не блокирует таблицу во время непосредственной перестройки индекса, и индекс доступен практически все время при перестроении, кроме времени переключения. Однако при этом блокируется таблица в начале и в конце перестроения. При этом старый индекс не используется для перестроения индекса, но с ним работают пользователи. Все изменения тем временем вносятся в журнальную таблицу, затем уже будут перенесены в новый индекс. Может потребоваться большая сортировка.

Таким образом, оператор coalesce особенно эффективен, когда процент проблематичного пространства к общему индексному пространству невелик (20% листовых блоков) и фрагментирован индекс несущественно. rebuild особенно эффективен, когда процент проблематичного пространства к общему индексному пространству велик и средняя степень фрагментации в пределах индексного блока листа сравнительно высокая.

Oracle обеспечивает выполнение ограничения целостности UNIQUE или PRIMARY KEY для таблицы, создавая уникальный индекс для уникального или первичного ключа. Этот индекс создается автоматически, когда включается ограничение целостности. Когда выполняется CREATE TABLE или ALTER TABLE, для создания индекса не надо предпринимать никаких действий, но при желании можно указать предложение USING INDEX, чтобы контролировать его создание.

Чтобы включить ограничение целостности UNIQUE или PRIMARY KEY, создавая таким образом связанный с ним индекс, владелец таблицы должен иметь квоту табличного пространства, где будет храниться этот индекс, или системную привилегию UNLIMITED TABLESPACE. Индекс связанный с ограничением целостности всегда получает имя этого ограничения, если вы не укажете иное.

Параметры хранения для индексов связанных с ограничением целостности UNIQUE или PRIMARY KEY, можно устанавливать с помощью предложения USING INDEX.

Следующий пример CREATE TABLE включает ограничение целостности PRIMARY KEY и задает параметры хранения связанного с ним индекса:

CREATE TABLE ALL_ORACLE_USERS ( ID NUMBER (5 ) PRIMARY KEY . . . LOCKED INTEGER ) ENABLE PRIMARY KEY USING INDEX TABLESPACE ALL_ORACLE_IDX_TBS PCTFREE 0 ;

Если требуется более явное управление индексами, связанными с ограничением целостности UNIQUE или PRIMARY KEY, то Oracle позволяет:

• Указывать существующий индекс, который Oracle должен использовать для обеспечения выполнения ограничения целостности.
• Указывать оператор создания индекса, который Oracle должен использовать, чтобы создать индекс и обеспечить выполнение ограничения целостности.

Эти возможности задаются с помощью предложения USING INDEX. Это продемонстрировано в следующих примерах:

CREATE TABLE TEST ( COL1 INT PRIMARY KEY USING INDEX (CREATE INDEX TEST_IDX ON TEST (COL1 ) ) ) ; CREATE TABLE TEST ( COL1 INT , COL2 INT , CONSTRAINT TESTU1 UNIQUE (COL1 , COL2 ) USING INDEX (CREATE UNIQUE INDEX TEST_IDX ON TEST (COL1 , COL2 ) ) , CONSTRAINT TESTU2 UNIQUE (COL2 , COL1 ) USING INDEX TEST_IDX) ; CREATE TABLE TEST ( COL1 INT , COL2 INT ) ; CREATE INDEX TEST_IDX ON TEST (COL1 , COL2 ) ; ALTER TABLE TEST ADD CONSTRAINT TEST_CON PRIMARY KEY (COL1 ) USING INDEX TEST_IDX;

Если один и тот же оператор создает индекс с одним ограничением целостности и использует этот индекс для другого ограничения целостности, система пытается изменить порядок предложений, чтобы создать индекс, прежде чем использовать его повторно.

This Oracle tutorial explains how to create, rename and drop indexes in Oracle with syntax and examples.

What is an Index in Oracle?

An index is a performance-tuning method of allowing faster retrieval of records. An index creates an entry for each value that appears in the indexed columns. By default, Oracle creates B-tree indexes.

Create an Index

Syntax

The syntax for creating an index in Oracle/PLSQL is:

CREATE INDEX index_name ON table_name (column1, column2, ... column_n) [ COMPUTE STATISTICS ]; UNIQUE It indicates that the combination of values in the indexed columns must be unique. index_name The name to assign to the index. table_name The name of the table in which to create the index. column1, column2, ... column_n The columns to use in the index. COMPUTE STATISTICS It tells Oracle to collect statistics during the creation of the index. The statistics are then used by the optimizer to choose a "plan of execution" when SQL statements are executed.

Example

Let"s look at an example of how to create an index in Oracle/PLSQL.

CREATE INDEX supplier_idx ON supplier (supplier_name);

In this example, we"ve created an index on the supplier table called supplier_idx. It consists of only one field - the supplier_name field.

We could also create an index with more than one field as in the example below:

CREATE INDEX supplier_idx ON supplier (supplier_name, city);

We could also choose to collect statistics upon creation of the index as follows:

CREATE INDEX supplier_idx ON supplier (supplier_name, city) COMPUTE STATISTICS;

Create a Function-Based Index

In Oracle, you are not restricted to creating indexes on only columns. You can create function-based indexes.

Syntax

The syntax for creating a function-based index in Oracle/PLSQL is:

CREATE INDEX index_name ON table_name (function1, function2, ... function_n) [ COMPUTE STATISTICS ]; UNIQUE It indicates that the combination of values in the indexed columns must be unique. index_name The name to assign to the index. table_name The name of the table in which to create the index. function1, function2, ... function_n The functions to use in the index. COMPUTE STATISTICS It tells Oracle to collect statistics during the creation of the index. The statistics are then used by the optimizer to choose a "plan of execution" when SQL statements are executed.

Example

Let"s look at an example of how to create a function-based index in Oracle/PLSQL.

CREATE INDEX supplier_idx ON supplier (UPPER(supplier_name));

In this example, we"ve created an index based on the uppercase evaluation of the supplier_name field.

However, to be sure that the Oracle optimizer uses this index when executing your SQL statements, be sure that UPPER(supplier_name) does not evaluate to a NULL value. To ensure this, add UPPER(supplier_name) IS NOT NULL to your WHERE clause as follows:

SELECT supplier_id, supplier_name, UPPER(supplier_name) FROM supplier WHERE UPPER(supplier_name) IS NOT NULL ORDER BY UPPER(supplier_name);

Rename an Index

Syntax

The syntax for renaming an index in Oracle/PLSQL is:

ALTER INDEX index_name RENAME TO new_index_name; index_name The name of the index that you wish to rename. new_index_name The new name to assign to the index.

Example

Let"s look at an example of how to rename an index in Oracle/PLSQL.

ALTER INDEX supplier_idx RENAME TO supplier_index_name;

In this example, we"re renaming the index called supplier_idx to supplier_index_name .

Collect Statistics on an Index

If you forgot to collect statistics on the index when you first created it or you want to update the statistics, you can always use the ALTER INDEX command to collect statistics at a later date.

Syntax

The syntax for collecting statistics on an index in Oracle/PLSQL is:

ALTER INDEX index_name REBUILD COMPUTE STATISTICS; index_name The index in which to collect statistics.

Example

Let"s look at an example of how to collect statistics for an index in Oracle/PLSQL.

ALTER INDEX supplier_idx REBUILD COMPUTE STATISTICS;

In this example, we"re collecting statistics for the index called supplier_idx.

Drop an Index

Syntax

The syntax for dropping an index in Oracle/PLSQL is:

DROP INDEX index_name; index_name The name of the index to drop.

Example

Let"s look at an example of how to drop an index in Oracle/PLSQL.

DROP INDEX supplier_idx;

In this example, we"re dropping an index called supplier_idx.