МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ

Ордена Трудового Красного Знамени федеральное государственное бюджетное образовательное учреждение высшего образования

«Московский технический университет связи и информатики»

Кафедра «Сетевые информационные технологии и сервисы»

Задача №4

по дисциплине

«Принципы построения систем управления базами данных и знаний»

Выполнила:

Вариант №13

Проверил: доцент, к.т.н., Гадасин Д.В.

Москва, 2023

Оглавление

Условие задачи 4 3

1. количество пар «ключ-указатель» 3

2. количество блоков для построения плотного индекса 3

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

Индивидуальное задание 3

Решение задачи 4 4

Условие задачи 4

Пусть дано отношение, содержащее А кортежей, и для хранения записей используется блок Б. Длина ключевого поля равняется С байт. Указатель – Д байт, а заголовок блока – E байт. Необходимо найти:

1. количество пар «ключ-указатель»

2. количество блоков для построения плотного индекса

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

Индивидуальное задание

Вариант	A	B	C	D	E
13	1000000	4096	79	2	46

Решение задачи 4

Количество пар «ключ-указатель»:

= [(B – E)/(C + D)]

= [ = 50

Количество блоков для построения плотного индекса:

R блоков = [A/R кр]

= = = 20 000

Количество операций:

S = + + 1

S = + + 1 = 15 + 6 + 1 = 22

Ответ:

= 20 000

S = 22