Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 32
Текст из файла (страница 32)
персе.) можно обнаружить, что места для него нет, поскольку ссютветствующий узел на втором уровне заполнен до отказа, Однако зта неприятность легко преодолевается путем разбиения узла на две части с тремя ключами в каждой и передачи среднего ключа на первый уровень: преобразуется в (3) В целом, чтобы вставить новый элемент в В-дерево порядка п1, в котором все листья расположены на уровне 1, необходимо вставить новый ключ в подходящее место на уровне 1 — 1. Если соответствующий узел содержит пт ключей, т. е, имеет вид (1) с у = т, разбиваем его на два узла (4) и вставляем ключ К~„,~з1 в родительский по отношению к данному узлу узел (другими словами, указатель Р в родительском узле заменяется последовательностью Р, К~„,~з1, Р').
Такая вставка может привести к аналогичному делению родительского узла (см. рис. 27, на котором показан случай для т = 3). При необходимости разделить корневой узел — сироту без родителя — просто создаем новый корневой узел, содержащий единственный ключ К~„,~т); дерево при этом прибавляет в росте и становится на единицу выше. При такой процедуре вставки все свойства В-деревьев сохраняются; чтобы оценить всю красоту идеи, рекомендуем выполнить упр. 1. По существу, дерево растет "'сверху вверх", вместо того чтобы делать это "снизу вниз", поскольку единственная причина, вызывающая рост дерева, — разделение корня.
Операция удаления из В-дерева немногим сложнее вставки (см. упр. 6). оп ОМ Озв ОЗ1 сот 1033 ! 09 мтт ! 49 1ет !67 !Т9 197 зм ззт И! ТЮ 269 277 307Т в!3 зм звт 4О! звт з то звю 233 4199 4З1 439 461 4 вт 4677 ттз 797 вп 623 041 04ТТ 069 овт а тз О 63 609 юзз 647 звз .вт1 звт вот 61И ВЗ1 Е43 вззз 661 вот 919 езт 947 967 Рис. Зй, В-дерево порядка 1 с листьями, расположенными иа третьем уровяе.
Каждый узел содержит 3, 4, 5 или 6 ключей. Лист, предшествуютдий ключу 449, помечен символом 4 (см. (8)). Верхняя граница времени работы. Посмотрим теперь, к скольким узлам потребуется обратиться в наихудшем случае при поиске в В-дереве порядка т. Предположим, что имеется Ю ключей и иа уровне 1 имеется У+1 лист. Тогда количество узлов иа уровнях 1, 2,3,... равно как минимум 2, 2 ~т/2), 21т/21т, ...; следовательно, У + 1 > 2 1т/2) 1 1 Другими словами, ГХ+ 1~ 1 < 1+ 1о31 э1~ — ); это означает, например, что если Лг = 1999998 и т = 199, то 1 ие превышает 3. Поскольку в процессе поиска иам необходим доступ по крайней мере к 1 узлам, данная формула гарантирует, что время работы алгоритма весьма малб. При вставке нового узла может потребоваться разделить до 1 узлов, однако среднее количество таких разделений существеиио меньше.
Общее количество разделений равио общему количеству внутренних узлов мииус 1. При величии в дереве р виутреииих узлов имеется как минимум 1+ (~т/2) — 1)(р — 1) ключей. Следовательно, Ф вЂ” 1 1'т/2) — 1 Таким образом, среднее количество разделеиий узлов при построении дерева, содержащего Л" ключей, меньше 1/(1т/2) — 1) разделений иа узел. Усовершенствования и изменения, Существует несколько возможностей улучшить методы работы с В-деревьями при иебольших изменениях их определения. Прежде всего, заметим, что все указатели иа уровне 1 — 1 равны Л, а все указатели иа других уровиях ие равны Л. Зачастую это приводит к значительной потере пространства, так что можно "покорить пространство и время", убрав все Л и использовав другое значение т для всех "нижних" узлов. Подобпое примеиеиие двух различных т, однако, ие ухудшает алгоритма вставки, так как обе половииы разделенного узла остаются ка том же уровне, что и оригииал.
Можно даже определить обобщеииое В-дерево порядков тм тт, тз,..., потребовав, чтобы все иекориевые узлы ца уровне 1 — 1 имели от ть/2 до ть потомков, Такое В- дерево имеет различные т иа каждом уровне, однако алгоритм вставки при этом, в сущности, ие меняется. Развивая изложенную в предыдущем абзаце идею, можно использовать различиые форматы узлов иа различных уровнях дерева, а также хранить информацию в листьях. Иногда ключи занимают лишь малую часть записи в файле, и в таких случаях хранение записей целиком в близких к корню узлах может оказаться ошибкой: это может привести к слишком малым т и снизить тем самым эффективность сильиого ветвлеиия. Обратимся вновь к рис. 30 и представим себе, что все записи файла храиятся в листьях и лишь иесколько ключей продублироваио в узлах ветвей. В таком случае крайний слева лист содержит все записи, для которых ключ < 011; лист, помеченный символом А, содержит записи, удовлетворяющие соотношению 439<К <449 и т.
д. При этом листья растут и расщепляются, как и другие узлы, с тем отличием, что записи никогд» не переходят из листьев ва верхние уровни н, таким образом, листья всегда заполнены хотя бы наполовину. Волн каждый лист связан со следующим в симметричном порядке листом, то можно эффективно и удобно проходить по файлу как последовательно, так и в случайном порядке. Такой вариант дерева называется В~-деревом. Некоторые вычисления, проведенные С.
П. Гошем (Б. Р. ОЬозЬ) и М. Э, Сенко (М. Е. Бепйо) (ЗАСЫ 16 (1969), 569-379), приводят к мысли о том, что неплохо иметь большие листья длиной, скажем, до 10 последовательных страниц. При помощи линейной интерполяции в известном для каждого листа диапазоне ключей можно предположить, в какой из десяти страниц должен находиться данный аргумент. Воли такая догадка окажется неверной, будет потеряно время, однако эксперименты свидетельствуют о том, что эти потери могут оказаться меньшими, чем время, сэкономленное на уменьшении дерева.
Т. Х. Мартин (Т. Н. Магсш) (неопубликовано) указал, что идея, лежащая в основе В-деревьев, также может использоваться для ключей переменной длины. Нет необходимости требовать, чтобы количество потомков каждого узла находилось в пределах [ш/2 .. гп]; вместо этого можно просто сказать, что каждый узел должен быть заполнен данными как минимум наполовину. Механизм вставки и разделения продолжает неплохо работать, хотя точное количество ключей в узле зависит от их длин. Однако ключи не должны быть очень длинными, иначе это может все испортить (см. упр. 5).
Другой важной модификацией схемы В-дерева является идея переливания, предложенная Вайером (Вауег) и Мак-Крейтом (МсСге!ба). Она заключается в улучшении алгоритма вставки путем сопротивления соблазну частого разделения. Вместо этого предлагается использовать локальнью повороты. Предположим, что имеется переполненный узел, содержащий ш ключей и т + 1 указатель. Вместо его разделения можно сначала обратить внимание на соседний узел справа, у которого., к примеру, есть у ключей и у + 1 указатель.
В родительском узле имеется ключ Ку, который разделяет ключи двух соседей. Схематично это можно изобразить так: (9) При ) < гп — 1 можно избежать разделения с помощью простой перегруппировки: оставляем 1(гп + Я~2~ ключей в левом узле, заменяем в родительском узле Ку на КВ +~уз~~.~ и помещаем ((ш + у)~2~( оставшихся ключей (в том числе Ку) и соответствующие указатели в правый узел. Таким образом, заполненный узел "переливается" в соседний. С другой стороны, если соседний узел также заполнен Ц = пт — 1), можно разделить оба узла, сделав из них три узла, заполненных на две трети и содержащих ссютветственно 1(2пт — 2)/3), '((2т — 1)/3) и ~2т(3) ключей: ге Рд Р,д Ре Р~ рФ Если у исходного узла нет соседа справа, можно обратиться с предложением о переливании к соседу слева (если имеются оба соседа, та избегать разделения узла можно до тех пор, пока они оба не заполнятся).
И, наконец, если исходный узел не имеет соседей, значит, зто корневой узел. Можно изменить определение В- дерева, позволив корню содержать до 21(2т — 2)/3) ключей, чтобы при разделении корень давал два узла, содержащих по ((2т — 2)/3) ключей. (Не рассмотренный автором случай переливания к соседу, родительский узел которого является соседом родителя исходного узла, хотя и возможен теоретически, но слишком сложен, чтобы иметь преимущество перед разделением узлов.
— )Трим, нерее.) В результате применения всех описанных технологий выводится новая "порода" деревьев (назовем их В"-деревьями порядка т), которые можно определить следующим образом. 1) Каждый узел, за исключением корневого, имеет не более т потомков, й) Каждый узел, за исключением корневого и листьев, имеет не менее (2гп — 1)~3 потомков. И) Корневой узел имеет не менее 2 и не более 2 ((2гп — 2)Д) + 1 потомков. Ь") Все листья находятся на одном уровне.
«) Узлы, не являющиеся листьями и имеющие Й потомков, содержат к — 1 ключ. Важным изменением является условие (В), которое утверждает, что используется минимум две трети имеющегося в каждом узле пространства. Это изменение позволяет не только более аффективно использовать пространство, но и повысить скорость работы, поскольку при зтом в формулах (6) н (7) (гп/2) заменяется на ~ (2гп — 1)/3~, Однако процесс вставки становится более медленным, так как узлам приходится уделять больше внимания при их заполнении (см. приближенный анализ в работе В.
ЕЬапк апд М. Нзп, Ас1а 1пгогтабса 26 (1989), 421-436). Иногда выгоднее позволить узлам быть заполненными менее чем наполовину, чем часто их изменять. Такая ситуация была проанализирована в работе Т. ЛоЬпзоп апд В. 9ЬазЬа, Х Сошрпа Вуза Ясз 47 (1993), 45-76. Возможно, читатель скептично настроен по отношению к В-деревьям, поскольку степень ветвления в корне может быть равна 2. Какой смысл тратить обращение к диску для разветвления всего лишь на 2 пути?! Однако простейшая схема буферизации, называемая замещением дольше всеао не используемой сгпраницм, позволяет преодолеть это неудобство.
Можно выделить во внутренней памяти несколько буферов и избежать реального ввода с диска при наличии страницы в памяти. При использовании втой схемы алгоритмы поиска или вставки выполняют команды "виртуального чтения", которые транслируются в реальные команды ввода данных с диска только при отсутствии необходимой страницы в памяти. Последующая команда "освобождения" выполняется в том случае, когда информация в буфере модифицируется алгоритмом. Когда требуется действительное чтение, выбирается буфер, который был освобожден ранее других, его содержимое, если оно было изменено с момента чтения, записывается на диск и затем в него считывается необходимая страница. Поскольку число уровней дерева обычно малб по сравнению с количеством буферов, такая страничная схема обеспечивает постоянное наличие корневой страницы в памяти; если корень имеет 2-3 потомка, то же самое можно сказать и о страницах первого уровня.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
