Файл: 6. Способы размещения данных и доступа к данным в рбд оглавление Способы размещения данных и доступа к данным в рбд.pdf

6. Способы размещения данных и доступа к данным в РБД Оглавление
6.
Способы размещения данных и доступа к данным в РБД ......................................... 1 Способы доступа к данным ................................................................................................ 1 Индексирование данных ..................................................................................................... 2 Хеширование ......................................................................................................................... 8 При создании новой записи во многих случаях существенно размещение этой записи в памяти, т.к. это оказывает огромное влияние на время выборки. Простейшая стратегия размещения данных заключается в том, что новая запись размещается на первом свободном участке (если ведется учёт свободного пространства) или вслед за последней из ранее размещённых записей. Среди более сложных методов размещения данных отметим хеширование и кластеризацию. Хеширование заключается в том, что специально подобранная хеш- функция преобразует значение ключа записи в адрес блока (страницы) памяти, в котором эта запись будет размещаться. Под ключом записи здесь подразумевается поле или набор полей, позволяющие классифицировать запись. Например, для таблицы СОТРУДНИКИ в качестве ключа записи может выступать поле Номер паспорта или набор полей (Фамилия, Имя, Дата рождения. Кластеризация – это способ хранения водной области памяти таблиц, связанных внешними ключами (одна родительская таблица, одна или несколько подчинённых таблиц. Для размещения записей используется значение внешнего ключа таким образом, чтобы все данные, имеющие одинаковое значение внешнего ключа, размещались водном блоке данных. Например, для таблиц СОТРУДНИКИ, ДЕТИ СОТРУДНИКОВ, ТРУДОВАЯ КНИЖКА, ОТПУСКА в качестве внешнего ключа подчинённых таблиц выступает первичный ключ Идентификатор сотрудника таблицы СОТРУДНИКИ, и тогда при кластеризации все данные о каждом сотруднике будут храниться водном блоке данных.
6.1. Способы доступа к данным Рассмотрим основные способы доступа к данным Последовательная обработка области БД. Областью БД может быть файл или другое множество страниц (блоков) памяти. Последовательная обработка предполагает, что система последовательно просматривает страницы, пропускает пустые участки и выдаёт записи в физической последовательности их хранения. Доступ по ключу базы данных (КБД). КБД определяет местоположение записи в памяти ЭВМ. Зная его, система может извлечь нужную запись заодно обращение к памяти.

Доступ по ключу (в частности, первичному. Если система обеспечивает доступ по ключу, то этот ключ также может использоваться при запоминании записи (для определения места размещения записи в памяти. В базах данных применяются такие способы доступа по ключу, как индексирование, хеширование и кластеризация.
Примечание:в иерархических и сетевых СУБД есть ещё доступ по структуре. Эта разновидность доступа применяется для групповых отношений и позволяет перейти к предыдущему или следующему экземпляру группового отношения, к экземпляру- владельцу группового отношения или к списку подчинённых экземпляров.
6.2. Индексирование данных Определим индексирование как способ доступа к данным в реляционной таблице с помощью специальной структуры – индекса. Индекс – это структура, которая определяет соответствие значения ключа записи (атрибута или группы атрибутов) и местоположения этой записи
– КБД (Рис. Каждый индекс связан с определённой таблицей, но является внешним по отношению к таблице и обычно хранится отдельно от не. Индекс
Пространство памяти Значение атрибута
КБД
F6:00 Волкова
…
Белова
FA:00
F6:1E Волков
… Волков
F6:1E
F6:31 Поспелов
…
Волкова
F6:00
…
Осипов
FA:2B
FA:00 Белова
…
Поспелов
F6:31
FA:1D Фридман
…
Фридман
FA:1D
FA:2B Осипов
… Рис. Пример индекса Индекс обычно хранится в отдельном файле или отдельной области памяти. Пустые значения атрибутов (NULL) не индексируются. Индексирование используется для ускорения доступа к записям по значению ключа и не влияет на размещение данных этой таблицы. Ускорение поиска данных через индекс обеспечивается за счёт:
1) упорядочивания значений индексируемого атрибута. Это позволяет просматривать в среднем половину индекса при линейном поиске
2) индекс занимает меньше страниц памяти, чем сама таблица, поэтому система тратит меньше времени на чтение индекса, чем на чтение таблицы. Индексы поддерживаются динамически, те. после обновления таблицы
– добавления или удаления записей, а также модификации индексируемых полей, – индекс приводится в соответствие с последней версией данных таблицы. Обновление индекса, естественно, занимает некоторое время иногда, очень большое, поэтому существование многих индексов может замедлить работу БД. Примечание в реальных СУБД существуют методы оптимизации переиндексации. Например, при выполнении пакетной операции модификации БД обновление индексов может происходить один раз после внесения всех изменений в данные.

Обращение к записи таблицы через индексы осуществляется в два этапа сначала СУБД считывает индекс в оперативную память (ОП) и находит в нём требуемое значение атрибута и соответствующий адрес записи (КБД), затем поэтому адресу происходит обращение к внешнему запоминающему устройству. Индекс загружается в ОП целиком или хранится в ней постоянно вовремя работы с таблицей БД, если хватает объёма ОП. Индекс называется первичным если каждому значению индекса соответствует уникальное значение ключа. Индекс по ключу, допускающему дубликаты значений, называется вторичным. Большинство СУБД автоматически строят индекс по первичному ключу и по уникальным столбцам. Эти индексы используются для проверки ограничения целостности
unique уникальность. Для каждой таблицы можно одновременно иметь несколько первичных и вторичных индексов, что также относится к достоинствам индексирования. Различают индексы по одному полю и по нескольким (составные. Составной индекс включает два или более столбца одной таблицы (Рис. Последовательность вхождения столбцов в индекс определяется при его создании. Из примера на Рис видно, что данные в индексе отсортированы по первому столбцу (ID), внутри группы с одинаковыми значениями ID – отсортированы по второму столбцу (EDATE), а внутри группы с одинаковыми значениями ID и EDATE – по третьему столбцу (CODE). Таблица Индекс
ID
EDATE
CODE
FIRM
PRICE
ID
EDATE
CODE
100 01.12.95 А
Комус
312.0 100 01.12.95 А 200 01.12.95 А Партия
321.5 100 02.12.95 А 100 02.12.95 А ОАО "Заря"
110.6 110 10.12.95 А 110 10.12.95 А Фирма "Б"
314.0 200 01.12.95 А 200 01.12.95 А Партия
114.0 200 01.12.95 А 200 02.12.95 А
Amos ltd.
52.8 200 02.12.95 А Рис. Пример составного индекса
6.2.1. Способы организации индексов Существует множество способов организации индексов
1. В плотных индексах для каждого значения ключа имеется отдельная запись индекса, указывающая место размещения конкретной записи. Неплотные (разреженные)индексы строятся в предположении, что на каждой странице памяти хранятся записи, отсортированные по значениям индексируемого атрибута. Тогда для каждой страницы в индексе задаётся диапазон значений ключей хранимых в ней записей, и поиск записи осуществляется среди записей на указанной странице.
2. Для больших индексов актуальна проблема сжатия ключа. Наиболее распространенный метод сжатия основан на устранении избыточности хранимых данных. Последовательно идущие значения ключа обычно имеют одинаковые начальные части, поэтому в каждой записи индекса можно хранить неполное значение ключа, а лишь информацию,

позволяющую восстановить его из известного предыдущего значения. Такой индекс называется сжатым.
3. Одноуровневый индекс представляет собой линейную совокупность значений одного или нескольких полей записи. На практике он используется редко. В развитых СУБД применяются более сложные методы организации индексов. Особенно эффективными являются многоуровневые индексы в виде сбалансированных деревьев (B- деревьев, balance trees).
6.2.2. Многоуровневые индексы на основе В-дерева дерево строится динамически по мере заполнения базы данными. Оно растёт вверх, и корневая вершина может меняться. Параметрами дерева являются порядок n и количество уровней. Порядок – это количество ссылок из вершины го уровня на вершины (го уровня. Пример построения B- дерева порядка 3 приведён на Рис. Шаги Шаги Шаги Шаги Шаги 11,12

8

12

8


4

6


9

12

8 12

4

6


9



13

14

12


4

6

8

14


9

10


13



16

100

12


4

6

8


9

10


13


14 25

16 Записи поступают в таком порядке:
шаг ключ 12 2
8 3
4 4
9 5
6 6
13 7
14 8
16 9
100 10 10 11 25 12 Рис. Пример построения дерева порядка 3 Каждое дерево должно удовлетворять следующим условиям
1. Все конечные вершины расположены на одном уровне, те. длина пути от корня к любой конечной вершине одинакова.
2. Каждая вершина может содержать n адресных ссылок и (n-1) ключей. Ссылка влево от ключа обеспечивает переход к вершине дерева с

меньшими значениями ключей, а вправо – к вершине с большими значениями.
3. Любая неконечная вершина имеет не менее n/2 подчинённых вершин. (Для деревьев нечётного порядка значение n/2 округляется в большую сторону.
4. Если неконечная вершина содержит k (k) ключей, то ей подчинена (k+1) вершина наследующем уровне иерархии. Алгоритм формирования дерева порядка n предполагает, что сначала заполняется корневая вершина. Затем при появлении новой записи корневая вершина делится, образуются подчинённые ей вершины. При запоминании каждой новой записи поиск места для неё начинается с корневой вершины. Если в существующем на данный момент дереве нет места для размещения нового ключа, происходит сдвиг ключей вправо или влево, если это невозможно – осуществляется перестройка дерева. В качестве конкретного примера рассмотрим индексирование в виде B- дерева, которое используется в СУБД Oracle (Рис. К
Апина-rowid
Белов-rowid
Белов-rowid В Д ПС Апина
Белов
Ван
Ге
Даева
Даль
Котов
Осина
Попов
Рогова
Серов
Ван
Ге-rowid
Даева- rowid
Даева- rowid
Даль- rowid
Котов
Осина
Попов
Попов
Рогова-rowid
Серов-rowid й уровень
2

(n–2) уровни й уровень Рис. Пример индексного блока СУБД Oracle Организация индексов в СУБД Oracle несколько отличается от рассмотренной выше классической организации дерева, но принцип остаётся тот же одинаковое количество уровней на любом пути и автоматическая сбалансированность. Верхние блоки индекса содержат автоматически вычисляемые значения, которые позволяют осуществлять поиск данных. Предпоследний (й уровень содержит значения индексируемого поля (атрибута) без повторов (те. каждое значение один раз. Самый нижний й уровень – блоки-листья, которые содержат индексируемые значения и соответствующие идентификаторы записей RowID (row identification, КБД), используемые для нахождения самих записей. Для неуникальных индексов значения идентификаторов строк (RowID) в блоках

листьях индекса также отсортированы по возрастанию. Блоки-листья связаны между собой двунаправленными ссылками. Поиск по ключу осуществляется следующим образом. Блок верхнего уровня (уровень 1) содержит некоторое значение X и указатели на верхнюю и нижнюю части индекса. Если значение искомого ключа больше X, то происходит переход к верхней части индекса (полевому указателю, иначе – к нижней части. Блоки второго и последующих уровней (кроме двух последних) хранят начальное X
0
и конечное значения к ключа, а также три указателя. Если значение искомого ключа меньше, чем X
0
, то происходит обращение полевому указателю если оно больше, чем кто происходит обращение по правому указателю если оно попадает в диапазон к – по среднему указателю. Вершины, которые делят следующий уровень дерева натри поддерева, могут занимать несколько уровней. Это зависит от количества индексируемых записей и среднего размера индексируемых значений. При обнаружении значения искомого ключа в блоке индекса происходит обращение к диску пои извлечение требуемой записи (записей. Если же значение не обнаружено, результат поиска пуст. Индекс в виде дерева автоматически поддерживается в сбалансированном виде. Это означает, что при переполнении какого-либо из блоков индекса происходит перераспределение значений ключей индекса (без физического перемещения записей данных. Например, если при добавлении новой записи с ключом "Горин" возникает переполнение соответствующего блока индекса (Рис, система может перестроить индекс так, как показано на Рис. Дал
Апина-rowid
Белов-rowid
Белов-rowid В Го О Р
Апина
Белов
Ван
Ге
Горин
Даева
Даль
Котов
Осина
Попов
Рогов
Серов
Ван
Ге-rowid
Горин-rowid
Даева-rowid
Даева-rowid
Даль
Котов
Осина
Попов
Попов
Рогова-rowid
Серов-rowid
1 2

(n–2) n–1 Рис. Пример перераспределения данных индексного блока СУБД Oracle Если все блоки-листья индекса заполнены приблизительно натри четверти, то при добавлении новой записи осуществляется полная

перестройка дерева путём введения дополнительного уровня. Всё это скрыто от пользователя и происходит автоматически. Структура дерева имеет следующие преимущества

дерево автоматически поддерживается в сбалансированном виде. Все блоки-листья в дереве расположены на одном уровне, следовательно, поиск любой записи в индексе занимает примерно одно и тоже время.

деревья обеспечивают хорошую производительность для широкого спектра запросов, включая поиск по конкретному значению и поиск в открытом и закрытом интервалах (благодаря ссылкам между блоками- листьями. Модификация данных таблицы выполняется достаточно эффективно, т.к. в блоках индекса обычно есть свободное место для размещения новых значений, а полная перестройка дерева выполняется достаточно редко. Производительность дерева одинаково хороша для маленьких и больших таблиц, и не меняется существенно приросте таблицы.
6.2.3. Использование индексов В системах, поддерживающих язык SQL, индекс создаётся командой create index
. Синтаксис этой команды следующий create index <имя_индекса> on <имя_таблицы>(<поле1> [, поле) параметры Имя индекса должно быть уникальным среди имён объектов БД. Если индекс составной, то входящие в него поля перечисляются через запятую. Необязательные параметры зависят от используемой СУБД. Например, с помощью следующей команды можно создать составной индекс для таблицы СОТРУДНИКИ (EMP) по полям Фамилия (fam) и Имя
(name): create index ind_emp_name on emp(fam, name); Индексы повышают производительность запросов, которые выбирают относительно небольшое число строк из таблицы. Для определения целесообразности создания индекса нужно проанализировать запросы, обращённые к таблице, и распределение данных в индексируемых столбцах. Система может воспользоваться индексом по определённому полю, если в запросе назначение этого поля накладывается условие, например
SELECT * FROM emp WHERE name = 'Даль Но даже при наличии такой возможности система не всегда обращается к индексу. Например, если запрос выбирает больше половины записей отношения, то извлечение данных через индекс потребует больше времени, чем последовательное чтение данных. Это следует из того, что данные через индекс выбираются не в той последовательности, в которой они хранятся в памяти. Для подобных запросов построение индекса нецелесообразно. Обращение к составному индексу возможно только в том случае, если в условиях выбора участвуют столбцы, представляющие собой лидирующую часть составного индекса. Если индекс, например, включает поля (X, Y, Z), то

обращение к индексу будет происходить в тех случаях, когда в условии запроса участвуют поля XYZ, XY или X, причём именно в таком порядке. При создании индекса большое значение имеет понятие селективности. Селективность определяется процентом строк, имеющих одинаковое значение индексируемого столбца чем выше этот процент, тем меньше селективность. Выбор столбцов для индекса определяется следующими соображениями В первую очередь выбираются столбцы, которые часто встречаются в условиях поиска. Стоит индексировать столбцы, которые используются для соединения таблиц или являются внешними ключами. В последнем случае наличие индекса позволяет обновлять строки подчинённой таблицы без блокировки основной таблицы, когда происходит интенсивное конкурентное обновление связанных между собою таблиц (подробнее о блокировках – раздел 5.4). Нецелесообразно индексировать столбцы с низкой селективностью. Исключения для низкой селективности составляют случаи, при которых выборка чаще производится по редко встречающимся значениям. Не индексируются столбцы, которые часто обновляются, т.к. команды обновления ведут к потере времени на обновление индекса. Не индексируются столбцы, которые часто используются как аргументы выражений или функций как правило, это не позволяет использовать индекс. В некоторых случаях использование составного индекса предпочтительнее, чем одиночного, а именно Несколько столбцов с низкой селективностью в комбинации друг с другом могут дать гораздо более высокую селективность. Если в запросах часто используются только столбцы, участвующие в индексе, система может вообще не обращаться к таблице для поиска данных.
6.3. Хеширование При ассоциативном доступе к хранимым записям, предполагающем определение местоположения записи по значениям содержащихся в ней данных, используются более сложные механизмы размещения. Для этой цели используются различные методы отображения значения ключа в адрес, например, методы хеширования (перемешивания. Принцип хеширования заключается в том, что для определения адреса записи в области хранения к значению ключевого поля этой записи применяется так называемая хеш-функция h(K). Она преобразует значение ключа K в адрес участка памяти (это называется свёрткой ключа. Новая запись будет размещаться потому адресу, который выдаст хеш-функция для ключа этой записи. При поиске записи по значению ключа K хеш-функция

выдаст адрес, указывающий на начало того участка памяти, в котором надо искать эту запись.
Хеш-функция h(K) должна обладать двумя основными свойствами
1) выдавать такие значения адресов, чтобы обеспечить равномерное распределение записей в памяти, в частности, для близких значений ключа значения адресов должны сильно отличаться, чтобы избегать перекосов в размещении данных
K
1

K
2

h(K
1
)>>h(K
2
) V h(K
2
)>>h(K
1
),
2) для разных значений ключа выдавать разные адреса
K
1

K
2

h(K
1
)

h(K
2
). Второе требования является сложно выполнимым. Трудно подобрать такую хеш-функцию, которая для любого распределения значений ключа всегда выдавала бы разные адреса для разных значений. Для реальных функций хеширования допускается совпадение значений функции h(K) для различных ключей. Для разрешения неопределённости при совпадении адресов после вычисления h(K) используются специальные методы (см. раздел
4.5.3.2). Недостаток методов подбора хеш-функций заключается в том, что количество данных и распределение значений ключа должны быть известны заранее. Также методы хеширования неудобны тем, что записи обычно неупорядочены по значению ключа, что приводит к дополнительным затратам, например, при выполнении сортировки. К преимуществам хеширования относится то, что ускоряется доступ к данным по значению ключа. Обращение к данным происходит за одну операцию ввода/вывода, т.к. значение ключа с помощью хеш-функции непосредственно преобразуется в адрес соответствующей записи (или адрес блока памяти, в котором хранится эта запись. При этом ненужно создавать никаких дополнительных структур типа индекса) и тратить память на их хранение.
6.3.1. Методы хеширования Многочисленные эксперименты с реальными данными выявили удовлетворительную работу двухосновных типов хеш-функций. Один из них основан наделении, другой – на умножении. Все рассуждения ведутся в предположении, что хеш-функция h(K): 0

h(K)

N для всех ключей K, где N – размер памяти (количество ячеек. Метод деления использует остаток отделения на М h(K)= К mod M.
(4.1) Если М – чётное число, то прич тных К значение h(K) будет чётным, и наоборот, что даёт значительные смещения значений функции для близких значений К. Нельзя брать М кратным основанию системы счисления машины, а также кратным 3. Вообще М должно удовлетворять условию М

r k

a , где k и a – небольшие числа, а r – "основание системы счисления" для большинства используемых литер (как правило, 128 или 256), т.к. остаток отделения на такое число оказывается обычно простой суперпозицией цифр ключа. Чаще всего в качестве М берут простое число, например, вполне удовлетворительные результаты даёт М = 1009. Мультипликативный метод также легко реализовать. В соответствии с ним хеш-функция определяется так













1
mod
M
h(K)
K
w
A
,
(4.2) где w – размер машинного слова (обычно, 2 31
); А – целое число простое по отношению ка некоторая степень основания системы счисления ЭВМ
(2
m
). Таким образом, в качестве значения функции берутся M правых значащих цифр дробной части произведения значения ключа и константы A/w. Преимущество второго метода перед первым обусловлено тем, что произведение обычно вычисляется быстрее, чем деление. При использовании любых методов хеширования для размещения записей должен быть выделен участок памяти размером N. Для того чтобы полученное в результате значение h(K) не вышло заграницы отведённого участка памяти, окончательно адрес записи вычисляется так
А(К) = h(K) mod N.
(4.3)
6.3.2. Разрешение коллизий Случай, когда для двух и более ключей выдаётся одинаковый адрес, называется коллизией. Наличие коллизий снижает эффективность хеширования. Разрешение коллизий достигается путём рехеширования – специального алгоритма, который используется каждый раз при размещении новой записи или при поиске существующей, если возникла коллизия. В системах баз данных рехеширование выполняется одним из следующих способов
1. Открытая адресация новая запись размещается вслед за последней записью на данной странице или наследующей, если страница заполнена. Для последней страницы памяти следующей является первая страница. Поиск записи осуществляется также последовательно, откуда следует, что записи нельзя удалять физически (с освобождением памяти, иначе цепочка рехешированных записей прервётся, и часть записей может быть "потеряна.
2. Использование коллизионных страниц новая запись размещается на одной из коллизионных страниц, относящихся к таблице (в области переполнения. Для ускорения поиска рехешированных записей может использоваться связанная область переполнения, для которой на странице хранится ссылка на коллизионную страницу. Нулевое значение такой ссылки говорит об отсутствии коллизий для данных, размещённых на этой странице.
3. Многократное хеширование. Заключается в том, что при возникновении коллизии для поиска другого адреса (возможно, на коллизионных страницах) применяется другая функция хеширования.

Примечание значения ключа хеширования необязательно должны быть уникальными. В реальных базах данных в качестве адреса записи может выступать адрес блока страницы памяти, в котором размещается несколько записей, возможно, с одинаковым значением ключа. Коллизией в этом случае является ситуация переполнения блока, адрес которого получен в результате применения функции хеширования к значению ключа новой записи. Тогда система выполнит для этой записи рехеширование.
6.3.3. Использование хеширования Хеширование таблицы полезно в следующих случаях В таблице есть уникальный ключи большинство запросов обращается к записям по значению этого ключа, например
SELECT список выбора
FROM таблица
WHERE unique_key = значение Значение, указанное в условии, хешируется; поэтому хеш-значению происходит прямой доступ к соответствующему блоку данных (обычно, одно физическое чтение, если нет коллизий и запись помещается водном блоке. Для неуникального хеш-ключа все записи с таким значением ключа помещаются водном блоке, который также можно прочитать за один раз. Таблица практически статична (редко обновляется. Число записей и их средний размер можно определить заранее и сразу выделить под таблицу требуемое физическое пространство. Хеширование не рекомендуется в следующих случаях Нельзя сразу выделить столько памяти, сколько требуется таблице. Если потребуется выделять таблице дополнительную память, эта память будет отведена под коллизионные страницы, что сильно ухудшит производительность (это следует из формулы (4.3), по которой рассчитывается адрес записи. Большинство запросов выбирает записи в некотором интервале значений ключа. Хеширование не даёт здесь преимуществ, т.к. записи обычно не упорядочены, и система использует последовательное чтение. Эффективность использования хеширования не в последней степени определяется качеством хеш-функции. Системы, поддерживающие возможность хеширования данных, обычно имеют встроенную хеш-функцию, но и позволяют пользователю задавать свою. Это может понадобиться тогда, когда встроенная хеш-функция не даёт хороших результатов, а пользовательская хеш-функция может учесть особенности распределения значений конкретного ключа. Если же ключ является уникальными распределение его значений равномерно, то сами значения могут быть использованы в качестве хеш-значений (тогда данные будут размещаться в порядке увеличения значений хеш-ключа).