Домашнее задание 3.

Срок сдачи – 7 апреля ДО лекции. Задания могут сдаваться в лаборантскую кафедры (Айслу) в любой из предыдущих дней.

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

Задавайте вопросы на *****@***ru

Задача 1 (30 очков)

1. Рассмотрите B+ tree порядка 4. Покажите результат вставки ключей:

6, 14, 13, 8, 3, 9, 7, 15, 16, 17, 10, 11, 12, 1, 2, 18, 19, 4, 20, 5

в данном порядке в пустое B+ tree. Достаточно нарисовать конфигурации дерева перед каждым разделением узла, а также его окончательную конфигурацию.

2. Рассмотрите следующее B+ tree порядка 4. Покажите результат удаления Q, N и V, в данном порядке. Приведите вид дерева после каждого удаления.

Q
 
 

 

Задача 2 (25 очков)

Рассмотрим индексно-последовательный файл, состоящий из 4,000,000 блоков. Каждый блок содержит 10 записей фиксированной длины. Для каждого ключевого значения может быть не более 5 записей с этим значением.

Для данной задачи предполагается, что:

. Указатели на блоки имеют длину 8 байт

. Указатели на записи имеют длину 9 байт (указатель на блок плюс 1 байт смещение)

. Индексные блоки имеют длину 4096 байт

. В файле нет записей с продолжением.

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

НЕ нашли? Не то? Что вы ищете?

. Ключ поиска для записей файла имеет длину 12 байт.

а. В предположении, что файл и индекс расположены непрерывно на диске, каков будет размер (в блоках) разреженного одноуровневого первичного индекса? Опишите построение индекса минимального размера.

б. В предположении, что файл и индекс не являются непрерывными на диске, каков будет размер (в блоках) разреженного одноуровневого первичного индекса? Опишите построение индекса минимального размера.

в. Если теперь построить индекс второго уровня для индекса предыдущего пункта (б). Каков будет его минимальный размер в блоках (без записей с продолжением)?

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

д. Если теперь построить индекс второго уровня для индекса предыдущего пункта (г). Каков будет его минимальный размер в блоках (без записей с продолжением)?

Задача 3 (25 очков)

Рассматривается B+ tree. Листы дерева содержат N указателей на записи, каждый блок индекса имеет m указателей. Мы хотим выбрать значение m , минимизирующее время поиска на конкретном диске с характеристиками:

- Время чтения блока в память оценивается величиной (70 + .05*m) мсек. 70 мсек суммируют перемещение головок и другие задержки чтения .05*m мсек – времф передачи блока. Чем больше m, тем больше времени требуется для чтения блока.

- Как только блок в памяти, двоичный поиск используется для нахождения нужного указателя. Время обработки блока в памяти a+ b log 2 m мсек, где a, b – некоторые константы. Предполагается что a значительно меньше 70 мсек.

- Предполагается, что индекс полон, поэтому число блоков, которое необходимо просмотреть при каждом поиске, - log m N.

Ответьте на следующие вопросы:

1. Какое значение m минимизирует время поиска записи с заданным ключом? Ответ можно дать приближенно. Представляемое значение не должно зависеть от b. (Подсказка: Если вы получили уравнение, которое нельзя решить алгебраически, воспользуйтесь известным приближенным методом или методом подбора корня)

2. Что произойдет если уменьшить задержку (70ms)? Например, если уменьшить задержку вполовину, как изменится оптимальное значение m?

Задача 4 (20 очков)

a. Каково общее выражение для минимального числа указателей на записи, которое может иметь B+ tree порядка n, если оно имеет j уровней?

b. Если B+ tree порядка n имеет r указателей на записи, каково максимальное количество уровней j, оно может иметь? Вывести выражение вида j <= f(n, r). Заметьте, что это будет ограничение сверху для числа узлов B+ tree, которое мы должны проверить при поиcке записи с заданным значением ключа, когда индексируемый файл содержит r записей.