Индексно-последовательный метод доступа

 

Основное назначение этого метода – поиск уникальных записей по значению ключа (2-й класс запросов). Однако, в отличие от других индексных методов, реализуется достаточно эффективно последовательный доступ (1-й класс запросов).

Все записи в основном файле упорядочены по возрастанию первичного ключа. Основной файл разбит на блоки фиксированной длины, содержащие целое количество записей. Для каждого блока формируется запись в индексном файле, содержащая значение ключа последней записи блока (так как упорядочены по возрастанию – наибольшее значение в блоке) и адрес начала блока. Индексный файл имеет аналогичную блочную структуру.

Поиск записи

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

Индексно-последовательная организация является эффективной по памяти (короткий индекс). Использование метода доступа ISAM для IBM 360-370 позволяет сделать эффективным поиск данных. Один блок – одна дорожка устройства, последовательность друг за другом идущих блоков – цилиндр устройства, то есть последовательный просмотр осуществляется без перемещения считывающих головок.

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

Дополнение записей

Определяется местоположение дополняемой записи в соответствии с возрастание первичного ключа. Если она не помещается в найденный блок, то последние записи, не поместившиеся в блок, перемещаются в область переполнения: отдельное пространство на диске. Там они не сортируются, а связываются в цепочку в соответствии с возрастанием первичного ключа: перемещенные записи становятся первыми в цепочке, соответствующей данному блоку. В данном случае используется стандартный прием в методах доступа – организация области переполнения. Кроме того, используется метод отведенного свободного пространства: в каждом блоке при первоначальной загрузке файла резервируется пустое пространство в конце блока (примерно 30 %). Такая процедура дополнения требует операций сопровождения основного файла: его периодическую перезагрузку.

 

Методы хеширования

 

Исходные данные для построения функции хеширования: интервал изменения ключа и приблизительное количество записей в основном файле. A=F(K), K – значение ключа, A – адрес записи. Основное требование к функции хеширования: квазиравномерное распределение значений величины A.

Определение. Два ключа K1 и K2 называются синонимами относительно функции хеширования F, если F(K1)=F(K2).

Второе требование к функции хеширования: как можно меньше синонимов.

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

Метод деления. Двоичный эквивалент ключа делится на число, равное количеству записей в файле, либо на число, близкое к этому количеству. Делитель должен быть при этом простым числом или числом, не содержащим мелких сомножителей (меньших 20). Остаток от деления является адресом записи.

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

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

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

Метод нелинейного поиска. В отличие от предыдущего метода адрес следующей просматриваемой записи вычисляется по формуле, аналогичной функции хеширования. Этот метод дает более равномерное распределение записей по файлу, однако требует хаотического обращения к файлу (неупорядоченное перемещение считывающих головок на диске). При открытой адресации этого нет.

 

Библиографический список

 

1. Мартин Дж. Организация баз данных в вычислительных системах. - М.: Мир, 1980. - 662 с.

2. Ульман Дж. Основы систем баз данных. - М.: Финансы и статистика, 1983. - 334 с.

3. Мейер Д. Теория реляционных баз данных. - М.: Мир, 1987. - 608 с.

4. Вейнеров О.М., Самохвалов Э.Н. Разработка САПР: В 10 кн. Кн. 4. Проектирование баз данных САПР. - М.: Высш. шк., 1990. - 144 с.

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

6. Солтон Дж. Динамические информационно-справочные системы. - М: Мир, 1979. - 557 с.

7. Тиори Т., Фрай Дж. Проектирование структур баз данных. - М.: Мир, 1985. Т 2. - 320 с.

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

9. Кузин А.В. Базы данных: Учебное пособие. – М.: Academia, 2005. – 320 с.

10. Советов Б.Я., Цехановский В.В., Чертовской В.Д. Базы данных: теория и практика. – М.: Высшая школа, 2005. – 463 с.

11. Мирошниченко Г.А. Реляционные базы данных. Практические приемы оптимальных решений. – СПб.: BHV, 2005. – 400 с.

12. Диго С.М. Базы данных: проектирование и использование. – М.: Финансы и статистика, 2005. – 592 с.

13. Кузнецов С.Д. Основы баз данных. - М.: Интуит.ру, 2005. - 488 с.

14. Уидом Д., Ульман Дж.Д. Основы реляционных баз данных. – М.: Лори, 2006. – 374 с.

15. Мальцев М.Г., Хомоненко А.Д., Цыганков В.М. Базы данных. Учебник для вузов. – М.: КОРОНА, 2006. – 736 с.

Содержание

1. Введение в предмет «Базы данных»............................................................... 3

1.1. Основные определения и категории БД.................................................... 3

1.2. Требования к БД и методы их реализации............................................... 4

1.3. Принципы функционирования СУБД....................................................... 6

1.4. Языковые средства для работы с БД........................................................ 7

2. Логическое описание и проектирование БД................................................... 8

2.1. Элементы данных и связи.......................................................................... 8

2.2. Древовидные модели данных.................................................................... 9

2.3. Сетевые модели данных........................................................................... 10

2.4. Реляционная модель данных................................................................... 11

2.5. Функциональные зависимости................................................................. 14

2.6. Вторая и третья нормальные формы...................................................... 14

2.7. Этапы построения схемы БД................................................................... 15

3. Физическая организация БД......................................................................... 16

3.1. Основы физической организации БД...................................................... 16

3.2. Индексно-последовательный метод доступа........................................... 17

3.3. Методы хеширования.............................................................................. 18

Библиографический список............................................................................... 19

 

 

Редактор Т.А. Жирнова

ИД № 06039 от 12.10.2001

Свод. темплан 2006 г.

Подписано в печать 07.06.2006. Формат 64×84 ¹/₁₆. Бумага офсетная.

Отпечатано на дубликаторе. Усл. печ. л. 1,25. Уч.-изд. л. 1,25.

Тираж. Заказ.

Издательство ОмГТУ. 644050, Омск, пр-т Мира, 11

Типография ОмГТУ