AOP_Tom3 (1021738), страница 133
Текст из файла (страница 133)
Большое бинарное дерево поиска может быть разделено на "страницы' ! Разумеется, не следует делать страницы очень большими, так как размеры внутренней памяти ограничены и чтение большей страницы отнимает больше времени. Например, предположим, что для чтения страницы, допускающей разветвление на т путей, необходимо 72.5+0.05т шэ. Время на внутреннюю обработку каждой страницы составит около а+ Ыя пг ше, где а малб по сравнению с 72.5 шэ, так что общее время поиска в большой таблице примерно пропорционально 1к гУ, умноженному на (72.5+ 0.05т)/!6ти+ 5. Эта величина достигает минимума при т 307; в действительности этот минимум очень "широк" — близкие к оятнмальному значения достигаются при т в диапазоне от 200 до 500.
На практике получение подобного диапазона подходящих значений т зависит от характеристик используемых внешних запоминающих устройств и от длины записей в таблице. В. И. Ландауэр (%, 1. Ьапг1апег) (1ЕЕЕ Тгапэ. ЕС-12 (1963), 863-871] предложил строить т-арные деревья следующим образом: размещать узлы на уровне 1+ 1, лишь если уровень 1 почти заполнен. Эта схема требует довольно сложной системы поворотов, так как для вставки одного нового элемента может потребоваться основательная перестройка дерева. Ландауэр исходил из предположения, что поиск приходится выполнять гораздо чаще вставок и удалений.
Если файл хранится на диске и является объектом сравнительно редких вставок н удалений, для его представления подходит трехуровневое дерево, где первый уровень разветвления определяет, какой цилиндр диска будет использоваться, второй уровень разветвления определяет дорожку на этом цилиндре, а третий уровень содержит собственно записи. Такой метод называется иг<дексгго-последовательной организацией файла (см. УАСМ 16 (1969), 569-57Ц. Р.
Мюнц (Н.. Мопса) и Р. Узгалис (В. 1)зла)1э) [Ргос. РПпсеСоп Сопб оп 1пб 5сгепсев апс( Яуэсепгэ 4 (1970), 345 — 349) предложили изменить алгоритм поиска по дереву со вставкой 6.2.2Т таким образом, что все вставки порождают узлы, относящиеся к той же странице, что и их родительский узел (если только это возможно) Если страница заполнена, начинается новая страница (если таковая имеется). Если количество страниц не ограничено и если данные поступают в случайном порядке, можно показать, что среднее количество обращений к страницам примерно равно Н~/(Н вЂ” 1), что лишь немногим больше числа обращений при использовании наилучшего т-арного дерева (см.
упр. 8). В-деренья (В-Сгеев). Новый подход ко внешнему поиску с помощью сильноветвящихся деревьев был открыт в 1972 году Р. Байером (Н. Вауег), Э. Мак-Крейтом (Е. МсСгефЬ1) [Асга 1пйзгшаг1са 1 (1972), 173-189] и независимо от них в то же время М. Кауфманом (М.
Капйпап) [не опубликовано). Их идея, которая основана на изменчивости нового вида структур данных, называемых В-деревьями, делает возможным поиск и обновление больших файлов с гарантированной эффективностью в наихудшем случае с помощью сравнительно простых алгоритмов. В-деревом т-го порядка называется дерево, удовлетворяющее следующим условиям. 1) Каждый узел имеет не более пт потомков. й) Каждый узел, за исключением корневого узла и листьев, имеет не менее гп/2 потомков.
ш) Корневой узел, если он не является листом, имеет минимум двух потомков. гк) Все листья находятся на одном и том же уровне и не содержат информации. ч) Нелнстовой узел с й потомками содержит 1г — 1 ключей. (Как обычно, под листом подразумевается конечный, не имеющий потомков узел. Поскольку листья не несут информации, их можно рассматривать как внешние узлы, которых нет в дереве, так что указатели на листы равны Л.) На рис. 30 показано В-дерево порядка 7.
Каждый узел (за исключением корня и листьев) имеет от (7/2) до 7 потомков, т. е, содержит 3, 4, 5 или б ключей. Корневой узел может содержать от 1 до б ключей; в приведенном на рисунке случае их 2. Все листья расположены на уровне 3. Заметьте, что (а) ключи расположены в порядке возрастания слева направо с использованием естественного обобщения концепции симметричного порядка; (Ь) количество листьев на единицу превышает количество ключей. В-деревья порядка 1 н 2, очевидно, не представляют интереса, поэтому будем рассматривать только случай, когда гп > 3. 2-3-деревья, описанные в разделе 6.2.3, представляют собой В-деревья порядка 3.
(Байер и Мак-Крейт рассматривали только нечетные ш; некоторые авторы, говоря о В-деревьях порядка гп, подразумевают под ними то, что мы назвали бы деревом порядка 2гп+ 1.) Узел, содержащий у ключей и у + 1 указатель, может быть представлен как где К~ < Кг < < К, а р, указывает на поддерево с ключами между К; и К, ьм Таким образом, поиск в В-дереве прямолинеен: после размещения узла (1) во внутренней памяти выполняется поиск данного аргумента среди ключей Кы Кг,..., Ку. (При больших 1, вероятно, удобнее воспользоваться бинарным поиском; при малых 1 наилучшим способом поиска будет последовательный поиск.) Если поиск успешен, значит, искомое найдено; при неудачно занершенном поиске, когда ключ находится между К; и К;ы, следует загрузить в оперативную память узел, на который указывает Р„и продолжить процесс.
Если аргумент поиска меньше К„используется указатель Рэ,' при аргументе, большем Кч для продолжения поиска применяется указатель Р . Если Р, = Л, значит, поиск завершился неудачно. Приятная особенность В-деревьев заключается в простоте вставки. Рассмотрим, например, рис. 30. Каждый лист соответствует месту, где может быть выполнена новая вставка. Чтобы вставить новый ключ 337, просто заменим соответствующий узел (2) узлом С другой стороны, при попытке вставить новый ключ 071 (программистам на С/ С++: не примите случайно это число (071) за восьмеричную запись числа 37 ь). —. Прим. перев.) можно обнаружить, что места для него нет„поскольку соответствующий узел на втором уровне заполнен до отказа.
Однако эта неприятность легко преодолевается путем разбиения узла на две части с тремя ключами в каждой и передачи среднего ключа на первый уровенгс преобразуется в (3) В целом, чтобы вставить новый элемент в В-дерево порядка т, в котором все листья расположены на уровне 1, необходимо вставить новый ключ в подходящее место на уровне 1 — 1. Если соответствующий узел содержит нт ключей, т, е.
имеет вид (1) с 1 = т, разбиваем его на два узла и вставляем ключ К~ 7з) в родительский по отношению к данному узлу узел (другими словами, указатель Р в родительском узле заменяется последовательностью Р, К~ 7з, Р'). Такая вставка может привести к аналогичному делению родительского узла (см. Рис. 27, на котором показан случай для т = 3). При необходимости разделить корневой узел -- сироту без родителя — просто создаем новый корневой узел, содержащий единственный ключ Кр„~з1; дерево прн этом прибавляет в росте н становится на единицу выше. При такой процедуре не~анки все свойства В-деревьев сохраняются; чтобы оценить всю красоту идеи, рекомендуем выполнить упр. 1. По существу, дерево растет "сверху вверх", вместо того чтобы делать это "снизу вниз", поскольку единственная причина, вызывающая рост дерева, — разделение корня.
Операция удаления из В-дерева немногим сложнее вставки (см. упр. 6). 011 оы Озв ОЗ! 097 1ОЗ 109 12Т !9! 149 157 Ыт 179 !97 ю! 227 241 257 269 277 зат з!з зз! 34Т ззв ва! збт зта 359 233 449 419 4З! 459 461 467 ввт 67Т ттз ввз 797 511 юз Взв 859 877 О41 овт 059 овт отз авз 509 ыз 547 заз 571 ззт 60Т 817 631 Вбв 653 651 691 709 тзт 789 751 761 907 919 937 94Т 967 Рис. ЗО.
В-дерево порядка у с листьями, расположенными на третьем уровне. Каждый узел содержит 8, 4, 5 или 8 ключей, Лист, предшествующий ключу 449, помечен символом А (см. ~8)). Верхняя граница времени работы. Посмотрим теперь, к скольким узлам потребуется обратиться в наихудшем случае при поиске в В-дереве порядка т. Предположим, что имеется Х ключей и на уровне 1 имеется г1'+1 лист. Тогда количество узлов на уровнях 1,2,3,... равно как минимум 2, 2(т/2), 2(т/2) г, ...; следонательно, Я+ 1 > 2(т/21' '. Другими словами, (6) это означает, например, что если Х = 1999998 и т = 199, то 1 не превышает 3. Поскольку в процессе поиска нам необходим доступ по крайней мере к 1 узлам, данная формула гарантирует, что время работы алгоритма весьма малб. Прн вставке нового узла может потребоваться разделить до 1 узлов, однако среднее количество таких разделений существенно меныпе. Общее количество разделений равно общему количеству внутренних узлов минус 1.
При наличии в дереве р внутренних узлов имеется как минимум 1+ ((т/2) — 1)(р — 1) ключей. Следовательно, (7) Таким образом, среднее количество разделений узлов при построении дерева, содер- жащего Х ключей, меньше 1/((т/2) — 1) разделений на узел. усовершенствования и изменения. Существует несколько возможностей улучшить методы работы с В-деревьями при неболыпнх изменениях их определения. Прежде всего, заметим, что все указатели на уровне 1 — 1 равны А, а все указатели на других уровнях не равны Л.
Эачастую это приводит к значительной потере пространства, так что можно "покорить пространство и время", убрав все Л н использовав другое значение т для всех "нижних" узлов. Подобное применение двух различных т, однако, не ухудшает алгоритма вставки, так как обе половины разделенного узла остаются на том же уровне, что и оригинал. Можно даже определить обобщенное В-дерево порядков ты тг, тг,..., потребовав, чтобы все некорневые узлы на уровне 1 — 1 имели от ть/2 до ть потомков. Такое В- дерево имеет различные т на каждом уровне, однако алгоритм вставки при этом, в сущности, не меняется. Развивая изложенную в предыдущем абзаце идею, можно использовать различные форматы узлов на различных уровнях дерева, а также хранить информацию в листьях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
