AOP_Tom3 (1021738), страница 134
Текст из файла (страница 134)
Иногда ключи занимают лишь малую часть записи в файле, и в таких случаях хранение записей целиком в близких к корню узлах может оказаться ошибкой: это может привести к слишком малым т н снизить тем самым эффективность сильного ветвления. Обратимся вновь к рис. 30 и представим себе, что все записи файла хранятся в листьях н лишь несколько ключей продублировано в узлах ветвей. В таком случае крайний слева лист содержит нсе записи, для которых ключ < 011; лист, помеченный символом А, содержит записи, удовлетворяющие соотношению 439 < К < 449 (8) и т. д. При этом листья растут и расщепляются, как и другие узлы, с тем отличием, что записи никогда не переходят из листьев на верхние уровни и, таким образом, листья всегда заполнены хотя бы наполовину.
Если каждый лист связан со следующим в симметричном порядке листом, то можно эффективно и удобно проходить по файлу как последовательно, так и в случайном порядке. Такой вариант дерева называется В -деревом. Некоторые вычисления, проведенные С. П. Гошем (6. Р. Опоэп) и М. Э. Сенко (М. Е. 6епьо) [1АСМ 16 (1969), 569-579), приводят к мысли о том, что неплохо иметь большие листья длиной, скажем, до 10 последовательных страниц. Г!ри помощи линейной интерполяции в известном для каждого листа диапазоне ключей можно предположить, в какой из десяти страниц должен находиться данный аргумент.
Если такая догадка окажется неверной, будет потеряно время, однако эксперименты свидетельствуют о том, что эти потери могут оказаться меньшими, чем время, сэкономленное на уменьшении дерева. Т. Х. Мартин (Т. Н. Маг11п) (неопубликовано', указал, что идея, лежащая в основе В-деревьев, также может использоваться для ключей переменной длиньь Нет необходимости требовать, чтобы количество потомков каждого узла находилось в пределах (т/2 .. т]; вместо этого можно просто сказать, что каждый узел должен быть заполнен данными как минимум наполовину. Механизм вставки и разделения продолжает неплохо работать, хотя точное количество ключей в узле зависит от их длин. Однако ключи не должны быть очень длинными, иначе это может все испортить (см. упр. 5). Другой важной модификацией схемы В-дерева является идея переливания, предложенная Вайером (Вауег) и Мак-Крейтом (МсСге161п).
Она заключается в улучшении алгоритма вставки путем сопротивления соблазну частого разделения. Вместо этого предлагается использовать локальные повороты. Предположим, что имеется переполненный узел, содержащий ти ключей и т+ 1 указатель. Вместо его разделения можно сначала обратигь внимание на соседний узел справа, у которого, к примеру, есть у' ключей и у + 1 указатель.
В родительском узле имеется ключ Ку, который разделяет ключи двух соседей. Схематично это можно изобразить так: (9) При у ( т — 1 можно избежать разделения с помощью простой перегруппировки: оставляем ((т + у)/2~ ключей в левом узле, заменяем в родительском узле Ку на КН ь узы~, н помещаем ((пз + у)/2) оставшихся ключей (в том числе Хс~) и соответствующие указатели в правый узел. Таким образом, заполненный узел "переливается" в соседний.
С другой стороны, если соседний узел также заполнен (у = т — 1), можно разделить оба узла, сделав из них три узла, заполненных на две трети и содержащих соответственно 1(2т — 2)/З~, '((2щ — 1)/З~ и (2гп/3) ключей: (10) Рс Р~ Р„, Рс Р1 Р,' Если у исходного узла нет соседа справа, можно обратиться с предложением о переливании к соседу слева (если имеются оба соседа, то избегать разделения узла можно до тех пор, пока они оба не заполнятся). И, наконец, если исходный узел не имеет соседей, значит, это корневой узел. Можно изменить определение В- дерева, позволив корню содержать до 2 ((2т — 2)/З~ ключей, чтобы при разделении корень давал два узла, содержлзцих по ((2т — 2)/3~ ключей.
(Не рассмотренный автором случай переливания к соседу, родительский узел которого является соседом родителя исходного узла, хотя и возможен теоретически, но слишком сложен, чтобы иметь преимущество перед разделением узлов. — Прим. перев.) В результате применения всех описанных технологий выводится новая "порода" деревьев (назовем их В -деревьями порядка т), которые можно определить следующим образом. 1) Каждый узел, за исключением корневого, имеет не более т потомков. й) Каждый узел, за исключением корневого и листьев, имеет не менее (2т — 1)/3 потомков. гй) Корневой узел имеет не менее 2 и не более 2 ((2т — 2)/З~ + 1 потомков.
РР) Все листья находятся на одном уровне. Р) Узлы, не являющиеся листьями и имеющие 1с потомков, содержат й — 1 ключ. Важным изменением является условие (й), которое утверждает, что используется минимум две трети имеющегося в каждом узле пространства. Это изменение позволяет не только более эффективно использовать пространство, но и повысить скорость работы, поскольку при этом в формулах (6) и (7) (т/2) заменяется на ~(2т — 1)/31. Однако процесс вставки становится более медленным, так как узлам приходится уделять больше внимания при их заполнении (см, приближенный анализ в работе В.
ЕЬал8 апд М. Нзп, Асга 1п$огша11са 26 (1989), 421-438). Иногда выгоднее позволить узлам быть заполненными менее чем наполовину, чем часто их изменять. Такая ситуация была проанализирована в работе Т. ЗоЬпвоп апс1 П. БЬалЬа, Х Сотриа Яузб Ясй 47 (1993), 45 — 76. Возможно, читатель скептично настроен по отношению к В-деревьям, поскольку степень ветвления в корне может быть равна 2.
Какой смысл тратить обращение к диску для разветвления всего лишь на 2 пути?! Однако простейшая схема буферизации, называемая замещением дольше всего не используемой страницы, позволяет преодолеть это неудобство. Можно выделить во внутренней памяти несколько буферов и избежать реального ввода с диска прн наличии страницы в памяти. При использовании этой схемы алгоритмы поиска или вставки выполняют команды "виртуального чтения", которые транслируются в реальные команды ввода данных с диска только при отсутствии необходимой страницы в памяти.
Последующая команда "освобождения" выполняется в том случае, когда информация в буфере модифицируется алгоритмом. Когда требуется действительное чтение, выбирается буфер, который был освобожден ранее других, его содержимое, если оно было изменено с момента чтения, записывается на диск и затем в него считывается необходимая страница. Поскольку число уровней дерева обычно мало по сравнению с количеством буферов, такая страничная схема обеспечивает постоянное наличие корневой страницы в памяти; если корень имеет 2 — 3 потомка, то же самое можно сказать и о страницах первого уровня. Заметим, что страницы, которые могут понадобиться для разделения при вставке, автоматически присутствуют в памяти в силу обращения к ним во время предыдущего поиска. Эксперименты Э.
Мак-Крейта (Е. МсСге1851) показали, что такая политика работы вполне успешна. Например, им было найдено, что при 10 буферах и т = 121 процесс вставки 100000 ключей в порядке возрастания требует только 22 действительных чтений и только 857 реальных команд записи, Таким образом, ббльшая часть действий выполнялась во внутренней памяти. Далее, полученное дерево содержало всего 835 узлов, лишь на один узел больше, чем минимально возможное значение (100000/(т — 1)~ = 834; следовательно, память была использована практически на 100%.
В этом эксперименте применялась технология переливания, но с разделением на две части согласно (4), а не на три, как в (10) (см. упр, 3). В другом эксперименте, также с десятью буферами, гп = 121 и использованной технологией переливания, Э. Мак-Крейт вставил 5000 ключей в первоначально пустое дерево в случайном порядке. При этом было получено двухуровневое дерево с 48 узлами (утилизация памяти составила 87%) после выполнения 2762 реальных чтений и 2 739 реальных записей. Затем для 1 000 случайных поисков потребовалось 786 реальных чтений.
В результате того же эксперимента без применения переливания было построено двухуровневое дерево с 62 узлами (утилизация памяти— 67%) после выполнения 2743 реальных чтений и 2800 реальных записей. Далее для 1000 случайных поисков потребовалось 836 реальных чтений. Это показывает не только эффективность страничной схемы, но и преимущества, полученные от использования технологии переливания. Эндрю Яо (Апг1геъ Уао) доказал, что среднее количество узлов после случайных вставок без переливания для больших Л и тп равно Ж/(т 1п 2) + 0(Х/пзз), так что утилизация памяти будет составлять примерно 1и 2 = 69.3% (Асса 1пгогшаыса 9 (1978), 159-170).
Более детальный анализ можно найти в работах В. Е1эепЬаг1Ь, Х. 21х1апй О. П. Ооппег, К. Мерййогн, апг1 П. Жоог1, 1пгогтаГюп апд Сопгго! 55 (1982), 125-174; В. А. Ваеза-алагез, Асга уп/огшабса 26 (1989), 439 — 471. В-деревья со времен своего изобретения стали чрезвычайно популярны. Обратитесь, например, к статье Дугласа Комера (Ропб!аз Сошег) в Сошрпбпб 8иг еуз 11 (1979), 121-138, 412, в которой обсуждаются ранние разработки и описывается широко используемая система Ч8АМ (Ъ'1ггна! 81огабе Ассеээ МетЬод — метод доступа к виртуальной памяти), созданная в 1ВМ Согрогабоп.
Одним из новшеств Н8АМ была репликация блоков дисковых цилиндров с целью минимизации времени обращения. Две из наиболее интересных разработок основ стратегии В-деревьев получили одинаковые имена: "оВ-деревья" и "БВ-деревья". оВ-дерево П. Ю. О'Нейла (Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
