Тема_8 (1122356), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Базы данных.117Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (27)Индексы (14) Хэширование (1)Альтернативным и достаточно популярным подходом корганизации индексов является использование техникихэшированияЭто очень обширная тема, которая заслуживаетотдельного рассмотренияОграничимся здесь лишь несколькими замечаниямиОбщей идеей методов хэширования является применениек значению ключа некоторой функции свертки (хэшфункции), вырабатывающей значение меньшего размераЗначение хэш-функции затем используется для доступа кзаписи12.11.2009С.Д. Кузнецов.

Базы данных.118Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (28)Индексы (15) Хэширование (2)В самом простом, классическом случае сверткаключа используется как адрес в таблице,содержащей ключи и записиОсновным требованием к хэш-функции являетсяравномерное распределение значение сверткиодним из распространенных видов «хороших» хэшфункций являются функции, выдающие остаток отделения значения ключа на некоторое простое числоПри возникновении коллизийодна и та же свертка для нескольких значений ключаобразуются цепочки переполнения12.11.2009С.Д. Кузнецов.

Базы данных.119Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (29)Индексы (16) Хэширование (3)Главным ограничением этого метода являетсяфиксированный размер таблицыЕсли таблица заполнена слишком сильно илипереполнена, но возникнет слишком многоцепочек переполнения, и главное преимуществохэшированиядоступ к записи почти всегда за одно обращение ктаблицебудет утраченоРасширение таблицы требует ее полнойпеределки на основе новой хэш-функциисо значением свертки большего размера12.11.2009С.Д.

Кузнецов. Базы данных.120Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (30)Индексы (17) Хэширование (4)Идея доступа к данным на основе хэширования настолькопривлекательна потенциальная возможность за одно обращение к памятиполучить требуемые данные,что от нее невозможно отказаться при работе с данными вовнешней памятиИсходная идея кажется очевидной:если при управлении данными на основе хэширования восновной памяти хэш-функция вырабатывает адрес требуемого элемента,то при обращении к внешней памяти необходимо генерировать номер блока дискового пространства, вкотором находится запрашиваемый элемент данныхОсновная проблема относится к коллизиям12.11.2009С.Д.

Кузнецов. Базы данных.121Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (31)Индексы (18) Хэширование (5)Если при работе в основной памятипотенциально возникающими потребностямидополнительного поиска информации привозникновении коллизий можно, вообще говоря,пренебречьпоскольку время доступа к основной памяти мало,то при использовании внешней памяти любоедополнительное обращение вызываетсущественные накладные расходыОсновные методы хэширования для поискаинформации во внешней памяти направлены нарешение именно этой задачи12.11.2009С.Д. Кузнецов.

Базы данных.122Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (32)Индексы (19) Хэширование (6)В основе подхода расширяемого хэширования (ExtendibleHashing) лежит принцип использования деревьев цифровогопоиска в основной памятиВ основной памяти поддерживается справочник,организованный на основе бинарного дерева цифровогопоиска, ключами которого являются значения хэш-функции, а в листовых вершинах хранятся номера блоков записей вовнешней памятиВ этом случае любой поиск в дереве цифрового поискаявляется «успешным», т.е.

ведет к некоторому блокувнешней памятиВходит ли в этот блок искомая запись, обнаруживается ужепосле прочтения блока в основную память12.11.2009С.Д. Кузнецов. Базы данных.123Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (33)Индексы (20) Хэширование (7)Проблема коллизий переформулируется следующим образомКак таковых, коллизий не существуетМожет возникнуть лишь ситуация переполнения блока внешнейпамятиЭта ситуация обрабатывается такЗначение хэш-функции указывает на этот блок, но места длявключения записи в нем уже нетБлок расщепляется на два, и дерево цифрового поискапереформируется соответствующим образомКонечно, при этом может потребоваться расширение самогосправочникаРасширяемое хэширование хорошо работает в условияхдинамически изменяемого набора записей в хранимом файле,но требует наличия в основной памяти справочного дерева12.11.2009С.Д.

Кузнецов. Базы данных.124Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (34)Индексы (21) Хэширование (8)Идея линейного хэширования (Linear Hashing)состоит в том, чтобы можно было обойтись безподдержания справочника в основной памятиОсновой метода является то, что для адресацииблока внешней памяти всегда используютсямладшие биты значения хэш-функцииЕсли возникает потребность в расщеплении, тозаписи перераспределяются по блокам так,чтобы адресация осталась правильной12.11.2009С.Д.

Кузнецов. Базы данных.125Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (35)Индексы (22) Журнальная информация (1)Структура журнала обычно является сугубо частным деломконкретной реализацииОтметим только самые общие свойства.Журнал обычно представляет собой чисто последовательный файлс записями переменного размера, которые можно просматривать впрямом или обратном порядкеОбмены производятся стандартными порциями (страницами) сиспользованием буфера оперативной памятиВ грамотно организованных системах структура (и тем более,смысл) журнальных записей известна только компонентам СУБД,ответственным за журнализацию и восстановлениеПоскольку содержимое журнала является критичным привосстановлении базы данных после сбоев, к ведению файлажурнала предъявляются особые требования по части надежностиВ частности, обычно стремятся поддерживать две идентичныекопии журнала на разных устройствах внешней памяти12.11.2009С.Д.

Кузнецов. Базы данных.126Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (36)Индексы (23) Служебная информация (1)Для корректной работы подсистемы управления данными вовнешней памяти необходимо поддерживать информацию,которая используется только этой подсистемой и не виднаподсистеме языкового уровняНабор структур служебной информации зависит от общейорганизации системы, но обычно требуется поддержаниеследующих служебных данных: Внутренние каталоги, описывающие физические свойстваобъектов базы данных, например,число атрибутов таблицы,их размер и, возможно, типы данных;описание индексов, определенных для данной таблицы и т.д.12.11.2009С.Д.

Кузнецов. Базы данных.127Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (37)Индексы (24) Служебная информация (2)Описатели свободной и занятой памяти встраницах данныхТакая информация требуется для нахождениясвободного места при занесении кортежаОтдельно приходится решать задачу поискасвободного места в случаях некластеризованных икластеризованных таблицoв последнем случае приходится дополнительноиспользовать кластеризованный индексКак уже отмечалось, нетривиальной являетсяпроблема освобождения страницы в условияхмультидоступа12.11.2009С.Д.

Кузнецов. Базы данных.128Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (38)Индексы (25) Служебная информация (3)Связывание страниц одной таблицыЕсли в одном файле внешней памяти могут располагатьсястраницы нескольких таблиц (обычно к этому стремятся),то нужно каким-то образом связать страницы однойтаблицыТривиальный способ использования прямых ссылокмежду страницами часто приводит к затруднениями присинхронизации транзакцийoнапример, особенно трудно освобождать и заводить новыестраницы таблицыПоэтому стараются использовать косвенное связываниестраниц с использованием служебных индексовВ частности, известен общий механизм для описаниясвободной памяти и связывания страниц на основе Bдеревьев12.11.2009С.Д.

Кузнецов. Базы данных.129Организация данных.

Характеристики

Список файлов лекций