Представление структур данных в памяти ЭВМ. Физическое представление данных

Современные СУБД облд-т высоким быстродействием поиска инф в БД. Это быстродействие реализ за счет 2х методов

– 1.Использование SQL для запросов. Это реляционный язык, кот использует элементы реляц алгебры и реляц исчисления кортежей. В реляционной системе запросов сущ возм-ть выбора эффективности стратегии д/вычисл реляцион выражения. Этот процесс выполняет оптимизатор. Он позволяет сократить кол-во операций, кот необходимы для выполнения запросов.

- 2. Работа с совр структурами таблиц.

Можно выделить логическую структуру данных и физическое представление данных. Для представл дан-х на физиче-м уровне сущ 2 метода-

1 метод – любому элементу данных указ-ся адрес памяти. Размещение данных и их выборка производятся по известному адресу.

2 метод. – содержимое ключа конкретн записи преобра-ся опред метод в адрес памяти вычисл системы. Размещение данных и их выборка производ по знач-ю ключа, т.е. опре-ся содержимым самих данных.

1 метод представления данных. Линейный список с последовательным распределением памяти и с связанным распределением памяти.

Пусть есть опред тип записи с набором экземпляров записи. Будем считать, что запись из Эл-в данных хранится целиком и раздел-ся на атрибуты или элементы данных после выборки записи.

Линейный список – мин упорядоч записи, когда номера записей следуют одна за другой.

N количество записей в списке; m размер записи в байтах; β – адрес базы (указывает начало вектора дан-ных в памяти); i – текущая запись в списке; αi – адрес фи-зической памяти.

Преимущества: высокое быстродействие поиска и раз-мещения записей (используется адресная функция или алгоритм).

Недостатки: при изменении размера записи необходимо перезаписывать весь линейный список; Введение дополнительных записей может привести к перезаписи линейных списков.

Связанное распределение памяти

При связ распределении памяти Эл-ты списка имеют указатели на адрес хранения хранения след элемента. Связ распред в памяти – это более сложный и гибкий способ хранения лин списка.

N =10⁶ – кол-во узлов. При связ распределении значение узла списка м/получить только путем просмотра указателей, хранящихся в записи. Связанный список позволяет модифицировать стру-ру списка, т.е. вставки и удаление производ просто.

При объединении этих 2-х типов списков получили ин-дексные файлы (связанный линейный список с исполь-зованием индексов).

Имеется список из N элементов; в каждый вводится по 2 дополнительных поля для указания адреса следующего элемента и для связи с индексом. При поиске сперва загружается в память индекс (линейный список с последовательным распределением памяти) потом – искомая запись ‘yi‘. При добавлении происходит реиндексация файла.

Быстродействие увеличивается на 4 порядка.