ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 1580
Скачиваний: 23
146
не
изменяется
во
все
время
существования
записи
.
Эти
записи
могут
просматриваться
с
помощью
диспетчера
файлов
.
При
выполнении
запроса
к
данным
,
СУБД
обращается
к
файловой
системе
,
которая
является
компонентом
операционной
системы
и
обеспечивает
доступ
к
соответствующим
записям
файлов
.
В
свою
очередь
,
с
точки
зрения
файловой
системы
хранимая
на
внешней
памяти
и
считываемая
в
оперативную
память
база
данных
выглядит
как
набор
страниц
данных
.
Дело
в
том
,
что
современные
запоминающие
устройства
устроены
таким
образом
,
что
минимальной
«
порцией
»
данных
,
в
операции
ввода
/
вывода
,
является
страница
,
содержащая
определенное
фиксированное
число
записей
.
Обычно
каждый
картеж
хранится
во
внешней
памяти
целиком
на
одной
странице
.
Отсюда
возникает
,
кстати
,
ограничение
в
СУБД
на
максимальную
длину
кортежа
.
Как
правило
,
также
в
одной
странице
хранят
кортежи
одного
отношения
,
хотя
возможны
решения
,
когда
в
одной
странице
размещают
кортежи
разных
логически
связанных
отношений
(
см
.
ниже
про
кластеризацию
данных
).
Реально
страницы
данных
могут
размещаться
на
дисках
или
дублироваться
(
кэшироваться
)
в
оперативной
памяти
.
Диспетчер
файлов
определяет
страницу
,
на
которой
находится
искомая
запись
,
и
формирует
запрос
для
доступа
к
соответствующей
странице
хранимых
данных
к
подсистеме
диспетчера
дисков
.
Диспетчер
дисков
осуществляет
все
дисковые
операции
ввода
/
вывода
.
Он
работает
непосредственно
с
хранимыми
на
дисках
данными
–
определяет
физическое
расположение
искомой
страницы
на
дисковом
носителе
(
цилиндры
,
дорожки
,
секторы
)
и
обеспечивает
соответствующее
управление
аппаратными
средствами
для
реализации
процесса
ввода
/
вывода
данных
конкретной
страницы
.
В
этой
многоступенчатой
процедуре
доступа
к
хранимым
данным
наиболее
медленными
являются
операции
по
непосредственному
чтению
/
записи
данных
на
физическом
носителе
,
так
как
они
связаны
с
механическими
операциями
позиционирования
головок
чтения
/
записи
на
соответствующие
цилиндры
,
дорожки
и
секторы
дисковой
подсистемы
.
При
реальной
работе
информационных
систем
с
базами
данных
в
запросах
к
данным
обычно
фигурируют
не
одна
,
а
множество
записей
данных
.
Поэтому
существенное
влияние
на
время
доступа
к
такому
множеству
данных
оказывает
близость
их
взаимного
расположения
на
физическом
носителе
,
их
размещение
в
одной
или
разных
физических
страницах
,
так
как
от
этого
существенно
зависит
время
,
затрачиваемое
дисковой
подсистемой
на
изменение
позиционирования
головок
при
переходе
от
одной
записи
к
другой
.
В
связи
со
сказанным
,
следует
упомянуть
один
из
используемых
в
промышленных
СУБД
методов
повышения
скорости
доступа
к
хранимым
данным
,
известный
как
кластеризация
данных
.
Идея
кластеризации
данных
состоит
в
том
,
чтобы
хранить
логически
связанные
записи
базы
данных
на
147
физическом
носителе
таким
образом
,
чтобы
минимизировать
время
,
требуемое
для
перемещения
головок
чтения
/
записи
при
переходе
от
одной
записи
к
другой
.
При
этом
может
рассматриваться
как
внутрифайловая
кластеризация
,
когда
речь
идет
о
записях
одной
реляционной
таблицы
базы
данных
,
и
межфайловая
кластеризация
,
когда
в
непосредственной
близости
на
одной
странице
размещаются
,
например
,
записи
нескольких
таблиц
,
связанных
с
помощью
внешних
ключей
.
11.2.
Индексирование
Очевидно
,
что
физическое
размещение
записей
базы
данных
в
соответствие
с
их
логической
взаимосвязью
с
целью
минимизации
времени
доступа
к
данным
на
практике
далеко
не
всегда
осуществимо
.
В
особенности
,
когда
речь
идет
о
данных
,
динамически
изменяющихся
во
времени
.
Кроме
того
,
при
поиске
данных
по
каким
-
либо
условиям
,
касающихся
значений
атрибутов
,
требования
к
оптимальному
размещению
записей
таблицы
для
разных
атрибутов
могут
оказаться
(
и
,
как
правило
,
оказываются
)
противоречивыми
.
Например
,
нельзя
упорядочить
записи
таблицы
в
алфавитном
порядке
одновременно
по
двум
и
более
атрибутам
.
Эффективным
методом
повышения
скорости
доступа
к
данным
без
использования
их
физического
упорядочивания
и
близкого
размещения
на
дисковом
носителе
является
индексирование
.
Рассмотрим
в
качестве
примера
таблицу
с
данными
о
студентах
и
запрос
о
выборе
всех
студентов
из
некоторого
города
N
.
Если
не
использовать
никаких
специальных
ухищрений
,
и
если
записи
отношения
не
упорядочены
в
соответствии
с
алфавитным
порядком
значений
поля
Город
,
то
для
решения
данной
задачи
должны
быть
последовательно
просмотрены
все
записи
таблицы
и
из
них
отобраны
те
,
у
которых
значения
атрибута
Город
равны
заданному
в
условии
выборки
значению
«
N
».
При
этом
,
реальное
количество
отобранных
записей
может
быть
существенно
меньше
общего
числа
просмотренных
при
выполнении
запроса
записей
.
Выполнение
описанной
задачи
может
быть
значительно
ускорено
,
если
создать
,
как
это
показано
на
рис
дополнительную
структуру
данных
,
так
называемый
индексный
файл
городов
,
или
просто
индекс
(
index
–
указатель
).
В
этом
файле
представлены
все
значения
поля
Город
файла
,
соответствующего
таблице
Студент
,
но
уже
физически
упорядоченные
по
алфавиту
,
с
указателями
на
соответствующие
записи
файла
таблицы
Студент
.
Поиск
нужного
города
в
индексном
файле
может
быть
осуществлен
существенно
быстрее
,
чем
в
исходной
таблице
.
Во
-
первых
,
из
-
за
упорядоченного
по
148
алфавиту
расположения
наименований
городов
,
благодаря
чему
не
нужно
просматривать
все
до
одной
записи
файла
.
Во
-
вторых
,
физические
размеры
индексного
файла
существенно
меньше
файла
таблицы
Студент
,
для
его
размещения
требуется
меньше
физических
страниц
и
чтение
его
записи
с
диска
будет
происходить
существенно
быстрее
.
Индексы
,
приведенные
на
рис
иногда
называют
инвертированными
списками
.
Если
обычный
файл
отношения
это
список
указателей
кортежа
со
значениями
соответствующих
полей
,
то
индексный
файл
представляет
собой
список
упорядоченных
значений
атрибута
с
указателями
соответствующих
записей
-
кортежей
.
Воронеж
Воронеж
Воронеж
Воронеж
Москва
Москва
Москва
Москва
Липецк
Липецк
Иванов
Петров
Сидоров
Кузнецов
Попов
...
..
С
1
С
2
С
3
С
4
С
5
Город
RowID
Код
_
студ
Имя
_
студ
Город
Индексный
файл
городов
Файл
данных
отношения
СТУДЕНТ
Рис
Использование
индексирования
для
ускорения
доступа
к
записям
отношения
студент
Для
одного
файла
,
представляющего
отношение
базы
данных
,
могут
формироваться
одновременно
несколько
индексных
файлов
для
разных
его
полей
.
Например
,
для
приведенного
выше
на
рис
файла
отношения
студент
могут
быть
сформированы
индексные
файлы
для
полей
Код
-
студ
и
Имя
-
студ
.
Более
того
,
может
быть
сформирован
индексный
файл
по
составному
атрибуту
,
то
есть
по
комбинации
полей
.
Комбинированный
индекс
по
полю
Город
и
полю
Имя
-
студ
будет
представлять
собой
список
пар
значений
этих
атрибутов
,
упорядоченный
по
значениям
городов
,
а
при
одинаковых
значениях
поля
Город
упорядоченный
по
именам
студентов
.
149
11.3.
Использование
при
индексировании
структур
типа
В
-
деревьев
Недостатком
рассмотренной
выше
и
представленной
на
рис
структуры
индекса
является
то
,
что
эффективность
такого
индекса
будет
падать
с
ростом
числа
записей
индексируемого
файла
.
В
частности
из
-
за
того
,
что
размер
индексного
файла
также
будет
увеличиваться
и
,
в
конце
концов
,
занимать
не
одну
,
а
большее
число
страниц
.
В
связи
с
этим
в
настоящее
время
для
построения
индексных
файлов
используется
более
сложная
,
но
более
эффективная
иерархическая
структура
типа
В
-
дерева
(
В
-
tree
) («
B
»
от
англ
.
Binary
).
Причиной
использования
для
индексирования
иерархических
структур
типа
В
-
дерева
заключается
в
желании
избежать
при
поиске
обязательного
просмотра
всех
страниц
индексного
файла
согласно
его
физической
структуры
.
Этого
можно
достичь
,
если
создать
индекс
следующего
уровня
уже
для
самого
индексного
файла
.
Учитывая
,
что
в
индексном
файле
список
значений
физически
упорядочен
,
т
.
е
.
следующие
последовательно
значения
сгруппированы
по
страницам
,
в
индексном
файле
следующего
уровня
нет
необходимости
ссылаться
на
каждую
запись
индекса
нижнего
уровня
.
Достаточно
организовать
ссылки
на
соответствующие
страницы
индекса
нижнего
уровня
.
Как
мы
знаем
,
страницы
данных
всегда
считываются
с
диска
в
оперативную
память
целиком
и
,
хотя
в
оперативной
памяти
нам
все
равно
придется
последовательно
просматривать
записи
считанной
страницы
,
это
будет
происходить
гораздо
быстрее
,
чем
при
поиске
нужных
записей
на
диске
.
Очевидно
,
что
индекс
следующего
уровня
будет
содержать
гораздо
меньше
записей
,
чем
индекс
первого
уровня
,
что
также
способствует
ускорению
поиска
.
Вследствие
этого
,
такой
индекс
называют
неплотным
индексом
,
в
отличие
от
плотного
,
у
которого
число
записей
равно
числу
записей
индексируемого
файла
.
Рассмотренная
идея
может
быть
развита
дальше
в
направлении
создания
многоуровневой
древовидной
индексной
структуры
.
Пример
такой
структуры
,
называемой
В
-
деревом
,
приведен
на
рис
C
точки
зрения
внешнего
логического
представления
В
-
дерево
–
это
сбалансированное
сильно
ветвистое
дерево
во
внешней
памяти
.
Сбалансированность
означает
,
что
длина
пути
от
корня
дерева
к
любому
его
листу
одна
и
та
же
.
Ветвистость
дерева
–
это
свойство
каждого
узла
дерева
ссылаться
на
большое
число
узлов
-
потомков
.
Физическая
организация
В
-
дерева
представляется
как
мультисписочная
структура
страниц
внешней
памяти
,
т
.
е
.
каждому
узлу
дерева
соответствует
страница
внешней
памяти
.
Индекс
,
построенный
на
основе
В
-
дерева
,
состоит
из
двух
частей
.
Первая
–
это
набор
страниц
с
последовательностями
значений
(
ключей
)
с
150
указателями
на
записи
индексируемого
файла
с
реальными
данными
(
нижний
ряд
на
рис
.13.3).
И
вторая
,
набор
неплотных
индексов
,
обеспечивающих
быстрый
доступ
к
страницам
набора
последовательностей
.
Комбинация
набора
последовательностей
и
набора
индексов
называется
В
-
плюс
-
деревом
или
В
+
-
деревом
.
На
самом
верхнем
уровне
В
+
-
дерева
находится
единственный
элемент
,
так
называемая
корневая
(
root
)
страница
,
а
на
самом
нижнем
уровне
дерева
набор
последовательностей
с
указанием
на
записи
индексируемого
файла
,
которые
являются
«
листьями
»
дерева
.