(P. E. ONeil) [Acta Inf. 29 (1992), 241-265] создано для минимизации времени выполнения дисковых операций путем расположения соседних записей в одном цилиндре; тем самым поддерживается высокая эффективность работы приложений, в которых требуется одновременный доступ к множеству последовательных записей (в этом случае "5В" выделяется курсивом и S означает "sequential" - "последовательный"). SB-дерево (см. Р. Ferragina and R. Grossi, STOC 27 (1995), 693-702; SODA 7 (1996), 373-382) представляет собой элегантную комбинацию структуры В-дерева с деревьями "Патриция", о которых пойдет речь в разделе б.З; в этом случае "SB" записывается обычным шрифтом и S означает "string" - "строка" Такие деревья используются во многих приложениях для крупномасштабной обработки текстов и обеспечивают эффективную сортировку строк переменной длины на диске [Arge, Ferragina, Grossi, and Vitter, STOC 29 (1997), 540-548].

УПРАЖНЕНИЯ

1. [10] Какое В-дерево порядка 7 получится после вставки ключа 613 в дерево, показанное на рис. 30 (технология переливания не используется)?

2. [15] Выполните упр. 1, используя технологию переливания с разделением на три части, как в (10).

► 3. [23] Предположим, что ключи 1, 2, 3, ... в порядке возрастания вставляются в изначально пустое В-дерево порядка 101. Какой ключ приведет к появлению листьев на уровне 4:

a) без использования переливания;

b) при использовании переливания с разделением только на 2 части, как в (4);

c) при использовании В*-дерева порядка 101 с переливанием и разделением на 3 части, как в (10)?

4. [21] (Байер (Bayer) и Мак-Крейт (McCreight).) Объясните, как выполнить вставки в обобщенное В-дерево так, чтобы все узлы, кроме корня и листьев, имели не менее т - потомков.

► 5. [21] Предположим, что для узлов отведено по 1000 символов во внешней памяти. Если каждый указатель занимает 5 символов и если ключ имеет ддину, кратную пяти и находящуюся в пределах от 5 до 50 символов, то каково минимальное количество символов, занятых в узле после его разделения в процессе вставки? (Рассмотрите только простую процедуру разделения, аналогичную описанной в тексте для В-дерева с ключом фиксированной длины без переливания; рассмотрите перемещение вверх ключа, который делает оставшиеся части наиболее близкими по размеру.)

6. [23] Разработайте алгоритм удаления из В-деревьев.

7. [28] Разработайте алгоритм конкатенации В-деревьев (см. раздел 6.2.3).

► 8. [НМ37] Рассмотрим обобщение вставки в дерево, предложенное Мюнцем (Muntz) и Узгалисом (Uzgalis), в котором каждая страница может содержать М ключей. Пусть в дерево вставлено N случайных элементов, так что оно имеет N +1 внешний узел. Обозначим через вероятность того, что при неудачном поиске потребуется к обращений к страницам и что он закончится в узле, родительский узел которого принадлежит странице, содержащей j ключей. Пусть В(2) = - соответствующая производящая

функция. Докажите, что b[\z) = Sjiz и

N-j-l

Найдите асимптотическое поведение С - YIjLinW - среднего числа страниц, к которым осуществляется обращение при неудачном поиске. [Указание. Выразите рекуррентное соотношение с помощью матрицы

/-3 О ... О 2z\ 3 -4 ... О О

О 4 ... О О

W{z) =

О О ... -М-1 о о о ... М+1 -21

и сопоставьте С с многочленом iV-й степени в И(1)].

9. [22,\ Может ли идея В-деревьев использоваться для получения элементов линейного списка по позиции, а не по значению ключа (см. алгоритм 6.2.3В)?

► 10. [55] Обдумайте, каким образом большой файл, организованный в виде В-дерева, можно использовать для доступа и изменения со стороны большого числа одновременно работающих пользователей, чтобы пользователи различных страниц практически не мешали друг другу.

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

- ЭНТОНИ г. ЁТТИНГЕР (ANTHONY G. OETTINGER) (1961)

6.3. ЦИФРОВОЙ ПОИСК

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

Развивая идею побуквенных меток до ее логического завершения, можно получить схему поиска, основанную на повторяемом индексировании, которое проиллюстрировано в табл. 1. Предположим, что необходимо проверить, является ли данный аргумент поиска одним из 31 наиболее употребительного английского слова (см. рис. 12 и 13 в разделе 6.2.2). Данные представлены в табл. 1 в виде структуры луча**. Луч, по сути, - это М-арное дерево, узлы которого представляют М-местные векторы с компонентами, соответствующими цифрам или буквам. Каждый узел уровня / является набором всех ключей, начинающихся с определенной последовательности I символов, которая называется его префиксом (prefix); узел определяет разветвление на М путей в зависимости от / -Ь 1 символа.

Например, луч из табл. 1 содержит 12 узлов; узел (1) представляет собой корень, в котором мы ищем первую букву. Если первой буквой является, скажем, N, из таблицы следует, что либо это слово NOT, либо такого слова вообще нет в таблице. В то же время, если первая буква - W, то узел (1) отправит нас к узлу (9) для поиска второй буквы тем же способом. Узел (9) указывает, что вторая буква должна быть А, Н или I. Префикс узла (10) - НА. Пустые записи в таблице означают отсутствие связей.

Узлы-векторы в табл. 1 расположены в соответствии с кодами символов MIX. Это означает, что "лучевой поиск" будет весьма быстрым, поскольку следует просто выбирать слова из массивов с использованием символов наших ключей в качестве индексов. Технологии быстрого многопутевого принятия решения по индексу называются просмотром таблицы (table look-at) в отличие от поиска по таблице (table look-up) [см. Р. М. Sherman, САСМ 4 (1961), 172-173, 175].

Алгоритм Т {"Лучевой поиск" {Trie search)). Дана таблица записей в форме Агарного луча. Алгоритм осуществляет поиск по заданному аргументу К. Узлы луча представляют собой векторы, индексы которых изменяются от О до М - 1; каждый компонент такого вектора представляет собой ключ или ссылку (возможно, пустую).

Т1. [Инициализация.] Установить ссылочную переменную Р таким образом, чтобы она указывала на корень луча.

Т2. [Ветвление.] Установить к равным следующему символу входного аргумента ключа К слева направо. (Если аргумент полностью просканирован, установить

* Наличие у страницы книги трех свободных сторон позволило однажды переводчику этого раздела оснастить свой словарь метками поиска до третьей буквы слова включительно. - Прим. перев.

** В оригинале используется термин trie (произносится как английское слово "try"), предложенный Э. Фредкиным (Е. Fredkin) [САСМ 3 (1960), 490-500]. Этот термин представляет собой часть слова "retrieval" В русском переводе будет использоваться часть слова "получение" (информации). И хотя при этом теряется определенная игра слов, основанная на схожести слов trie и tree, приобретается некоторый смысл, згшоженный в слове луч; быстрый четко Определенный по направлению движения поиск. - Прим. перев.