или вставки в В*-дереве порядка М, содержащем Л элементов. Сравните эти предельные значения с соответствующими предельными значениями для В-деревьев (см. лемму 16.2) при Л/= 10, 100 и 1000 и yv= 10\ 10 10 и 10

16.14 Разработайте реализацию операции insert в В*-дереве (основанную на эвристическом методе родственного разделения).

16.15 Создайте рисунок, аналогичный рис. 16.8 для иллюстрации эвристического метода родственного разделения.

16.16 Выполните вероятностную имитацию (см. упражнение 16.11) с целью определения среднего количества страниц, задействованных при использовании эвристического метода родственного разделения при помощи построения В*-дерева порядка М в результате вставки случайных узлов в первоначально пустое дерево, при М= 10, 100 и 1000 и Л 10 10\ 10 и 10

16.17 Создайте программу для восходящего построения индекса В-дерева, начиная с массива указателей страниц, содержащих от М до 2М упорядоченных элементов.

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

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

16.20 Измените реализацию В-дерева в программах 16.1-16.3, чтобы в одном узле дерева могло содержаться М элементов.

t> 16.21 Постройте таблицу значений разностей log999iVH XogNю\л N = 10, 10, 10 и 10

t> 16.22 Реализуйте операцию sort для таблицы символов, основанной на использовании В-дерева.

о 16.23 Реализуйте операцию select для таблицы символов, основанной на использовании В-дерева.

16.24 Реализуйте операцию remove для таблицы символов, основанной на использовании В-дерева.

о 16.25 Реализуйте операцию remove для таблицы символов, основанной на применении В-дерева, при использовании простого метода, когда указанный элемент удаляется из внешней страницы (возможно, допустив, чтобы количество элементов на странице становилось меньше М/2), но чтобы изменение не распространялось вверх по дереву, за исключением, возможно, настройки значений ключей, если удаленный элемент оказался наименьшим на данной странице.

16.26 Измените программы 16.2 и 16.3, чтобы внутри узлов использовался бинарный поиск (профамма 12.6). Определите значение М, при котором время, затрачиваемое программой на построение таблицы символов за счет вставки элемен-

тов со случайными ключами в первоначально пустую таблицу, минимально, при 7V = 10, IG**, 10 и 10 и сравните полученные значения времени с соответствующими значениями для RB-деревьев (программа 13.6).

16.4 Расширяемое хеширование

Альтернатива В-деревьям, расширяющая применение алгоритмов поразрядного поиска на внешний поиск, была разработана Фагином (Fagin), Нивергельтом (Nievergelt), Пиппенгером (Pippenger) и Стронгом (Strong) в 1978 г. Их метод, названный расширяемым хешированием, приводит к реализации операции search, для которой в типичных приложениях требуется всего одно-два зондирования. Для соответствующей реализации операции insert также (почти всегда) требуется всего одно-два зондирования.

Расширяемое хеширование объединяет свойства методов хеширования, использования многопозиционных trie-деревьев и последовательного доступа. Подобно методам хеширования, описанным в главе 14, расширяемое хеширование представляет собой рандомизированный алгоритм - прежде всего необходимо определить хеш-функцию, которая преобразует ключи в целые числа (см. раздел 14.1). Для простоты в этом разделе мы будем просто считать, что ключи являются случайными строками разрядов фиксированной длины. Подобно алгоритмам с использованием многопозиционных trie-деревьев, описанным в главе 15, расширяемое хеширование начинает поиск с использования ведущих разрядов ключей в качестве индексных указателей в таблицу, размер которой является степенью 2. Подобно алгоритмам с применением В-деревьев, при использовании расширяемого хеширования элементы хранятся на страницах, которые разделяются на две части при заполнении. Подобно методам индексного последовательного доступа расширяемое хеширование поддерживает каталог, указывающий, где можно найти страницу, содержащую соответствующие искомому ключу элементы. Поскольку оно объединяет эти знакомые свойства в одном алгоритме, расширяемое хеширование как нельзя более подходит для завершения знакомства с алгоритмами поиска.

Предположим, что количество доступных страниц диска является степенью 2 - скажем, 2. Тогда можно поддерживать каталог 2 ссылок различных страниц, использовать d разрядов ключей для индексных указателей внутрь каталога и хранить на одной и той же странице все ключи, первые к разрядов которых совпадают, как показано на рис. 16.10. Подобно тому, как это делалось в случае В-деревьев, элементы на страницах хранятся по порядку, и достигнув страницы, которая соответствует элементу с заданным искомым оючом, мы выполняем последовательный поиск.

Если удвоить размер каталога и клонировать каждый указатель, можно получить структуру, которую можно индексировать первыми 4 разрядами искомого ключа (рисунок справа). Например, последняя страница по-прежнему определяется как содержащая элементы с ключами, первые три разряда которых - 111, и она будет доступна через каталог, если первые 4 разряда искомого ключа - 1110 или 1111. Этот больший каталог может допускать увеличение таблицы.

Рисунок 16.10 иллюстрирует две базовых концепции, лежащие в основе расширяемого хеширования. Во-первых, нам не обязательно поддерживать 2 страниц.

РИСУНОК 16.10 ИНДЕКСЫ СТРАНИЦ КАТАЛОГА

При использовании каталога, состоящего из восьми записей, можно хранить до 40 ключей, храня все записи, первые 3 разряда которых совпадают, на одной странице, обратиться к которой можно через указатель, хранящийся в каталоге (рисунок слева). Запись О каталога содержит указатель на страницу, которая содержит все ключи, начинающиеся с ООО; запись таблицы 1 содержит указатель на страницу, которая содержит все ключи начинающиеся с 001; запись таблицы 2 содержит указатель на страницу, которая содержит все ключи, начинающиеся с 010, и т.д. Если некоторые страницы заполнены не полностью, количество требующихся страниц можно уменьшить, организуя множество указателей на одну и ту же страницу. В данном примере (слева) ключ 373 находится на той же странице, что и ключи, начинающиеся с 2; эта страница определена как содержащая элементы с ключами, первые два разряда которых - 01.