|
|
Физическая организация данных
Шаги 11,12
4* а*
• 13* •
• Ifiwe
•31*110*
Ж«гж 6.7
Рис.4.5. Пример построения Б-дерева порядка 3
Каждое Б-дерево должно удовлетворять следующим условиям:
Все конечные вершины расположены на одном уровне, т.е. длина пути от корня к любой конечной вершине одинакова.
Каждая вершина может содержать n адресных ссылок и (n-1) ключей. Ссылка влево от ключа обеспечивает переход к вершине дерева с меньшими значениями ключей, а вправо - к вершине с большими значениями.
Любая неконечная вершина имеет не менее n/2 подчинённых вершин.
(Для деревьев нечётного порядка значение n/2 округляется в большую сторону).
Если неконечная вершина содержит k (k
Алгоритм формирования Б-дерева порядка nпредполагает, что сначала заполняется корневая вершина. Затем при появлении новой записи корневая вершина делится, образуются подчинённые ей вершины. При запоминании каждой новой записи поиск места для неё начинается с корневой вершины. Если в существующем на данный момент Б-дереве нет места для размещения нового ключа, происходит сдвиг ключей вправо или влево, если это невозможно - осуществляется перестройка дерева.
В качестве конкретного примера рассмотрим индексирование в виде Б-дерева, которое используется в СУБД Oracle (рис. 4.6).
Рис.4.6. Пример индексного блока СУБД Oracle
Организация индексов в СУБД Oracle несколько отличается от рассмот-ренной выше классической организации Б-дерева, но принцип остаётся тот же: одинаковое количество уровней на любом пути и автоматическая сбалансированность. Верхние блоки индекса содержат автоматически вычисляемые значения, которые позволяют осуществлять поиск данных. Предпоследний (п-1)-й уровень содержит значения индексируемого поля (атрибута) без повторов (т.е. каждое значение один раз). Самый нижний п-й уровень - блоки-листья, которые содержат индексируемые значения и соответствующие идентификаторы записей RowID (row identification, КБД), используемые для нахождения самих записей. Для неуникальных индексов значения идентификаторов строк (RowID) в блоках-листьях индекса также отсортированы по возрастанию. Блоки-листья связаны между собой двунаправленными ссылками.
Поиск по ключу осуществляется следующим образом. Блок верхнего уровня (уровень 1) содержит некоторое значение X и указатели на верхнюю и нижнюю части индекса. Если значение искомого ключа больше X, то происходит переход к верхней части индекса (по левому указателю), иначе - к нижней части. Блоки второго и последующих уровней (кроме двух последних) хранят начальное X0 и конечное значения Хк ключа, а также три указателя. Если значение искомого ключа меньше, чем Х0, то происходит обращение по левому указателю; если оно больше, чем Хк, то происходит обращение по правому указателю; если оно попадает в диапазон ХО^Хк - по среднему указателю. Вершины, которые делят следующий уровень дерева на три поддерева, могут занимать несколько уровней. Это зависит от количества индексируемых записей и среднего размера индексируемых значений.
При обнаружении значения искомого ключа в блоке индекса происходит обращение к диску по RowID и извлечение требуемой записи (записей). Если же значение не обнаружено, результат поиска пуст.
Индекс в виде B-дерева автоматически поддерживается в сбалансированном виде. Это означает, что при переполнении какого-либо из блоков индекса происходит перераспределение значений ключей индекса (без физического перемещения записей данных). Например, если при добавлении новой записи с ключом "Горин" возникает переполнение соответствующего блока индекса (рис. 4.6), система может перестроить индекс так, как показано на рис. 4.7.
Рис.4.7. Пример перераспределения данных индексного блока СУБД Oracle
Если все блоки-листья индекса заполнены приблизительно на три четверти, то при добавлении новой записи осуществляется полная пере-стройка B-дерева путём введения дополнительного уровня. Всё это скрыто от пользователя и происходит автоматически.
Структура B-дерева имеет следующие преимущества:
B-дерево автоматически поддерживается в сбалансированном виде.
Все блоки-листья в дереве расположены на одном уровне, следовательно, поиск любой записи в индексе занимает примерно одно и то же время.
B-деревья обеспечивают хорошую производительность для широкого спектра запросов, включая поиск по конкретному значению и поиск в открытом и закрытом интервалах (благодаря ссылкам между блоками- листьями).
Модификация данных таблицы выполняется достаточно эффективно, т.к. в блоках индекса обычно есть свободное место для размещения новых значений, а полная перестройка дерева выполняется достаточно редко.
Производительность B-дерева одинаково хороша для маленьких и больших таблиц, и не меняется существенно при росте таблицы.
Использование индексов
В системах, поддерживающих язык SQL, индекс создаётся командой create index. Синтаксис этой команды следующий:
create index <имя_индекса> on <имя_таблицы>(<поле1> [, <поле2>,...])
[<параметры>];
Имя индекса должно быть уникальным среди имён объектов БД. Если индекс составной, то входящие в него поля перечисляются через запятую. Необязательные <параметры> зависят от используемой СУБД.
Например, с помощью следующей команды можно создать составной индекс для таблицыСОТРУДНИКИ (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).
Нецелесообразно индексировать столбцы с низкой селективностью. Исключения для низкой селективности составляют случаи, при которых выборка чаще производится по редко встречающимся значениям.
Не индексируются столбцы, которые часто обновляются, т.к. команды об новления ведут к потере времени на обновление индекса.
Не индексируются столбцы, которые часто используются как аргументы выражений или функций: как правило, это не позволяет использовать ин декс.
В некоторых случаях использование составного индекса предпочтительнее, чем одиночного, а именно:
Несколько столбцов с низкой селективностью в комбинации друг с другом могут дать гораздо более высокую селективность.
Если в запросах часто используются только столбцы, участвующие в индексе, система может вообще не обращаться к таблице для поиска данных.
Хеширование
При ассоциативном доступе к хранимым записям, предполагающем оп ределение местоположения записи по значениям содержащихся в ней данных, используются более сложные механизмы размещения. Для этой цели используются различные методы отображения значения ключа в адрес, например, методы хеширования (перемешивания).
Принцип хеширования заключается в том, что для определения адреса записи в области хранения к значению ключевого поля этой записи применяется так называемая хеш-функция h(K). Она преобразует значение ключа K в адрес участка памяти (это называется свёрткой ключа). Новая запись будет размещаться по тому адресу, который выдаст хеш-функция для ключа этой записи. При поиске записи по значению ключа K хеш-функция выдаст адрес, указывающий на начало того участка памяти, в котором надо искать эту запись.
Хеш-функция h(K) должна обладать двумя основными свойствами:
1. выдавать такие значения адресов, чтобы обеспечить равномерное распределение записей в памяти, в частности, для близких значений ключа значения адресов должны сильно отличаться, чтобы избегать перекосов в размещении данных:
K1
K2^h(K 1 )>>h(K2) V K2>>h(K1)
2. для разных значений ключа выдавать разные адреса:
K1^K2^h(K1)^h(K2)
Второе требования является сложно выполнимым. Трудно подобрать такую хеш-функцию, которая для любого распределения значений ключа всегда выдавала бы разные адреса для разных значений. Для реальных функций хеширования допускается совпадение значений функции h(K)для различных ключей. Для разрешения неопределенности при совпадении адресов после вычисления h(K) используются специальные методы (см. раздел 4.5.3.2).
Недостаток методов подбора хеш-функций заключается в том, что количество данных и распределение значений ключа должны быть известны заранее. Также методы хеширования неудобны тем, что записи обычно неупорядочены по значению ключа, что приводит к дополнительным затратам, например, при выполнении сортировки. К преимуществам хеширования относится то, что ускоряется доступ к данным по значению ключа. Обращение к данным происходит за одну операцию ввода/вывода, т.к. значение ключа с помощью хеш-функции непосредственно преобразуется в адрес соответствующей записи (или адрес блока памяти, в котором хранится эта запись). При этом не нужно создавать никаких дополнительных структур (типа индекса) и тратить память на их хранение.
Методы хеширования
Многочисленные эксперименты с реальными данными выявили удовле творительную работу двух основных типов хеш-функций. Один из них основан на делении, другой - на умножении. Все рассуждения ведутся в предположении, что хеш-функция h(K): 0 < h(K) < N для всех ключей K, где N - размер памяти (количество ячеек).
Метод деления использует остаток от деления на М: h(K)= К mod M (4.1)
Если М - четное число, то при четных К значение h(K) будет четным, и наоборот, что дает значительные смещения значений функции для близких значений К. Нельзя брать М кратным основанию системы счисления машины, а также кратным 3. Вообще, М должно удовлетворять условию:
M ^rk+a,
где k и a - небольшие числа, а r - "основание системы счисления” для большинства используемых литер (как правило, 128 или 256), т.к. остаток от деления на такое число оказывается обычно простой суперпозицией цифр
ключа. Чаще всего в качестве М берут простое число, например, вполне удовлетворительные результаты даёт М = 1009.
(4.2)
Мультипликативный метод также легко реализовать. В соответствии с ним хеш- функция определяется так:
где w - размер машинного слова (обычно, 231); А - целое число простое по отношению к w; а M - некоторая степень основания системы счисления ЭВМ (2m). Таким образом, в качестве значения функции берутся M правых значащих цифр дробной части произведения значения ключа и константы A/w. Преимущество второго метода перед первым обусловлено тем, что произведение обычно вычисляется быстрее, чем деление.
При использовании любых методов хеширования для размещения записей должен быть выделен участок памяти размером N. Для того чтобы полученное в результате значение h(K) не вышло за границы отведённого участка памяти, окончательно адрес записи вычисляется так:
А(К) = h(K) mod N (4.3)
Разрешение коллизий
Случай, когда для двух и более ключей выдаётся одинаковый адрес, называется коллизией. Наличие коллизий снижает эффективность хеширования.
Разрешение коллизий достигается путём рехеширования - специального алгоритма, который используется каждый раз при размещении новой записи или при поиске существующей, если возникла коллизия. В системах баз данных рехеширование выполняется одним из следующих способов:
Открытая адресация: новая запись размещается вслед за последней запи-сью на данной странице или на следующей, если страница заполнена. (Для последней страницы памяти следующей является первая страница). Поиск записи осуществляется также последовательно, откуда следует, что записи нельзя удалять физически (с освобождением памяти), иначе цепочка рехешированных записей прервётся, и часть записей может быть "потеряна".
Использование коллизионных страниц: новая запись размещается на одной из коллизионных страниц, относящихся к таблице (в
области переполнения). Для ускорения поиска рехешированных записей может использоваться связанная область переполнения, для которой на странице хранится ссылка на коллизионную страницу. Нулевое значение
такой ссылки говорит об отсутствии коллизий для данных, размещённых на этой странице
3. Многократное хеширование. Заключается в том, что при возникновении коллизии для поиска другого адреса (возможно, на коллизионных страни цах) применяется другая функция хеширования.
Примечание: значения ключа хеширования не обязательно должны быть уникальными. В реальных базах данных в качестве адреса записи может выступать адрес блока (стра-ницы памяти), в котором размещается несколько записей, возможно, с одинаковым значением ключа. Коллизией в этом случае является ситуация переполнения блока, адрес которого получен в результате применения функции хеширования к значению ключа новой записи. Тогда система выполнит для этой записи рехеширование.
Использование хеширования
Хеширование таблицы полезно в следующих случаях:
В таблице есть уникальный ключ, и большинство запросов обращаются к записям по значению этого ключа, например:
SELECT <список выбора> FROM <таблица> WHERE unique_key = <значение>;
Значение, указанное в условии, хешируется; по этому хеш-значению происходит прямой доступ к соответствующему блоку данных (обычно, одно физическое чтение, если нет коллизий и запись помещается в одном блоке).
Для неуникального хеш-ключа все записи с таким значением ключа поме щаются в одном блоке, который также можно прочитать за один раз.
Таблица практически статична (редко обновляется). Число записей и их средний размер можно определить заранее и сразу выделить под таблицу требуемое физическое пространство.
Хеширование не рекомендуется в следующих случаях:
Нельзя сразу выделить столько памяти, сколько требуется таблице. Если потребуется выделять таблице дополнительную память, эта память будет отведена под коллизионные страницы, что сильно ухудшит производительность (это следует из формулы (4.3), по которой рассчитывается адрес записи)./Н>
Большинство запросов выбирают записи в некотором интервале значений ключа. Хеширование не даёт здесь преимуществ, т.к. записи обычно не упорядочены, и система использует последовательное чтение.
Эффективность использования хеширования не в последней степени оп ределяется качеством хеш-функции. Системы, поддерживающие возможность хеширования данных, обычно имеют встроенную хеш-функцию, но ипозволяют пользователю задавать свою. Это может понадобиться тогда, когда встроенная хеш-функция не даёт хороших результатов, а пользовательская хеш- функция может учесть особенности распределения значений конкретного ключа. Если же ключ является уникальным и распределение его значений равномерно, то сами значения могут быть использованы в качестве хеш- значений (тогда данные будут размещаться в порядке увеличения значений хеш- ключа).
Кластеризация данных
Принцип организации кластеров
Кластеризация является методом совместного хранения родственных данных (таблиц). Кластер - это структура памяти, в которой хранится набор таблиц (в одних и тех же блоках памяти). Кластеризуемые таблицы должны иметь общие столбцы, используемые для соединения (например, первичный ключ таблицы ТОВАРЫ и внешний ключ таблицы ПОСТАВКИ, рис. 4.8,б).
|
|
|
Скачать 487.44 Kb.