Реферат на тему:


Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск






Загрузка...
Физическая организация баз данных

Физическая организация баз данных

План

1. Организация хранения информации.

2. Индексация

3. Хеширования

4. B-дерева

Организация хранения информации

Физическая организация данных отвечает за их хранение, управление, формы представления и структуры данных.

Физическое проектирование представляет собой процесс определения характеристик хранилища данных и доступа к ним в БД. Свойства хранилища данных зависят от устройств хранения, средств доступа к данным, поддерживаемых системой и от СУБД. На этапе физического проектирования определяется местонахождение данных на устройствах хранения, общая производительность системы.

В реляционных БД сложные физические процессы организации данных скрыты от пользователя, но они имеют большое влияние на производительность работы с БД.

Процесс поиска и представления данных пользователю выполняется в несколько этапов (рис. 8.1).

Сначала определяется необходимая запись, для нахождения которого вызывается диспетчер файлов. Диспетчер файлов определяет страницу, на которой находится запись, и для ее получения вызывает диспетчер дисков. Диспетчер дисков определяет физическое положение необходимой страницы на диске и передает ее диспетчеру файлов, а тот - СУБД. Главными

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

Для организации хранения данных применяется технология кластеризации - физически близкое расположение записей в пространстве памяти среды хранения БД.

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

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

Индексация

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

В зависимости от организации индексной и основной области различают два типа файлов: с плотным индексом и с разреженным индексом. Плотный индекс содержит индексные записи для всех значений ключа поиска в данном файле. Разреженный индекс содержит индексные записи только для некоторых значений ключа поиска в данном файле.

В файлах с плотным индексом основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи выглядит так: (значение ключа, номер записи).

В индексных файлах с плотным индексом для каждой записи в основной области существует одна запись с индексной области. Все записи в индексной области упорядочены по значению ключа. Файлы с плотным индексом называются индексно- прямыми файлами.

В файлах с разреженным индексом основная область содержит последовательность записей одинаковой длины, которые расположены в упорядоченном порядке, а структура индексной записи выглядит так: (значение ключа первой записи блока, номер блока с этой записью).

Разреженное индекс строится для порядкеванных файлов. Файлы с разреженным индексом называются индексно- последовательными файлами.

Индексы целесообразно создавать по столбцу или группе столбцов в следующих случаях:

- часто выполняется поиск в БД атрибутами, которые перечислены в условии WHERE оператора SELECT;

- часто выполняется объединение таблиц с определенными атрибутами;

- часто выполняется сортировка таблиц (использование ORDER BY в операторе SELECT).

Индексы нецелесообразно создавать по столбцу или группе столбцов в следующих случаях:

- редко используются для поиска;

- содержат значения, которые часто меняются, что приводит к частому обновлению индекса и, соответственно, замедляет работу;

- содержат незначительное количество значений.

Как правило в БД определяют два вида индексов:

- индексы, которые используются запросами для доступа к данным;

- индексы, которые обеспечивают посылочную целостность между таблицами.

Большая часть БД поддерживает B-дерева, кроме того некоторые из них работают с хэш-таблицами. Некоторые системы представляют многомерные структуры данных, такие, как варианты R-деревьев и квадрадерев (kd-дерева). Отдельные системы поддерживают также битные векторы и многотабличных индексы соединения. Системы, располагаются в оперативной памяти, кроме того поддерживают структуры данных, которые имеют небольшие коэффициенты ветвления, такие как T-дерева, бинарные деревья.

хеширование

хеширование - технология прямого доступа к записям БД по известным значениям их ключей. Время доступа существенно не зависит от количества записей, сохраняются. Суть метода хеширования заключается в том, что по значениям ключа k, или его определенных характеристик, исчисляется некоторая хэш-фукция h (k) и полученное значение берется в качестве адреса начала поиска. Недостатком большинства хэш-функций является то, что они не гарантируют получения уникального адреса, поскольку количество возможных значений поля хеширования может быть значительно больше числа адресов, которые доступны для записи. Ситуация, когда резним значением ключей соответствует одно значение хеш-функции называется коллизией. Значения ключей, которые имеют одну и ту же хэш-функцию называются синонимами. Для решения коллизий применяют специальные методы: последовательного перебора, введение области переполнения, многократное хеширования. Хеш структура показана на рис.8.3.

