Index (Индексы)
Типы индексов:
Индексы в виде B-дерева (B-tree) – самые распространенные и используются по умолчанию
Кластерные индексы в виде B-дерева – определяются специально для кластера
Индексы хэш-кластера – определяются специально для хэш-кластера
Глобальные и локальные индексы – относятся к секционированным таблицам и индексам
Индексы с инвертированным ключом – полезны в среде Oracle Real Application Cluster
Битовые индексы – компактные, подходят для столбцов с небольшим набором значений
Индексы на базе функций – содержат заранее вычисленные значения функции/выражения
Индексы домена – зависят от приложения или картриджа
B*Tree
Структура индекса выглядит так:
Блоки самого нижнего уровня в индексе, которые называют листовыми вершинами (leaf blocks), содержат все проиндексированные ключи и идентификаторы строк (rowid на схеме), ссылающиеся на соответствующие строки. Промежуточные блоки над листовыми вершинами называют блоками ветвления (branch blocks). Они используются для переходов по структуре. Самый верхний блок называется корневым (root block), он относится к группе branch blocks.
Индексы состоят из одного или более уровней branch blocks и одного уровня leaf blocks.
Index height - высота индекса, кол-во уровней индекса
blevel - высота кол-ва уровней branch blocks
Пример
Создадим новую пустую таблицу и создадим индекс по ней. Индекс будет состоять из одного пустого блока (он будет одновременно и root и leaf блоком). Index height = 1, blevel = 0.
Добавим строки в таблицу. По мере того как новые строки будут вставлять в таблицу, новые индексные записи будут добавляться в блок индекса, до тех пор пока блок не заполнится.
Далее Oracle выделяет два новых индексных блока и переносит все записи из начального блока (root block) в эти два новых блока, и добавляет в root block указатели(RBA - Relative Block Address) на эти два новых блока (которые теперь являются листовыми) и наименьшее проиндексированное значение из каждого из этих двух листовых блоков. RBA1 - min(value) leaf_blk_1, RBA2 - min(value) leaf_blk_2. Таким образом Oracle с этой информацией из root блока может искать нужное значение в листовых блоках.
Теперь Index height = 2, blevel = 1.
Продолжаем вставлять строки в таблицу. Два leaf блока заполняются индексами, и когда они заполнятся, Oracle добавит ещё один листовой блок, содержимое старого заполненного блока, куда должен был бы попасть новый индекс распределяется между старым и новым листовыми блоками. Указатель на новый листовой блок помещается в root блок. Каждый раз когда листовой блок заполняется и разделяется на новый, в root записывается указатель, таким образом со временем заполнится и root блок.
Когда root блок полностью заполнится указателями, произойдёт его разделение на два branch блока, над которыми будет root блок с указателями на эти два блока. Теперь Index height = 3, blevel = 2. Как на картинке ниже:
По мере заполнения разделяются(split) листовые блоки, затем branch блоки и root блок. И так далее.
Интересно отметить, что листовые блоки фактически образут двухсвязный список. Как только найдено "начало" среди листовых вершин, т.е. первое значение, очень легко просматривать значения по порядку (это называют также просмотром диапазона по индексу, index range scan). Проходить по структуре индекса больше не нужно; мы просто переходим по листовым вершинам.
Одно из свойств В*-дерева состоит в том, что все листовые блоки должны быть на одном уровне, если точнее, разница по высоте между ветвями дерева не может быть больше 1.
Уровень листовых блоков называют также высотой дерева.
Все вершины выше листовых могут указывать только на содержащие более детальную информацию вершины следующего уровня, а листовые вершины указывают на конкретные идентификаторы строк или диапазоны идентификаторов строк. Большинство индексов на основе В*-дерева будут иметь высоту 2 или 3, даже для миллионов записей. Это означает, что для поиска ключа в индексе потребуется 2 или 3 чтения, что неплохо.
Еще одно свойство - автоматическая балансировка листовых вершин: они почти всегда располагаются на одном уровне. Есть причины, по которым индекс может оказаться не идеально сбалансированным при изменении и удалении записей. Сервер Oracle будет пытаться заполнять блоки индекса не более чем на три четверти, но и это свойство может временно нарушаться при выполнении операторов DELETE и UPDATE.
Когда следует использовать B*Tree индексы:
- Как средство доступа к строкам в таблице. Индекс читается, чтобы добраться до строки в таблице. Так имеет смысл обращаться к очень небольшой части строк таблицы.
- Как средство ответа на запрос. Индекс содержит достаточно информации, чтобы дать полный ответ на запрос — к таблице вообще не придется обращаться. Индекс будет использоваться как уменьшенная версия таблицы.
Bitmap
Индексы на основе битовых карт — это структуры, в которых хранятся указатели на множество строк, соответствующих одному значению ключа индекса, тогда как в структуре В*-дерева количество ключей индекса обычно примерно соответствует количеству строк. В индексе на основе битовых карт записей очень мало, и каждая из них указывает на множество строк. В индексе на основе В*-дерева обычно имеется однозначное соответствие — запись индекса ссылается на одну строку.
Когда следует использовать Bitmap индексы:
Для данных с небольшим количеством уникальных значений. Это данные, для которых при делении количества уникальных значений в строках на общее количество строк получается небольшое число (близкое к нулю).
Function Based
Индексы по функциям позволяют индексировать вычисляемые столбцы и эффективно
использовать их в запросах.
Индексы можно создавать не только по системным оракловым ф-циям, но и по своим написанным ф-циям
Application domain indexes(прикладные индексы)
Прикладные индексы позволяют создавать новые, еще не существующие в базе данных, типы индексов.
Например, если создается приложение, анализирующее хранящиеся в базе данных изображения и выдающее информацию об этих изображениях - скажем, используемые цвета — можно создать специальный индекс по изображениям. При добавлении изображений в базу данных будет вызываться код для извлечения информации о цветах, которая будет сохраняться отдельно (там, где сочтет нужным разработчик). При выполнении запросов, требующих вернуть "изображения в синих тонах", сервер Oracle при необходимости потребует от прикладного индекса вернуть ответ.
Избирательность индекса
Избирательность представляет собой отношение количества выбранных строк к общему количеству строк. Если это отношение мало, значит, индекс обладает высокой избирательностью. Он позволяет отбросить большую часть строк и значительно уменьшает размер результирующего набора. Подобный индекс является эффективным. Индекс, не обладающий избирательностью, не является эффективным.
Наилучшей избирательностью обладает уникальный индекс. При использовании уникального индекса возвращается только одна строка, что делает этот индекс наиболее эффективным для применения в запросах, которые должны возвращать только одну строку. Например, индексирование по столбцу, содержащему уникальный код, позволяет быстро найти требуемую строку.
Типы индексов:
Индексы в виде B-дерева (B-tree) – самые распространенные и используются по умолчанию
Кластерные индексы в виде B-дерева – определяются специально для кластера
Индексы хэш-кластера – определяются специально для хэш-кластера
Глобальные и локальные индексы – относятся к секционированным таблицам и индексам
Индексы с инвертированным ключом – полезны в среде Oracle Real Application Cluster
Битовые индексы – компактные, подходят для столбцов с небольшим набором значений
Индексы на базе функций – содержат заранее вычисленные значения функции/выражения
Индексы домена – зависят от приложения или картриджа
B*Tree
Структура индекса выглядит так:
Индексы состоят из одного или более уровней branch blocks и одного уровня leaf blocks.
Index height - высота индекса, кол-во уровней индекса
blevel - высота кол-ва уровней branch blocks
Пример
Создадим новую пустую таблицу и создадим индекс по ней. Индекс будет состоять из одного пустого блока (он будет одновременно и root и leaf блоком). Index height = 1, blevel = 0.
Добавим строки в таблицу. По мере того как новые строки будут вставлять в таблицу, новые индексные записи будут добавляться в блок индекса, до тех пор пока блок не заполнится.
Далее Oracle выделяет два новых индексных блока и переносит все записи из начального блока (root block) в эти два новых блока, и добавляет в root block указатели(RBA - Relative Block Address) на эти два новых блока (которые теперь являются листовыми) и наименьшее проиндексированное значение из каждого из этих двух листовых блоков. RBA1 - min(value) leaf_blk_1, RBA2 - min(value) leaf_blk_2. Таким образом Oracle с этой информацией из root блока может искать нужное значение в листовых блоках.
Теперь Index height = 2, blevel = 1.
Продолжаем вставлять строки в таблицу. Два leaf блока заполняются индексами, и когда они заполнятся, Oracle добавит ещё один листовой блок, содержимое старого заполненного блока, куда должен был бы попасть новый индекс распределяется между старым и новым листовыми блоками. Указатель на новый листовой блок помещается в root блок. Каждый раз когда листовой блок заполняется и разделяется на новый, в root записывается указатель, таким образом со временем заполнится и root блок.
Когда root блок полностью заполнится указателями, произойдёт его разделение на два branch блока, над которыми будет root блок с указателями на эти два блока. Теперь Index height = 3, blevel = 2. Как на картинке ниже:
Интересно отметить, что листовые блоки фактически образут двухсвязный список. Как только найдено "начало" среди листовых вершин, т.е. первое значение, очень легко просматривать значения по порядку (это называют также просмотром диапазона по индексу, index range scan). Проходить по структуре индекса больше не нужно; мы просто переходим по листовым вершинам.
Одно из свойств В*-дерева состоит в том, что все листовые блоки должны быть на одном уровне, если точнее, разница по высоте между ветвями дерева не может быть больше 1.
Уровень листовых блоков называют также высотой дерева.
Все вершины выше листовых могут указывать только на содержащие более детальную информацию вершины следующего уровня, а листовые вершины указывают на конкретные идентификаторы строк или диапазоны идентификаторов строк. Большинство индексов на основе В*-дерева будут иметь высоту 2 или 3, даже для миллионов записей. Это означает, что для поиска ключа в индексе потребуется 2 или 3 чтения, что неплохо.
Еще одно свойство - автоматическая балансировка листовых вершин: они почти всегда располагаются на одном уровне. Есть причины, по которым индекс может оказаться не идеально сбалансированным при изменении и удалении записей. Сервер Oracle будет пытаться заполнять блоки индекса не более чем на три четверти, но и это свойство может временно нарушаться при выполнении операторов DELETE и UPDATE.
-- создать индекс
create index t_idx on t(owner,object_type,object_name);
create index t_idx on t(owner,object_type,object_name);
Когда следует использовать B*Tree индексы:
- Как средство доступа к строкам в таблице. Индекс читается, чтобы добраться до строки в таблице. Так имеет смысл обращаться к очень небольшой части строк таблицы.
- Как средство ответа на запрос. Индекс содержит достаточно информации, чтобы дать полный ответ на запрос — к таблице вообще не придется обращаться. Индекс будет использоваться как уменьшенная версия таблицы.
Bitmap
Индексы на основе битовых карт — это структуры, в которых хранятся указатели на множество строк, соответствующих одному значению ключа индекса, тогда как в структуре В*-дерева количество ключей индекса обычно примерно соответствует количеству строк. В индексе на основе битовых карт записей очень мало, и каждая из них указывает на множество строк. В индексе на основе В*-дерева обычно имеется однозначное соответствие — запись индекса ссылается на одну строку.
Когда следует использовать Bitmap индексы:
Для данных с небольшим количеством уникальных значений. Это данные, для которых при делении количества уникальных значений в строках на общее количество строк получается небольшое число (близкое к нулю).
-- создать bitmap индекс
create bitmap index empno_bmx on t(empno);
create bitmap index empno_bmx on t(empno);
Function Based
Индексы по функциям позволяют индексировать вычисляемые столбцы и эффективно
использовать их в запросах.
Индексы можно создавать не только по системным оракловым ф-циям, но и по своим написанным ф-циям
-- создать индекс по ф-ции
create index emp_upper_idx on emp (upper(ename));
create index emp_upper_idx on emp (upper(ename));
Application domain indexes(прикладные индексы)
Прикладные индексы позволяют создавать новые, еще не существующие в базе данных, типы индексов.
Например, если создается приложение, анализирующее хранящиеся в базе данных изображения и выдающее информацию об этих изображениях - скажем, используемые цвета — можно создать специальный индекс по изображениям. При добавлении изображений в базу данных будет вызываться код для извлечения информации о цветах, которая будет сохраняться отдельно (там, где сочтет нужным разработчик). При выполнении запросов, требующих вернуть "изображения в синих тонах", сервер Oracle при необходимости потребует от прикладного индекса вернуть ответ.
Избирательность индекса
Избирательность представляет собой отношение количества выбранных строк к общему количеству строк. Если это отношение мало, значит, индекс обладает высокой избирательностью. Он позволяет отбросить большую часть строк и значительно уменьшает размер результирующего набора. Подобный индекс является эффективным. Индекс, не обладающий избирательностью, не является эффективным.
Наилучшей избирательностью обладает уникальный индекс. При использовании уникального индекса возвращается только одна строка, что делает этот индекс наиболее эффективным для применения в запросах, которые должны возвращать только одну строку. Например, индексирование по столбцу, содержащему уникальный код, позволяет быстро найти требуемую строку.
