Министерство образования российской федерации московский государственный институт электроники и математики (Технический университет)
 Скачать 1.02 Mb.
|
|
6. МЕХАНИЗМЫ РАЗМЕЩЕНИЯ ДАННЫХ И ДОСТУПА К ДАННЫМ При создании новой записи во многих случаях существенно размещение этой записи в памяти, т.к. это оказывает огромное влияние на время выборки. Простейшая стратегия размещения данных заключается в том, что новая запись размещается на первом свободном участке (если ведется учёт свободного про- странства) или вслед за последней из ранее размещённых записей. Среди более сложных методов можно отметить хеширование и кластеризацию. 6.1. Способы доступа к записям Рассмотрим основные способы доступа к данным. Последовательная обработка области БД. Областью БД может быть файл или другое множество страниц. Последовательная обработка предполагает, что система последовательно просматривает страницы, пропускает пустые участки и выдаёт записи в физической последовательности их хранения. – 48 – Доступ по ключу базы данных (КБД). КБД определяет местоположение записи в памяти ЭВМ. Зная его, система может извлечь нужную запись за одно обращение к памяти. Доступ по структуре. Эта разновидность доступа применяется для группо- вых отношений и позволяет перейти к предыдущему или следующему эк- земпляру группового отношения, к экземпляру-владельцу группового отно- шения или к списку подчинённых экземпляров. Доступ по первичному ключу. Первичный ключ идентифицирует записи внутри типа. Если система обеспечивает доступ по первичному ключу, то он (ключ) используется также при запоминании записи и, более того, его значе- ние в этом случае обычно используется при размещении записи в памяти. Наиболее распространённые механизмы доступа по первичному ключу – индексирование и хеширование. 6.2. Индексирование данных При случайном доступе к отдельным записям наиболее эффективным яв- ляется доступ по ключу. Для ускорения доступа к записям по ключевому атри- буту (или группе атрибутов) создаётся специальная структура – индекс, кото- рый определяет соответствие значения атрибута (группы атрибутов) и местопо- ложения записи (рис. 6.1). Индекс Пространство памяти Значение атрибута КБД F6:00 Волкова … Белова FA:00 F6:1E Волков … Волков F6:1E F6:31 Поспелов … Волкова F6:00 … Осипов FA:2B FA:00 Белова … Поспелов F6:31 FA:1D Фридман … Фридман FA:1D FA:2B Осипов … Рис. 6.1. Пример индекса Значения индексируемого атрибута упорядочиваются (чаще всего, по возрастанию). Индекс обычно хранится в отдельном файле или отдельной об- ласти памяти. Пустые значения атрибутов (null) не индексируются. Индексы поддерживаются динамически, т.е. после обновления БД – до- бавлении или удалении записей, а также при модификации полей записи, вхо- дящих в ключ, – индекс приводится в соответствие с обновленной версией БД. Обновление индекса, естественно, занимает некоторое время (иногда, очень большое), поэтому существование многих индексов может замедлить работу БД. В реальных СУБД существуют методы оптимизации переиндексации. На- пример, при выполнении пакетной операции модификации БД обновление ин- дексов может происходить один раз после внесения всех изменений в записи. Обращение к записи через индексы осуществляется в два этапа: сначала в индексной структуре находится требуемое значение атрибута и соответствую- щий адрес записи, затем по этому адресу происходит обращение к внешнему – 49 – запоминающему устройству (ВЗУ). Индекс загружается в ОП целиком (или хранится в ней постоянно во время работы с БД). В том случае, если каждому значению индекса соответствует уникальное значение ключа, такой индекс называется первичным. Если же индекс строится по ключу, допускающему дубликаты значений, такой индекс называется вто- ричным. Для каждой таблицы можно одновременно поддерживать несколько первичных и вторичных индексов, что также относится к достоинствам индек- сирования. Различают индексы по одному полю и по нескольким (составные). Со- ставной индекс включает два или более столбца одной таблицы (рис. 6.2). По- следовательность вхождения столбцов в индекс определяется при его создании. Таблица Индекс ID DATA CODE FIRM PRICE ID DATA CODE 100 01.12.95 А4 Комус 312.0 100 01.12.95 А4 200 01.12.95 А4 Партия 321.5 100 02.12.95 А2 100 02.12.95 А2 ОАО "Заря" 110.6 110 10.12.95 А4 110 10.12.95 А4 Фирма "Б+" 314.0 200 01.12.95 А2 200 01.12.95 А2 Партия 114.0 200 01.12.95 А4 200 02.12.95 А1 Amos ltd. 52.8 200 02.12.95 А1 Рис. 6.2. Пример составного индекса 6.2.1. Способы организации индексов Существует множество способов организации индексов: 1. В плотных индексах для каждого значения ключа имеется отдельная статья индекса, указывающая место размещения конкретной записи. Неплотные индексы строятся в предположении, что на каждой странице памяти (или в блоке) хранятся записи, отсортированные по значениям ключа индексирова- ния. Тогда для каждой страницы индекс задаёт диапазон значений ключей хранимых в ней записей, и поиск записи осуществляется среди записей на указанной странице. 2. Для больших индексов актуальна проблема сжатия ключа. Наиболее рас- пространенный метод сжатия основан на устранении избыточности храни- мых данных. Последовательно идущие значения ключа обычно имеют оди- наковые начальные части, поэтому в каждой статье индекса можно хранить не полное значение ключа, а лишь информацию, позволяющую его восста- новить из известного предыдущего значения. 3. Одноуровневый индекс представляет собой линейную совокупность значе- ний одного или нескольких полей записи. На практике он используется только в простейших случаях, когда количество индексируемых записей не- велико. В более сложных случаях индекс занимает много памяти (иногда – несколько страниц), и возникает задача минимизации доступа к нему. Тогда индекс разбивается на иерархические уровни, что позволяет ускорить поиск требуемого значения. Особенно эффективной является организация много- уровневых индексов в виде сбалансированных деревьев (balance trees, B- деревьев), в которых все пути от корня к листьям имеют одинаковую длину. – 50 – 6.2.2. Многоуровневые индексы на основе В-дерева B-дерево строится динамически по мере заполнения базы данными. Оно растёт вверх, и корневая вершина может меняться. Параметрами B-дерева яв- ляются порядок n и количество уровней. Порядок – это количество ссылок из вершины i-го уровня на вершины (i+1)-го уровня. Каждое B-дерево должно удовлетворять следующим условиям: 1. Каждая вершина может содержать n адресных ссылок и (n-1) ключей. Ссыл- ка влево от ключа обеспечивает переход к вершине дерева с меньшими по значению ключами, а вправо – к вершине с большими ключами. 2. Любая неконечная вершина имеет не менее n/2 подчинённых вершин. 3. Если неконечная вершина содержит k (kn) ключей, то ей подчинена (k+1) вершина на следующем уровне иерархии. 4. Все конечные вершины расположены на одном уровне. Алгоритм формирования B-дерева порядка n предполагает, что сначала заполняется корневая вершина. Затем при появлении новой записи корневая вершина делится, образуются подчинённые ей вершины. При запоминании ка- ждой новой записи поиск места для неё начинается с корневой вершины. Если в существующем на данный момент B-дереве нет места для размещения нового ключа, происходит сдвиг ключей вправо или влево, если это невозможно – осуществляется перестройка дерева. Пример построения B-дерева порядка 3 приведён на рис. 6.3. Шаги 1,2 Шаги 3,4,5 Шаги 6,7 Шаги 8,9,10 Шаги 11,12 8 12 8 4 6 9 12 8 12 4 6 9 1314 12 4 6 8 14 9 10 13 16100 12 4 6 8 910 13 14 25 16 31100 Записи поступают в таком порядке: шаг ключ 1 12 2 8 3 4 4 9 5 6 6 13 7 14 8 16 9 100 10 10 11 25 12 31 Рис. 6.3. Пример построения B-дерева порядка 3 – 51 – Индексирование в виде B-дерева используется, например, в СУБД Oracle (рис. 6.4). К Алин-rowid Белов-rowid Белов-rowid В Д П С Алин Белов Ван Ге Даев Даль Котов Осина Попов Рогов Серов Ван-rowid Ге-rowid Даев- rowid Даев- rowid Даль- rowid Котов–rowid Осина–rowid Попов-rowid Попов-rowid Рогов-rowid Серов-rowid 1 2 3(n–1) Рис. 6.4. Пример индексного блока СУБД Oracle Организация индексов в СУБД Oracle несколько отличается от рассмот- ренной выше классической организации B-дерева, но принцип остаётся тот же: одинаковое количество уровней на любом пути и автоматическая сбалансиро- ванность. Верхние блоки содержат данные индекса, которые ссылаются на бло- ки индекса нижних уровней. Самый нижний n–й уровень содержит блоки ин- декса (блоки-листья), которые содержат непосредственно данные индекса (ключи) и соответствующие идентификаторы строк ROWID (row identification, КБД), используемые для нахождения самих строк. Блоки-листья связаны между собой указателями. Поиск по ключу осуществляется следующим образом. Блок верхнего уровня (уровень 1) содержит некоторое значение X и указатели на верхнюю и нижнюю части индекса. Если значение искомого ключа больше X, то происхо- дит переход к верхней части индекса (по левому указателю), иначе – к нижней части. Блоки второго и последующих уровней (кроме двух последних) хранят начальное X 0 и конечное значения X к ключа, а также три указателя. Если значе- ние искомого ключа больше, чем X 0 , то происходит обращение по левому ука- зателю; если оно меньше, чем X к , то происходит обращение по правому указа- телю; если оно попадает в диапазон X 0 X к – по среднему указателю. Предпоследний уровень содержит значения ключей индекса и указатели на блоки последнего уровня, последний – значения ключей индекса и иденти- фикаторы строк (ROWID). Различие между двумя последними уровнями в том, что в случае неуникальных индексов значение ключа индекса в предпоследнем уровне содержится один раз, а в последнем – столько раз, сколько оно встреча- ется в записях файла данных. При обнаружении значения искомого ключа в блоке индекса происходит обращение к диску по ROWID и извлечение требуе- мой записи (записей). Если же значение не обнаружено, результат поиска пуст. – 52 – Уникальные ключи для каждого значения имеют только один соответст- вующий ROWID. Для неуникальных индексов значения идентификаторов строк также отсортированы по возрастанию. Индекс в виде B-дерева автоматически поддерживается в сбалансирован- ном виде. Это означает, что при переполнении какого-либо из блоков индекса происходит перераспределение значений ключей индекса (без физического пе- ремещения записей данных). Например, если при добавлении новой записи с ключом "Горин" возникает переполнение соответствующего блока индекса (рис. 6.4), система может перераспределить значения ключей так, как показано на рис. 6.5. Если все блоки-листья индекса заполнены приблизительно на три четвер- ти, то при добавлении новой записи осуществляется полная перестройка B- дерева путём введения дополнительного уровня. Всё это скрыто от пользовате- ля и происходит автоматически. Дал Алин-rowid Белов-rowid Белов-rowid В Го О Р Алин Белов Ван Ге Горин Даев Даль Котов Осина Попов Рогов Серов Ван-rowid Ге-rowid Горин-rowid Даев-rowid Даев-rowid Даль-rowid Котов-rowid Осина-rowid Попов-rowid Попов-rowid Рогов-rowid Серов-rowid 1 2 3(n–1) Рис. 6.5. Пример перераспределения данных индексного блока СУБД Oracle Структура B-дерева имеет следующие преимущества: Все блоки-листья в дереве одной и той же глубины, следовательно, поиск любой записи в индексе занимает примерно одно и то же время. B-дерево автоматически поддерживается в сбалансированном виде. B-деревья обеспечивают хорошую производительность для широкого спек- тра запросов, включая поиск по конкретному значению и поиск в открытом и закрытом интервалах. Модификация (т.е. добавление, обновление и удаление) строк выполняется достаточно эффективно. Производительность B-дерева одинаково хороша для маленьких и больших таблиц, и не меняется существенно при росте таблицы. – 53 – 6.2.3. Использование индексов В системах, поддерживающих язык SQL, индекс создаётся командой CREATE INDEX. Индексы повышают производительность запросов, которые выбирают относительно небольшое число строк из таблицы. Для определения целесообразности создания индекса нужно проанализировать запросы, обра- щённые к таблице, и распределение данных в индексируемых столбцах. Система может воспользоваться индексом по определённому полю, если в запросе на значение этого поля накладывается условие, например: SELECT * FROM emp WHERE name = 'Даль'; Но даже при наличии такой возможности система не всегда обращается к ин- дексу. Очевидно, что если запрос выбирает больше половины записей отноше- ния, то извлечение данных через индекс потребует больше времени, чем после- довательная обработка данных. В подобных случаях использование индекса нецелесообразно. Обращение к составному индексу возможно только в том случае, если в условиях выбора участвуют столбцы, представляющие собой лидирующую часть составного индекса. Если индекс, например, включает поля (X, Y, Z), то обращение к индексу будет происходить в тех случаях, когда в условии запроса участвуют поля XYZ, XY или X, причём именно в таком порядке. При создании индекса большое значение имеет понятие селективности. Селективность определяется процентом строк, имеющих одинаковое значение индексируемого столбца: чем выше этот процент, тем меньше селективность. Выбор индексируемых столбцов определяется следующими соображе- ниями: В первую очередь выбираются столбцы, которые часто встречаются в крите- риях поиска. Стоит индексировать столбцы, которые используются для соединения таб- лиц или являются внешними ключами. В последнем случае наличие индекса позволяет обновлять строки подчинённой таблицы без блокировки основной таблицы, когда происходит интенсивное конкурентное обновление связан- ных между собою таблиц. Нецелесообразно индексировать столбцы с низкой селективностью. Исклю- чения для низкой селективности составляют случаи, при которых выборка чаще производится по редко встречающимся значениям. Не индексируются столбцы, которые часто обновляются, т.к. команды об- новления ведут к потере времени на обновление индекса. Не индексируются столбцы, которые часто используются как аргументы функций или выражений: как правило, такие функции не позволяют исполь- зовать индекс. В некоторых случаях использование составного индекса предпочтитель- нее, чем одиночного: Несколько столбцов с низкой селективностью в комбинации с друг с другом могут дать гораздо более высокую селективность. – 54 – Если в запросах часто используются только столбцы, участвующие в индек- се, система может вообще не обращаться к таблице для поиска данных. Примечание: многие СУБД (в том числе, Oracle) автоматически строят индекс по первич- ному ключу и по уникальным столбцам. 6.3. Хеширование При ассоциативном доступе к хранимым записям, предполагающем оп- ределение местоположения записи по значениям содержащихся в ней данных, используются более сложные механизмы размещения. Для этой цели исполь- зуются различные методы отображения значения ключа в адрес, например, ме- тоды хеширования (перемешивания). Принцип хеширования заключается в том, что для ускорения поиска ин- формации область хранения данных разбивается на участки, каждому из кото- рых ставится в соответствие некоторое значение (указатель или адрес). Для оп- ределения, в какой участок будет помещена вновь добавляемая запись, к значе- нию ключевого поля этой записи применяется так называемая хеш-функция h(K). Она преобразует значение ключа K в адрес произвольного участка памяти (это называется свёрткой ключа). При поиске записи по известному значению ключа K хеш-функция выдаёт значение адреса, указывающее, где начинается тот участок памяти, в котором надо искать эту запись. Хеш-функция h(K) должна выдавать такие значения адресов, чтобы обес- печить равномерное распределение записей в памяти. При этом для близких значений ключа значения адресов должны сильно отличаться, чтобы избегать перекосов в размещении данных. Хорошая хеш-функция для каждого значения ключа выдаёт свой адрес, таким образом, извлечение записи производится за одно обращение к памяти. Для реальных функций хеширования допускается совпадение значений функции h(K) для различных ключей и для разрешения неопределённости после вычисления h(K) используются специальные методы. Недостаток методов подбора хеш-функций заключается в том, что коли- чество данных и распределение значений ключа должны быть известны зара- нее. Также методы хеширования неудобны тем, что записи неупорядочены по значению ключа, что приводит к дополнительным затратам, например, при вы- полнении сортировки. К преимуществам хеширования относится то, что обра- щение к данным происходит за одну операцию ввода/вывода, т.к. значение ключа непосредственно преобразуется в адрес соответствующей записи. 6.3.1. Методы хеширования Многочисленные эксперименты с реальными файлами выявили удовле- творительную работу двух основных типов хеш-функций. Один из них основан на делении, другой – на умножении. Все рассуждения ведутся в предположе- нии, что хеш-функция h(K): 0h(K)N для всех ключей K, где N – размер памя- ти (количество ячеек). Метод деления использует остаток от деления на М: h(K)= К mod M. – 55 – Если М – чётное число, то при чётных К значение h(K) будет чётным, и наобо- рот, что даёт значительные смещения значений функции для близких значений К. Нельзя брать М кратным основанию системы счисления машины, а также кратным 3. Вообще, М должно удовлетворять условию: М r k a , где k и a – небольшие числа, а r – "основание системы счисления" для боль- шинства используемых литер (как правило, 64, 256 или 100), т.к. остаток от де- ления на такое число оказывается обычно простой суперпозицией цифр ключа. Чаще всего в качестве М берут простое число, например, вполне удовлетвори- тельные результаты даёт М = 1009. Мультипликативный метод также легко реализовать. Он заключается в умножении значения ключа К на простую дробь и выделении правых значащих цифр результата: 1 mod M h(K) K w A , где w – размер машинного слова (обычно, 2 31 ), А – целое число простое по от- ношению к w, а M – некоторая степень основания системы счисления ЭВМ (2 m ). Таким образом, в качестве значения функции берутся m правых значащих цифр дробной части произведения значения ключа и числа A/w. Произведение обыч- но вычисляется быстрее, чем деление. Число А выбирают так, чтобы значение Q каждого из его байтов лежало в "хорошем" диапазоне (6.1) и не было слиш- ком близким к значениям других байтов или их дополнениям. 4 3 10 7 ; 3 2 7 4 ; 7 3 3 1 ; 10 3 4 1 Q Q Q Q (6.1) При использовании любых методов хеширования для размещения запи- сей должен быть выделен участок памяти размером N. Для того чтобы полу- ченное в результате значение h(K) не вышло за границы отведённого участка памяти, окончательно адрес записи вычисляется так: А(К) = h(K) mod N. 6.3.2. Разрешение коллизий Случай, когда для двух и более ключей выдаётся одинаковый индекс, на- зывается |