Размещение данных в памяти эвм
Одномерный линейный список
адрес |
m байт |
|
b |
Строка 1 |
|
b+m |
Строка 2 |
|
|
… |
|
b+(n-1)m |
строка n |
|
Недостатки:
Необходимы большие объемы свободной памяти
При необходимости вставить новую строчку или удалить существующую строку, необходимо сдвигать множество других строк, то есть совершать сдвиги больших объемов памяти ЭВМ
Связное распределение памяти
Память организована в виде связного списка.
Недостаток в том, что необходимо хранить в памяти адрес следующей строки
Организация данных в памяти ЭВМ с использованием методов вычисления адреса по значениям ключей записей
и множество к каким-то образом преобразуется
во множество адресов M.
Исходные записи обязательно упорядочены по ключу
Все записи фиксированной длины
Пример:
Ширина таблицы 20 байт
Номер рейса -
|
Дата вылета |
Наличие билетов |
01 |
001 |
|
01 |
002 |
|
.. |
.. |
|
01 |
365 |
|
02 |
001 |
|
02 |
002 |
|
.. |
.. |
|
02 |
365 |
|
… |
… |
|
Для вычисления
На экзамене есть эти штуки
Метод хеширования (рандомизации)
Основная идея – каждый экземпляр хранимой записи размешается в памяти по адресу, вычисляемому с помощью некоторой адресной функции (хеш-функция) по значению первичного ключа. Пусть в предыдущем примере номер рейса изменяется от 0001 до 9999, но система ставиться в аэропорту, в котором обслуживается лишь 50 рейсов. И они находятся не подряд, а случайно.
Нас интересует третий рейс 4-го января, а второй рейс не обслуживается вообще.
Номер рейса - |
Дата вылета |
Наличие билетов |
0001 |
001 |
|
0001 |
002 |
|
.. |
.. |
|
0001 |
365 |
|
0002 |
001 |
|
0002 |
002 |
|
.. |
.. |
|
0002 |
365 |
|
… |
… |
|
Для того, что бы использовать предыдущую формулу необходимо, что бы все строки были заполнены, иначе нельзя вычислить относительное положение. Информация о тех рейсах, которые не обслуживаются данным аэропортом, все равно должна присутствовать в памяти ЭВМ, если мы хотим использовать предыдущую формулу (пункт 3). То есть громадные объемы памяти будут использоваться впустую.
Что бы исключить этот недостаток, адреса функций будут вычисляться с помощью некоторой хеш-функции, которую выбирают согласно здравому смыслу и которая должна тщательно быть проверена на контрольных примерах.
Ключ будет использоваться в пределах 0001 001 до 9999 365.
А функция должна распределить эти числа в пределах от 0 до 18250 (50*365)
Использование метода квадратов
номер рейса |
дата |
|
l разрядов |
0001 |
001 |
0000 00100 2001 |
00100 |
0008 |
001 |
0000 06401 6001 |
06401 |
0100 |
001 |
0010 00020 0001 |
00020 |
После этого выделяем некоторое количество разрядов из ключа
Достоинства:
Выигрыш больших объемов памяти
Недостатки:
Нарушена сортировка записи в памяти ЭВМ
Образуются пустоты и сгустки информации
Коллизия – двум записям присваивается один и тот же машинный адрес