Системы управления базами данных. Лекция 12

1. СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ лекция 12, 2021/2022 учебный год

Гранков М.В.
Моб. +7 919 887 20 96 (БиЛайн)
E-mail: [email protected]
1

2. Схема организации хешированного файла.

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

3. Структура блока хешированного файла

• В каждом блоке предусмотрено место для размещения
фиксированного числа записей. Если запись требует r байт, то для
чтения, например, пятой записи внутри блока требуется сделать
смещение 4r байт, от первого байта, следующего за заголовком
блока.
• Пространство, используемое для хранения одной записи, будем
называть субблоком.
• Во «время жизни» файла может оказаться, что некоторый
субблок свободен (запись из него была удалена) в то время, как
следующие за ним субблоки заняты. Для того, чтобы как-то
различать записанные и свободные субблоки возможны два
метода:
• в освобождаемый субблок помещают последовательность бит,
которая никогда не может появиться в записи;
• в блоке отводят 1 бит на каждый субблок. Его нулевое значение
3
– субблок свободен, 1– субблок занят.

4. Структура блока хешированного файла

• Иногда отводят ещё один бит (в заголовке или в записи)
который показывает, была ли удалена запись. Это позволяет
избежать повторное использование субблоков, на которые была
ссылка в случае закреплённых записей.
4

5. Организация поиска в хешированном файле

Задача: найти запись с ключом v. (v– одно поле или
список полей в фиксированном порядке – тогда v
конкатенация полей).
Вычислим h(v) получая номер участка i. Прочтём
справочник участков и найдем адрес первого блока
участка i. Читаем первый блок, анализируем субблоки
на совпадение ключа. Если найдено – поиск успешен –
конец. Если нет – читаем следующий блок данного
участка. Если его нет – поиск закончен неуспешно.
5

6. Модификация в хешированном файле

Задача: изменить одно или несколько полей записи с
ключом v.
1.Найти запись с ключом v. Если не найдена –
аварийный останов.
2.Найдена запись:
• среди модифицированных полей, есть хотя бы одно,
которое входит в ключ: необходимо удалить найденную
запись из базы и затем добавить измененную;
• среди модифицированных полей нет ни одной,
входящей в ключ: необходимо изменить запись в ОП и
записать модифицированный блок по месту (туда же).
6

7. Включение в хешированном файле

Задача: добавить запись с ключом v.
1. Найти запись с ключом v (вычисляется номер
участка, куда надо добавить запись). Если запись
найдена, аварийный останов. Иначе:
2. Найдем первый свободный субблок среди блоков
участка h(v) (этот субблок может быть в середине, если
ранее было удаление с освобождением субблока, т.е.
записи не закреплены). Адрес этого субблока можно
запомнить при поиске ключа v. Помещаем запись в
данный субблок (записываем блок на место). Если
свободного места нет, то получаем свободный блок из
OС. Организуем цепочку с последним блоком участка
h(v), затем пишем блок на диск
7

8. Удаление в хешированном файле

Задача: удаление записи с ключом v.
1. Найти запись с ключом v. Если запись не найдена, то
аварийный останов. Иначе:
2. Если запись найдена, то:
• если записи не закреплены →бит свободен/занят
перевести в состояние свободен (при
следующем
добавлении этот субблок будет использован);
• если записи закреплены, тогда бит свободен/занят не
изменяеть, а бит удалён установить в состояние 1–
удалён.
Если записи не закреплены, то для удаления
возможно
использовать
следующий
алгоритм:
последнюю запись файла переписать на место
8
удаленной, а последний субблок освободить.

9. Проблема реорганизации. Анализ временных характеристик хеширования

Для каждой операции поиска, модификации, включения,
удаления требуется: одно обращение для чтения справочника
участков (если весь справочник не помещается в память) + число
доступов, которое не превышает число блоков в данном участке.
При поиске в среднем просматривается половина блоков участка.
Для всех операций, кроме поиска, требуется ещё записать блок во
внешнюю память.
Если каждый участок состоит ровно из одного блока (т.е.
лучший случай) для поиска требуется 2 обращения. Для
остальных доступов – 3 обращения. В каждом участке имеется не
менее одного блока. Чтобы среднее число блоков в участках в
превышало единицу, необходимо, чтобы число участков было бы
примерно равно числу записей в файле, деленному на число
записей в блоке.
9

10. Проблема реорганизации. Анализ временных характеристик хеширования

Для повышения скорости доступа, при росте числа блоков в
участках, потребуется реорганизация файла. Её достаточно
просто провести, если ввести два ограничения:
1. При вычислении функции хеширования от ключа v получают
большое число, гораздо большее, чем число участков.
Полученное число делят на число участков, остаток от деления –
номер участка.
2. При реорганизации число участков n умножают на некоторое
фиксированное с (обычно с = 2).
Если мы удвоим число участков, то все записи участка i будут
попадать в участки i или i+n. И в эти участки не попадут никакие
записи других участков.
10

