МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ЭЛЕКТРОНИКИ И МАТЕМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) КАФЕДРА ИКТ Дипломный проект на тему: Студент: Руководитель проекта: 1 Лекция 6. Организация данных в файлах Курс: Базы Данных

2 Повестка дня Для чего нужны файлы? Хеширование Индексирование

3 Чтение файла Состоит из записей Считывается блоками (страницами, сегментами) Стандартный размер блока: 4096 байт.

4 Файл: взгляд изнутри Неупорядоченные (куча) Метод доступа: линейный поиск Упорядоченные Метод доступа: бинарный поиск Хешированные Метод доступа: …

5 Бинарный поиск Файл занимает из N страниц Страница... Страница N Страница... Страница 2Страница 1 (1) (2)(3)

6 Хеширование (осн. термины, 1) Hash: что-либо мелко порубленное, нарезанное, покрошенное (Lingvo.ru) Хеш-функция Поле хеширования Хеш-ключ (хеш-код, дайджест сообщения) Методы образования: Свертка

7 Хеширование (методы образования) Свертка o Пример свертки: X * 34 X * Получение остатка от деления

8 Хеширование (осн. термины, 2) Страница (сегмент) Ячейка (слот) Конфликт (коллизия) Синонимы

9 Методы хеширования Открытая адресация Несвязанная область переполнения Связанная область переполнения Многократное хеширование

10 Хеширование. Открытая адресация Результат хеш-ф.Адрес страницы р1а1 р2а2 Адрес страницы а1 а2 Содержимое Запись 1 Запись 2 Запись 3 а3Запись 4 р3а3

11 Хеширование. Несвязанная область переполнения Результат хеш-ф.Адрес страницы р1а1 р2а2 Адрес страницы а1 а2 Содержимое Запись 1 Запись 2 Запись 3 а3Запись 4 р3а3 Номер страницы с1 с2 Содержимое Запись 7 Запись 8 Запись 14 с3Запись 144

12 Хеширование. Связанная область переполнения Результат хеш-ф.Адрес страницы р1а1 р2а2 Адрес страницы а1 а2 Содержимое Запись 1 Запись 2 Запись 3 а3Запись 4 р3а3 Адрес страницы адр.син_1 адр.син_2 Содержимое Запись 7 Запись 8 Запись 14 адр.син_3Запись 144 Адреса синонимов Адреса синонимов

13 Динамическое хеширование. Запись о сотруднике SL21 Запись о сотруднике SG37 Запись о сотруднике SL21 Запись о сотруднике SG14 Запись о сотруднике SG37 Запись о сотруднике SA9 Запись о сотруднике SG14 Запись о сотруднике SL Глубина Локальная глубина Каталог Сегмент Запись о сотруднике SG37

14 Динамическое хеширование.

15 Недостатки хеширования 1) Подумайте! 2) Придумайте!

Работники цехов предприятия получают со скидкой спецодежду (халаты, тапочки, комбинезоны и др.) для выполнения производственных функций. Процент скидки зависит от занимаемой должности и может составлять от 30 до 50 % стоимости единицы вида спецодежды. Спецодежда имеет разный срок носки, по истечении которого она подлежит замене. Ежедневно кладовщик цеха ведет учет выдачи спецодежды. Необходимо спроектировать базу данных СПЕЦОДЕЖДА, информация которой будет использоваться для получения оперативных сведений о наличии спецодежды у работников; формирования списка работников, нуждающихся в замене спецодежды; планирования закупок спецодежды и др. В БД должна храниться информация: о СПЕЦОДЕЖДЕ: код спецодежды, вид спецодежды, срок носки, стоимость единицы (руб.); ЦЕХАХ, работники которых пользуются различными видами спецодежды: код цеха, наименование цеха, Ф.И.О. начальника цеха; РАБОТНИКАХ: код работника, Ф.И.О. работника, должность, скидка на спецодежду (%); ПОЛУЧЕНИИ: код работника, код спецодежды, дата получения, роспись. При проектировании БД необходимо учитывать следующее: в цеху работают несколько работников. Работник работает только в одном цеху; работник цеха участвует в получении нескольких видов спецодежды. Каждое получение имеет отношение только к одному работнику; один и тот же вид спецодежды поступает несколько раз для получения. Каждое получение относится к одному виду спецодежды. Кроме того следует учесть: каждый работник обязательно работает в цеху. В каждом цехе обязательно работают работники; работники некоторых должностей не обязательно участвуют в получении спецодежды. В каждом получении обязательно участвует работник; каждый вид спецодежды обязательно поступает для получения. Каждое получение обязательно относится к некоторому виду спецодежду.