Показать сообщение отдельно
  #22  
Старый 24.09.2009, 13:22
Marley Marley вне форума
Senior Member
 
Регистрация: 19.09.2009
Сообщений: 7,211
По умолчанию Битовый индекс



Битовый индекс

Битовые индексы оказываются более выигрышными по сравнению с индексами в виде В-дерева в следующих ситуациях:

Таблица очень велика (содержит миллионы строк), и ключевые столбцы имеют низкую кардинальность - т.е. в столбце очень мало отличающихся значений. Например, в таблице паспортных данных для столбцов, содержащих сведения о поле и семейном положении, битовые индексы предпочтительнее индексов в виде В-дерева.
В запросах часто используется комбинация нескольких условий WHERE, включающих операцию типа OR.
Ключевые столбцы открыты только для чтения или редко обновляются.


Структура битового индекса

Битовый индекс также организован в виде В-дерева, но в листовом блоке индекса для каждого ключевого значения содержится не список значений ROWID, а битовая матрица. Каждый бит в этой матрице соответствует возможному значению ROWID, и если он установлен (т.е. его значение 1), то это означает, что строка с соответствующим ROWID содержит ключевое значение.


Как показано на слайде, в листовом блоке индекса содержится следующее:

заголовок элемента индекса, в который включена информация о числе столбцов и блокировках;
ключевые значения, состоящие из пар "длина-значение" для каждого ключевого столбца (в примере, показанном на слайде, ключ состоит только из одного столбца, и первый элемент имеет ключевое значение "Blue");
начальный ROW ID, который в данном примере содержит файл номер 3, блок номер 10 и строку номер 0;
конечный ROW ID, который в данном примере содержит файл номер 3, блок номер 12 и строку номер 8;
битовая матрица, состоящая из строки битов (1 означает, что соответствующая строка содержит ключевое значение, а 0 - что ключевое значение в строке отсутствует; для хранения битовых матриц сервер Oracle использует запатентованную методику сжатия).


Начальный ROWID - это ROWID первой строки, на которую указывает битовая матрица. Таким образом, первый бит этой матрицы соответствует данному ROWID, второй бит соответствует следующей строке в блоке, и конечный ROWID указывает на последнюю строку таблицы, входящую в битовую матрицу. Битовые индексы используют ограниченные ROWID.


Использование битового индекса

В-дерево используется для поиска листовых блоков, содержащих битовые матрицы для конкретного значения ключа. Начальный ROWID и битовые матрицы используются для поиска строк, содержащих это ключевое значение.

Когда в ключевой столбец таблицы вносятся изменения, битовые матрицы должны модифицироваться. Это приводит к блокировке соответствующих битовых матриц. Поскольку блокировки накладываются на всю битовую матрицу, строки, охваченные этой матрицей, не могут быть обновлены никакими другими транзакциями до тех пор, пока не завершится первая транзакция.
__________________
Телеграм чат
Ответить с цитированием