11. Проблема реорганизации. Анализ временных характеристик хеширования

Пусть по ключу v построим N=h(v) и N >>n– числа участков
(если мы удвоим n, то получим N >>2n), разделим N на n и
получим:
(1.)
N
i
k ; где: k–целое, i–остаток от деления, 0 ≤i ≤n-1 -номер
n
n
участка. Из формулы (1) получим :
(2.) N n k i ;
Удвоив число участков, получим:
N
j
= m+ .
(3.)
Обе части формулы (1) разделим на два и
2* n
2* n
прировняем с (3), получим (4):
k
i
j
=
m+
(4.)
2 2n
2n
11

12. Индексированные файлы

Решается та же задача: поиск записи по ключу v.
Допустим, что записи в файле отсортированы по значениям
этого ключа (обратить внимание на сортировку дат dtos() и строк
– лексикографическая сортировка). Для нескольких полей:
сортировка по первому ключу, при равных первых – сортировка
по второму и т.д.
В этом случае (файл отсортирован) для поиска можно
использовать идею поиска в телефонной книге (словаре). Вместо
просмотра всех записей будем анализировать только первую
запись на каждой странице. Если искомый ключ превышает ключ
этой записи, то возможно, что искомая запись находится на
предыдущей странице. Если даже для последней страницы
искомый ключ меньше, чем первый на этой странице, то следует
проанализировать записи этой последней страницы.
12

13. Индексированные файлы

Аналогично организован доступ к файлу. Пусть мы имеем
отсортированный файл с информацией, назовем его главным
файлом. Создадим для главного файла второй файл– так
называемый разреженный индекс, состоящий из пар
(значение_ключа, адрес_блока).
Пара (v,b) появляется в файле индекса, если первая запись в
блоке главного файла с адресом b имеет значение ключа v. Записи
файла индекса подобно обыкновенному (информационному)
файлу с двумя полями: ключ и номер блока. Записи файла индекса
отсортированы по значению ключа и не являются закрепленными,
т.к. нигде в другом файле нет ссылки, ни на какую запись файла
индекса. Вероятно, что с файлом индекса, как и с обычным
(информационным) файлом следует выполнить операции
включения, модификации, удаления.
13

14. Индексированные файлы

Кроме того, необходима новая функция (вместо поиска): для
данного ключа v1, найти такую запись ((v2 ,b2)| (v2 ≤ v1)
((следующая (v3,b3) | (v3 >v1) (v2,b2) –последняя в файле)))
• В этом случае говорят, что v2 покрывает v1 (это значит, что если
запись с ключом v1, содержится в файле, то она может
содержаться только в блоке b2, у которого первая запись имеет
ключ v2).
14

15. Индексированные файлы. Поиск в индексе.

Требуется найти запись в основном файле с ключом v1.
Задача (для файла индекса): найти в файле индекса запись
(v2,b2) такую, что v2 покрывает ключ v1.
Решение: в простом случае (мало записей в индексе) –
линейный поиск (условия применения – весь индекс в основной
памяти).
Но и в этом случае имеется выигрыш, т.к. если в блоке
основного файла можно записать k записей и известно. что одна
запись в индексе организуется на один блок основного файла, то в
файле индекса в k раз меньше записей. Кроме того, обычно
записи индекса короче, чем записи основного файла и в один блок
индекса помещается больше записей (появляется вероятность
размещение всего индекса в оперативной памяти).
15

16. Индексированные файлы. Поиск в индексе.

Лучшая стратегия поиска в файле индекса – использование
двоичного поиска. При данной стратегии на каждом шаге
количество блоков (при поиске записи (v2,b2) – покрывающих
ключ v1) индекса, содержащих запись (v2,b2), сокращается вдвое.
Таким образом, если в индексе n блоков, то не боле чем за
log2(n+1) чтений будет прочитан блок индекса, содержащий
запись (v2,b2). В практике часто вместо оценки log2(n+1)
используют оценку log2n. С учетом доступов к основному файлу
общее число доступов – 3+ log2n (3 складывается из одного
чтения справочника индекса, одного чтения блока файла и одной
записи блока файла на диск).
16

17. Индексированные файлы. Поиск в индексе.

• Пример: Пусть в главном файле есть 106 записей. В блоке
помещается 10 записей, следовательно, всего в файле 105 блоков.
Пусть в один блок индекса помещается 100 записей, значит для
индекса необходимо 1000 блоков. Таким образом, для доступа и
перезаписи блока основного файла требуется 3+log21000 13
обращений (log21024 log2210 = 10, т.к. log21024 log21000 10).
• При исследовании хешированного файла (и условии – каждый
участок состоит из одного блока) необходимо 3 доступа. Для
индекса имеется дополнительное преимущество, состоящее в
возможности поддерживать отсортированный порядок в файле
(как минимум логическую упорядоченность).
17

18. Индексированные файлы. Поиск в индексе.

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