Внутренняя организация реляционных БД

ОС делит вторичную память, как уже отмечалось, на блоки одинакового размера. Размер блока зависит от конкретного типа ОС и обычно находится в пределах от 512 до 4096 байт. Так, например, для DOS – это 512, для WindowsNT – 2048. Блок СУБД кратен блоку ОС. Его размер выбирается один раз при создании БД и, как правило, не может быть изменён в процессе её работы.

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

Если, например, четырёх байт достаточно, чтобы хранить адрес блока, а длина блока составляет 4096 байт, то корневой блок может содержать указатели максимум на 1024 блока. Таким образом, файл, состоящий максимум из 1024 блоков (т.е. примерно четырёх миллионов байт), можно представить одним корневым блоком и блоками, содержащими собственно файл. Файлы, состоящие максимум из блоков и содержащие байт, можно представить одним корневым блоком, указывающим на 1024 блока промежуточного уровня, каждый из которых, в свою очередь, указывает на 1024 блока-листа, содержащих определённую часть файла, и т. д.

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

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

Допустим, например, что имеется блок из 1000 целых чисел на диске, вращающемся со скоростью 1000 об/мин. Время, которое требуется для позиционирования считывающей головки над дорожкой, содержащей этот блок (так называемое время установки головок), плюс время, затрачиваемое на ожидание, пока требуемый блок сделает оборот и окажется под головкой (время ожидания), может в среднем составлять 100 миллисекунд. Процесс записи блока в определённое место во вторичной памяти занимает примерно столько же времени. Но за эти же 100 миллисекунд машина успевает выполнить 100 000 команд. Этого времени может быть более, чем достаточно, чтобы выполнить простую обработку (суммирование, нахождение среднего или быстрой сортировки) тысячи целых чисел, когда они находятся в основной памяти.

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

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