СПАСОИ (10) - Лекция №7 - Индексация данных: различия между версиями
ILobster (обсуждение | вклад) (Новая страница: «== Этап логического проектирования == === Методы индексации данных в реляционных БД === ==== B-…») |
ILobster (обсуждение | вклад) Нет описания правки |
||
Строка 10: | Строка 10: | ||
* инвертированный ключ - произвольный атрибут или набор атрибутов. Значения атрибутов в индексе могут повторяться. | * инвертированный ключ - произвольный атрибут или набор атрибутов. Значения атрибутов в индексе могут повторяться. | ||
Типы B- | Типы B-индексов: | ||
* обычные индексы - B-tree; | * обычные индексы - <code>B-tree</code>; | ||
* битовые индексы - Bit Mapped Index; | * битовые индексы - <code>Bit Mapped Index</code>; | ||
* реверсивные индексы - Reverse Key Index; | * реверсивные индексы - <code>Reverse Key Index</code>; | ||
* индекс-таблица - Table Index. | * индекс-таблица - <code>Table Index</code>. | ||
===== B-tree ===== | ===== B-tree ===== | ||
Строка 35: | Строка 35: | ||
Предположим, что индекс построен для некоторого атрибута ''q''. Записи блока третьего уровня показывают, что в таблицах хранятся следующие значения: | Предположим, что индекс построен для некоторого атрибута ''q''. Записи блока третьего уровня показывают, что в таблицах хранятся следующие значения: | ||
[[Файл:10semSPASOIl7pic2.png|center| | [[Файл:10semSPASOIl7pic2.png|center|200px]] | ||
<code>rowid</code> имеет сложную структуру: <code><font color="red">AABCDD</font>.<font color="blue">AAY</font>.<font color="green">AB7890</font>.<font color="orange">056</font></code> - 18 байт. | <code>rowid</code> имеет сложную структуру: <code><font color="red">AABCDD</font>.<font color="blue">AAY</font>.<font color="green">AB7890</font>.<font color="orange">056</font></code> - 18 байт. |
Версия от 10:59, 29 марта 2013
Этап логического проектирования
Методы индексации данных в реляционных БД
B-индексы
Строятся для следующих атрибутов:
- первичный ключ. Значение атрибутов в индексе уникально;
- альтернативный ключ. Значение атрибутов в индексе уникально;
- инвертированный ключ - произвольный атрибут или набор атрибутов. Значения атрибутов в индексе могут повторяться.
Типы B-индексов:
- обычные индексы -
B-tree
; - битовые индексы -
Bit Mapped Index
; - реверсивные индексы -
Reverse Key Index
; - индекс-таблица -
Table Index
.
B-tree
Каждая запись блока листового уровня имеет следующий вид:
<
значение атрибута(ов) - mean,
идентификатор записи таблицы БД - rowid
>
B - то есть бинарным - называется потому, что при переполнении блока индекса (они имеют ограниченный размер) он расщепляется на два примерно равных блока (появляется новый), а в блок предыдущего уровня добавляется указатель на новый.
Индексы строятся для конкретного атрибута(ов) конкретной таблицы.
Предположим, что индекс построен для некоторого атрибута q. Записи блока третьего уровня показывают, что в таблицах хранятся следующие значения:
rowid
имеет сложную структуру: AABCDD.AAY.AB7890.056
- 18 байт.
где:
AABCDD
- идентификатор объекта;AAY
- относительный идентификатор файла;AB7890
- блок внутри файла;056
- запись внутри блока.
Рассмотрим определение числа уровней в B-деревьеях.
Пусть:
V
- число записей в таблице БД;k
- максимальное число записей в одном блоке индекса;l
- число уровней индекса.
Тогда:
- $$\frac{V}{k}$$ - число блоков самого низшего, листового уровня;
- $$\frac{V}{k^2}$$ - число блоков $$l-1$$ уровня;
- ...
- $$\frac{V}{k^l} = 1$$ - число блоков первого уровня.
Тогда число уровней: $$$l = \log_k V$$$
Оценим объём индекса на листовом уровне. Будем предполагать, что все блоки на этом уровне заполнены.
Введём следующие обозначения:
V
- число записей в таблице БД;Lq
- длина индексируемого атрибута;Lr
- длина указателя на запись.
Получаем числов блоков $$$Q = V\cdot (Lq + Lr)$$$
Предположим, задана следующая таблица:
T1
... | q | S |
---|---|---|
... | 'A' | 'B' |
И выдаётся запрос с условием
SELECT * FROM T1
WHERE q = 'A' AND S = 'B'
Возможны следующие варианты:
1)
- система определяет идентификаторы записей по условию
q = 'A'
, используя индекс дляq
. - определяется список идентификаторов записей по условию
S = 'B'
, используя индекс дляS
. - полученные списки пересекаются и там ищется, обычно вложенными циклами. На это требуется время.
2)
- для поиска записи используется один из индексов: или
q
, илиS
; - читаются записи;
- результат определяется программно.
Преимущества B-деревьев:
- при обновлении записи в таблице блокируется только сама обновляемая запись;
- очень хорошо изучены, существуют эффективные алгоритмы реализации.
Недостатки B-деревьев:
- достаточно большой объём, занимаемый индексом;
- большое время выполнения операции со списком идентификаторов записи, удовлетворящих условию поиска.
Bit Mapped Index
Структура битового индекса такая же, как и у B-дерева. Отличаются они структурой записи блока листового уровня.
У битового индекса она такова:
<
значение атрибута(ов) - mean,
начальный идентификатор записи - start_rowid,
конечный идентификатор записи - end_rowid,
сегмент двоичной карты - bitmap_segment
>
Рассмотрим пример записи блока листового уровня индекса, построенного для некоторого атрибута q
:
Эта запись означает, что 14, 15, 18 и 20 записи имееют значение атрибута q
равное 'A'
.
Определим количество блоков на листовом уровне.
Введём следующие обозначения:
V
- число записей в таблице БД;Lq
- длина индексируемого атрибута;Lr
- длина указателя на запись;Lb
- длина сегмента bitmap.
Получаем числов блоков $$$Q = \frac{V}{8\cdot Lb}\cdot (Lq + 2\cdot Lr + Lb)$$$
Предположим, задана следующая таблица:
T1
... | q | S | ... |
---|---|---|---|
... | 'A' | 'B' | ... |
И выдаётся запрос с условием
SELECT * FROM T1
WHERE q = 'A' AND S = 'B'
Предположим, что запись блока листового уровня для индекса по атрибуту q
имеет вид 'A' 13 20 bitmap_segment1
, а для индекса по атрибуту S
имеет вид 'B' 13 20 bitmap_segment2
.
Тогда при выполнении запроса СУБД использует индексы по обоим атрибутам. Для работы с пересечением битовых массивов используется всего одна ассемблерная команда - это очень быстро.
Также скорость проявляется при инвертировании условия запроса: если надо искать не равенство, а неравенство атрибута, то достаточно только инвертировать сегмент, а в B-дереве надо просматривать опять всю таблицу.
Преимущества битового индекса:
- занимает меньший объём, чем B-дерево;
- поиск записей по условиям выполняется быстрее, чем в B-деревьях.
Недостаток битового индекса:
- при обнолении одной записи блокируются все записи, связанные с сегментом. Если модифицируется 14 запись, то блокируются записи с 13 по 20, например.