Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 33
Текст из файла (страница 33)
Заметим, что страницы, которые могут понадобиться для разделе. ния при вставке, автоматически присутствуют в памяти в силу обращения к ним во время предыдущего поиск». Эксперименты Э. Мак-Крейта (Е. МсСге18Ьг) показали, что такая политика работы вполне успешна. Например, им было найдено, что при 10 буферах и гп = 121 процесс вставки 100000 ключей в порядке возрастания требует пхчько 22 действительных чтений и тоаько 857 реальных команд записи. Таким образом, ббльшая часть действий выполнялась во внутренней памяти.
Далее, полученное дерево содержало всего 835 узлов, лишь на один узел больше, чем минимально возможное значение ~100000/(гп — 1)~ = 834; следовательно, память была использована практически на 100%. В этом эксперименте применялась технология переливания, но с разделением на две части согласно (4), а не на три, как в (10) (см. упр. 3). В другом эксперименте, также с десятью буферами, гп = 121 и использованной технологией переливания, Э. Мак-Крейт вставил о000 ключей в первоначально пустое дерево в случайном порядке. При этом было получено двухуровневое дерево с 48 узлами (утилизация памяти составила 87%) после выполнения 2 762 реальных чтений и 2 739 реальных записей.
Затем для 1000 случайных поисков потребовалось 786 реальных чтений. В результате того же эксперимента без применения переливания было построено двухуровневое дерево с 62 узлами (утилизация памяти— 67%) после выполнения 2743 реальных чтений и 2800 реальных записей. Далее для 1000 случайных поисков потребовалось 836 реальных чтений.
Это показывает не только эффективность страничной схемы, но и преимушества, полученные от использования технологии перыивания. Эндрю Яо (Апг(геп Као) доказал, что среднее количество узлов после случайных вставок без переливания для больших Ф и гп равно Х/(т 1п 2) + 0(Х/гп~), так что утилизация памяти будет составлять примерно 1п 2 = 69.3% [АсГа 1п/оггпаВса 9 (1978), 159-170).
Более детальный анализ можно найти в работах В. Е1вепЬаггЬ, 35 2Маш, О. Н. Ооппет, К. МеЫЬогп, ап<1 П. Жопа, 1п/огшагюп апс( Соп1го) 55 (1982), 125 — 174; В., А. Ваези- загсе, АсГа 1пуогша11са 26 (1989), 439-471. В-деревья со времен своего изобретения стали чрезвычайно популярны. Обратитесь, например, к статье Дугласа Комера (Попй!аз Сошег) в Сошригшй Япггеув 11 (1979), 121-138, 412, в которой обсуждаются ранние разработки и описывается широко используемая система ЧБАм (К(ггпа1 Бгогабе Ассезв МегЬоб — метод доступа к виртуальной памяти), созданная в 1ВМ Согрогагюп. Одним из новшеств КБАМ была репликация блоков дисковых цилиндров с целью минимизации времени обращения.
Две из наиболее интересных разработок основ стратегии В-деревьев получили одинаковые имена: "5В-деревья" и "БВ-деревья': ЯВ-дерево П. 1О. О'Нейла (Р. Е. О'Хе(1) ]Асса Хпб 29 (1992), 241-265] создано для минимизации времени выполнения дисковых операций путем расположения соседних записей в одном цилиндре; тем самым поддерживается высокая эффективность рабаты приложений, в которых требуется одновременный доступ к множеству последовательных записей (в этом случае кВВ" выделяется курсивом и В означает "весгпепг(а)" — "последовательныйе). БВ-дерево (см. Р. Геггаб(па апс( В.. Огошс, АТОС 27 (1995), 693-702; ВОВА 7 (1996), 373-382) представляет собой элегантную комбинацию структуры В-дерева с деревьями "Патриция", о которых пойдет речь в разделе 6.3; в этом случае "БВ" записывается обычным шрифтом и Б означает "вгПп8" — "строка". Такие деревья используются во многих приложениях для крупномасштабной обработки текстов и обеспечивают эффективную сортировку строк переменной длины на диске ]Агбе, Гегга81па, Оговв1, апс1 Ъ йгег, ВТОС 29 (1997)„540-548].
УПРАЖНЕНИЯ 1. [10] Какое В-дерево парадна 7 получится после вставки ключа 613 в дерево, показанное на рнс. 30 (технология переливания не используется)? 2. (М) Выполните упр. 1, используя технологию переливания с разделением на три части, как в (10). 3. ]33] Предположим, что ключи 1, 2, 3,, в порядке возрастания всшаляются в изначально пустое В-дерева порядка 101, Какой ключ приведет к появлению листьев на уровне 4: а) без использования переливания; Ь) при использовании переливания с разделением только на 2 части, как в (4); с) при использовании В -дерева порядка 101 с переливанием н разделением на 3 части, в (10)? 4, ]21] (Байер (Вауег) и Мак-Крейт(МсСгесб)гс),) Объясните, как выполнить вставки в обобщенное В-дерево так, чтобы все узлы, кроме корня н листьев, имели не менее вас — с потомков.
б. (в1] Предположим, чта для узлов отведено по 1000 снмвсиов во внешней памяти. Если каждый указатель занимает 5 символов и если ключ имеет длину, кратную пяти н находащуюос в пределах от 5 до 50 символов, та каково минимальное количество символов, занятых в узле после его разделения в процессе вставки? (Рассмотрите только простую процедуру разделения, аналогичную описанной в тексте для В-дерева с ключам фиксированной длины без переливания; рассмотрите перемещение вверх ключа, который делает оставшиеся части наиболее близкими па размеру.) 6. ]вУ] Разработайте алгоритм удаления нз В-деревьев. 7. (йв] Разработайте алгоритм конкатенации В-деревьев (см.
раздел 6.3.3). 8. ]ЛМ37] Рассмотрим обобщение вставки в дерево, предложенное Мюнцем (Мапгв) н Узсвлисом (1)вбайв), в котором каждая страница может содержать М ключей. Пусть в дерево вашвлено Ю случайных элементов, так что оно имеет ?сс+ 1 внешний узел. Обозначим через Ь вероятность тога, что при неудачном поиске потребуется Ь обращений к сс) страницам и чго он закончится в узле, родительский узел которога принадлеясит странице, содержащей з ключей. Пусть Всс (в) = 2 Ьлав — соответствующая производящая 6~ Ссп функц .
До, чт Вч1(х) = 4 ~х и В,„г()= Вя',(х)+ — В4, () 1</СИ; 01 М вЂ” у — 1 ш у'+1 О и й'+1 -' Л +1 Найдите асимптотическое поведение Ся ы Я., В (1) — среднего числа страниц, к которым осуществляется обращение при неудачном поиске. (Указание. Выразите рекуррентное соотношение с помощью матрицы -з о 0 2х о о а о Э -4 0 4 ()хх о а ... -и-1 о о а ... и+1 -г Мало известно, даже при использовании иных эквивалентных алгоритмов, об оптимизации выделения памяти, м«нимизэцик количества необходимых операций и т, п. эта область исследований долж«э черпать песу Рсы длл дальнейшего пРогресса «ак из чистой., тэк и из приклад«ой математ«кх.
— ЭНТОНИ Г. ЙТТИНГЕР (АНТНОЫУ Е. ОЕТТ!ЫЕЕй) (1961) и сопоставьте Сь с многочленом )ч'-й степени в И'(1)), 9. (йй) Может ли идея В-деревьев использоваться для получения элементов линейного списка по позиции, а не по значению ключа (см. алгоритм 6,2,3В)2 ь 10. (Уб] Обдумайте, каким образом большой файл, организованный в виде В-дерева, можно использовать для доступа и изменения со стороны большого числа одновремен- но работающих пользователей, чтобы пользователи различных страниц практически не мешали друг пруту. б,З. ЦИФРОВОЙ ПОИСК Вместо методов поиска, основанных иа сравиеиии ключей, можно воспользоваться представлением ключей в виде последовательиости цифр или букв. Рассмотрим, например, "побуквенные меткие в больших словарях (или записных адресных книжках), которые позволяют мгновенно иайти страницы со словами, яачииающимися с определенной буквы*. Развивая идею побуквеииых меток до ее логического завершения, можно получить схему поиска, осиоваииую иа повторяемом индексировании, которое проилдюстрироваио в табл.
1. Предположим„что необходимо проверить, является ли данный аргумент поиска одним из 31 наиболее употребительного английского слова (см. рис. 12 и 13 в разделе 6.2.2). Данные представлены в табл. 1 в виде сгпррктрры луча**. Дуч, по сути, — зто М-ариое дерево, узлы которого представляют М-местные векторы с компонентами, соответствующими цифрам или буквам. Каждый узел уровня 1 является иабором всех нлючей, иачииаиицихся с определенной последовательности ! символов, которая называется его префиксом (рте)гк); узел определяет разветвлеиие иа М путей в зависимости от ! + 1 символа.
Например, луч из табл. 1 содержит 12 узлов; узел (1) представляет собой корень, в котором мы ищем первую букву. Вали первой буквой является, скажем, И, из таблицы следует, что либо зто слово ИОТ, лкбо такого слова вообще иет в таблице. В то же время, если первая буква — И, то узел (1) отправит яас к узлу (9) для поиска второй буквы тем же способом, Узел (9) указывает, что вторая буква должиа быть А, Н или 1. Префикс узла (10) — НА.
Пустые записи в таблице означают отсутствие связей. Узлы-векторы в табл. 1 расположены в соответствии с кодами символов И11. Это означает, что елучевой поиск" будет весьма быстрым, поскольку следует просто выбирать слова из массивов с использованием символов наших ключей в качестве ицдексов. Техиологии быстрого миогопутевого принятия решения по индексу называются просмотром таблицы (саЫе!оо)с-ас) в отличие от поиска по таблице (саЫе !оо1с-цр) (см, Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
