LOGO Основные методы организации БД Дисциплина: «Проектирование баз данных» Специальность: «Прикладная информатика (в экономике)» Институт информатики, инноваций и бизнес систем Кафедра информатики, инженерной и компьютерной графики Старший преподаватель Богданова О.Б.

Company Logo Основные дидактические единицы Физический доступ к базе данных. Физические средства хранения данных. Организация данных и способы адресации: последовательная организация файлов; индексно- последовательная организация файлов; прямая организация файлов; статические и динамические хэш- функции. Реализация логических отношений: связанные списки; инвертированные списки; В-деревья. Преобразование логической структуры реляционной базы данных в физическую структуру.

Company Logo Основные методы организации БД Существует определенная схема управления физическим доступом для организации представления данных на уровне интерфейса.

Company Logo Основные методы организации БД

Company Logo Интерфейс внешней записи Создан для отвлечения пользователя от изучения структуры файлов, связей между файлами и т.д. Интерфейс хранимых записей Представляет структуру хранения в виде файлов, каждый из кот. состоит из записей одного типа, и связей между файлами. Интерфейс физических записей Структура хранения файлов в соответствии с установленной файловой системой. Основные методы организации БД

Company Logo Основные методы организации данных на уровне интерфейса хранимых записей Предположим, что существует файл, упорядоченный по значению первичного ключа. Данный файл на уровне интерфейса физических записей будет представлен в соответствии с файловой структурой ОС. А на уровне интерфейса хранимых записей его организация может быть различной, т.е. СУБД будет видеть записи в базе в зависимости от варианта организации.

Company Logo STATUS Вл-к Москва Артем Москва CITY МеталснабS2 Завод ЭВМS4 ПримснабS5 ХимснабS3 ГлавснабS1 SNAMES# 1 вариант: Создание таблицы с первичным ключом. Файл SUPLIER

Company Logo Существует единственный хранимый файл, который содержит 5 записей по одной на каждого поставщика. Преимущества: простота и очевидность. Недостатки: 1) медленный поиск (кроме запроса «найти все сведения о поставщике»); 2) нет экономии памяти. 1 вариант: Создание таблицы с первичным ключом.

Company Logo 2 вариант: Факторизация (по полю CITY) STATUSCITY МеталснабS2 Завод ЭВМS4 ПримснабS5 ХимснабS3 ГлавснабS1 SNAMES# Вл-к Артем Москва CITY Файл CITY Файл SUPLIER

Company Logo В случае факторизации данные размещаются по 2-м файлам, причем с указателями из исходного на дополнительный. Это основной принцип организации справочника. Преимущества: экономия памяти в том случае, если количество записей в исходной файле (SUPLIER) велико, а в факторизованном файле (CITY) мало. Недостатки: с т.з. поиска данная структура не является достаточно оптимальной особенно для запросов «найти все сведения о поставщике» и «найти всех поставщиков в одном городе». 2 вариант: Факторизация (по полю CITY)

Company Logo 3 вариант: Индексирование по определенному полю Вл-к Артем Москва CITYSuplier STATUS МеталснабS2 Завод ЭВМS4 ПримснабS5 ХимснабS3 ГлавснабS1 SNAMES# Файл CITY Файл SUPLIER

Company Logo В данном случае указатели направлены из индексного файла в основной. Данный метод с точки зрения памяти аналогичен предыдущему, с точки зрения поиска он обеспечивает лучшие характеристики для запроса «найти всех поставщиков в одном городе» и худшее для запроса «все сведения о поставщике», «статус поставщика». Данный индексированный файл (CITY) можно считать плотным вторичным индексом, что означает: индекс таблицы CITY содержит отдельную запись для каждого экземпляра хранимой записи исходного файла (SUPLIER). 3 вариант: Индексирование по определенному полю

Company Logo Механизм индексирования Один из механизмов индексирования предполагает, что записи в исходном файле имеют ключи со значениями из натурального ряда и перед выполнением индексирования эти ключи упорядочены по возрастанию. Записи загружаются в файл, плотно заполняя блоки (без пробелов) и после чего система формирует строку в таблице младших индексов, ставя в соответствие блока и мах-ый ключ в этом блоке (такая таблица формируется на определенное кол-во блоков). После заполнения таблицы формируется строка в таблице старшего индекса, где ставится в соответствие таблицы младшего индекса и мах-го ключа.

Company Logo Москва S1 Главснаб S4 Завод Владивосток S5 Примснаб Артем S2 Металснаб S3 Химснаб вариант: Сочетание факторизации и индексирования

Company Logo 5 вариант: Использование цепочек указателей Владивосток АртемМосква S1 Главснаб S2 Металснаб S3 Химснаб S4 Завод S5 Примснаб

Company Logo 6 вариант: Иерархическая организация S1 Главснаб 30 S4 Завод 10 S2 Металлоснаб 20 S3 Химический 20 S4 Приморский 20 Москва Артем Вл-к В1 В2 В3 А С5 С1 С2 С3 С4 Блок 1 Блок 2 А1В1С1С2В2 С3С4В3С5

Company Logo 7 вариант: Инвертированная организация S5 S4 S3 S2 S1 Ук-ли Металснаб Завод ЭВМ Примснаб Химснаб Главснаб SNAME Индекс SNAME S1 S2 S3 S5 S4 Ук-ли SNAME Индекс STATUS

Company Logo S1 S4 S5 S2 S3 Ук-ли Вл-к Москва Артем SNAME Индекс CITY S2 S4 S5 S3 S1 S# Индекс SUPLIER 7 вариант: Инвертированная организация

Company Logo 8 вариант: Хеш - адресация S S S S S Адрес хранения записи = остаток от делания S#/13

Company Logo 8 вариант: Хеш - адресация 5 S 200 Металлоснаб 20 Артем 10 S 400 Завод 20 Москва 1 S 300 Химснаб 20 Артем 9 S 100 Приборснаб 20 Вл-к 6 S 500 Главснаб 30 Москва

Company Logo Вопросы по теме лекции 1. Что означает термин стратегический селектор? 2. Объясните назначение диспетчера файлов. 3. Сравните последовательную, индексно- последовательную и прямую организацию файлов. 4. Какие характеристики должны быть у хорошего алгоритма хэширования? 5. Для чего применяются указатели?

Company Logo Использование материалов презентации Использование данной презентации, может осуществляться только при условии соблюдения требований законов РФ об авторском праве и интеллектуальной собственности, а также с учетом требований настоящего Заявления. Презентация является собственностью авторов. Разрешается распечатывать копию любой части презентации для личного некоммерческого использования, однако не допускается распечатывать какую-либо часть презентации с любой иной целью или по каким-либо причинам вносить изменения в любую часть презентации. Использование любой части презентации в другом произведении, как в печатной, электронной, так и иной форме, а также использование любой части презентации в другой презентации посредством ссылки или иным образом допускается только после получения письменного согласия авторов.

LOGO Основные методы организации БД