Хэш-структуры могут обеспечить ответ на вопрос к БД за одно обращение к диску при условии отсутствия синонимов. Хеш-структуры имеют низкую эффективность при запросах на определение диапазонов, нахождение экстремумов и некоторых других.

B-дерева

Во многих СУБД для сохранения индексов используется структура данных, которая называется деревом. Среди деревьев наиболее распространены бинарные деревья, B-дерева и их разновидности (В + -дерева, B -дерева и т.д.). B-дерево является сбалансированным, упорядоченным по значению ключа деревом. Наиболее распространенными среди B-деревьев является B + ^ эрев.

Пример. На рис. 8.4 приведен фрагмент B + -дерева и его связь с БД.

Инвертированные файлы

Для обеспечения быстрого доступа по вторичным ключами используются структуры, называемые инвертированными спискам. Инвертированный список представляет собой двухуровневую индексную структуру. На первом уровне находится файл или часть файла, в который упорядоченно расположены значение вторичных ключей. Каждая запись с вторичным ключом имеет указатель на номер первого блока в цепи блоков, содержащих номера записей с данным значением вторичного ключа. На втором уровне находится цепь блоков, содержащих номера записей, содержащих одно и то же значение вторичного ключа. При этом блоки второго уровня упорядочены по значению вторичного ключа. На третьем уровне находится непосредственно файл данных. Поиск данных выполняется в следующей последовательности:

- на первом уровне находится значение вторичного ключа;

- по найденным указателем читается блок второго уровня, содержащий номера всех записей с заданным значением вторичного ключа;

- врабочую область загружается содержание всех записей с заданным значением вторичного ключа.

Литература

1. Гайдамакин Н.А. Автоматизированные информационные системы, базы и банки данных. Вводный курс. - М .: Гелиос АРВ, 2002. - 368 с.

2. Гайна А. Организация баз данных и знаний. Языка баз данных Конспект лекций.-К.: КНУСА, 2002. - 64 с.

3. Гайна Г.А., Попович Н.Л. Организация баз данных и знаний. Организация реляционных баз данных: Конспект лекций. - М.: КНУБА, 2000. - 76 с.

4. Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. М .: Издательский дом "Вильямс", 2003. - 1088 с.

5. Григорьев Ю.А., Ревунков Г.И. Банки данных. М .: Изд-во МГТУ им. Н.Э.Баумана, 2002. - 320 с.

6. Грофф Дж. Вайнберг П. Энциклопедия SQL. - СПб .: Питер, 2003. - 896 с.

7. Дейт К.Дж. Введение в системы баз данных. - М .: Диалектика, 1998. - 784 с.

8. Дыгой С.М. Проектирование и внедрение баз данных. М .: Финансы и статистика, 1995. - 208 с.

9. Карпова Т.С. Базы данных: модели, разработка, реализация. - СПб .: Питер, 2001. - 304 с.

10. Когаловский М.Р. Энциклопедия технологий баз данных.- М .: Финансы и статистика, 2002. - 800 с.

11. Конноли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. - М .: Издательский дом "Вильямс", 2003. - 1440 с.

12. Кренке Д. Теория и практика построения баз данных. - СПб .: Питер, 2003. - 800 с.

13. Малыхина М.П. Базы данных: основы, проектирование, внедрение. - СПб .: БХВ-Петербург, 2004. - 512 с.

14. Роб П., Коронел К. Системы баз данных: проектирование, реализация и управление. - СПб .: БХВ-Петербург, 2004. - 1040 с.

Загрузка...