Внешний поиск a

Рис. 16.11. Построение расширяемой хеш-таблицы, часть 1
Как и в B-деревьях, первые пять вставок в расширяемую хеш-таблицу приходятся на одну страницу (слева). Затем, при вставке ключа 773, выполняется разбиение на две страницы (одна содержит все ключи, начинающиеся с бита 0, другая — все ключи, начинающиеся с бита 1), а размер каталога удваивается, чтобы он содержал по одному указателю на каждую из страниц (в центре). Ключ 742 вставляется в нижнюю страницу (т.к. он начинается с бита 1), а ключ 373 — в верхнюю страницу (т.к. он начинается с бита 0), но затем нижнюю страницу приходится разбить, чтобы было куда поместить ключ 52 4. Для выполнения этого разбиения все элементы, ключи которых начинаются с битов 10, помещаются на одну страницу, а все элементы, ключи которых начинаются с битов 11 — на другую, и размер каталога снова удваивается, чтобы в нем могли поместиться указатели на обе эти страницы (справа). Каталог содержит две ссылки на страницу, содержащую элементы с ключами, которые начинаются с бита 0: одна для ключей, которые начинаются с битов 00, и другая для ключей, которые начинаются с битов 01.
Программа 16.7 является реализацией операции вставить для расширяемой хеш-таблицы. Сначала, как и при поиске, с помощью единственного обращения к каталогу мы находим страницу, которая может содержать искомый ключ. Затем мы вставляем в нее новый элемент, как это делалось для внешних узлов в B-деревьях (см. программу 16.2). Если в результате этой вставки в узле оказывается M элементов, вызывается функция разбиения — опять же, как и для B-деревьев, правда, на этот раз она сложнее. Каждая страница содержит число к ведущих разрядов, которые совпадают в ключах всех элементов на этой странице, и, поскольку разряды нумеруются слева направо, начиная с 0, к задает также индекс разряда, который необходимо проверить для определения способа разбиения элементов.


Рис. 16.12. Построение расширяемой хеш-таблицы, часть 2
Ключи 766 и 275 вставляются в крайнее правое B-дерево, показанное на рис. 16.11, без разбиения узлов (слева). Затем, при вставке ключа 737, нижняя страницаразбивается, и, поскольку существует только одна ссылка на нижнюю страницу, это приводит кразбиению каталога (в центре). Затем выполняется вставка ключей 574, 434, 641 и 207, после чего необходимо разбиение верхней страницы (справа).