Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 48
Текст из файла (страница 48)
1!режде всего нужно сформулировать описание страницы. Мы выбираем расположение элементов в виде массива; зу4ге роке: — гееотй щ; Ьгуех угйм гег"; (4.81) и; аггеу11., пгг1 ог" гуеггг епй 4.ве. Сильно вегвяививея деревья 285 где совэФ лл = 2ьл; Фуре геГ = ')раке' Мвх = 0 ..лл Фуре 1!егп, гесогй йеу: ФлГейег; р: гег"; свинг: ЬМвяег ево (4М2) Здесь вновь компонента соипг заменяет всевозможную прочую информацию, которая может быть связана с каждым элементом, но не играет никакой роли в самом процессе поиска. Заметим, что каждая страница содержит пространство для 2п элементов.
Поле гл указывает, сколько элементов размсгцено в действительности. Поскольку гл ~ и (за исключением страницы-корня), использование памяти гарантируется по крайней мере на 60 Ъ. Алгоритм поиска с включением по Б-дереву является частью программы 4.7; он оформлен в виде процедуры зеагвЬ. Его основная структура проста и напоминает структуру простого поиска по бинарному дереву, с той разницей, что дальнейший путь выбирается не нз двух возможных ветвей.
Вместо этого «понск внутри страницы» оформлен как бинарный поиск в массиве. Алгоритм включения сформулирован в виде отдельной процедуры лишь для ясности. Эта процедура вызывается после того, как звагсй указывает, что элемент нужно передать вверх по дереву (в направлении к корню).
Для указания используется булевский параметр-результат й, он играет роль, подобную й в алгоритме включения в сбалансированное дерево, ;де он сооб|цает, что поддерево выросло. Если 6 истинно, то второй параметр-результат и представляет передаваемый вверх элемент, Отметим, что включение начинается с гипотспшеских страниц, а именно «специальных узлов» (см. рпс. 4З9); новый элемент сразу отправляется через параметр и на страницу-лист для включения. Набросок схемы приведен в (4.83). Если гюсле вызова яеагсй в основной программе параметр 6 истинен, это означает расщепление страницы-корня.
Поскольку эта страница играет особую роль, процесс нужно запрограммировать отдельно. Он состоит нз размещения новой корневой страницы и включения в нее одного элемента, переданного через параметр и, Следовательно, новая стра- ч. Динамические информанионнме сгрлнгарм ргаеейнге зеагсй(х: 1пГееег; а: Ге~; тат Ь: йоо!еап; тат ац йет); Ъен(п 11' и = п11 йеп Ъее(п [х нет в дереве) Лрисвоение значения х элементу и, установка Л в ггие, указывая, что элемент и передается вверх по дереву епа е1ае тт1й а[ ае Ъея(в [поиск х на странице а1) двоичный поиск в массиве; 11'найдено йеп увеличение счегпчика появлений элемента еЬе Ъей[п зеагсй (х, попюмок, Л, и) Ы Ь йеп [передача вверх элемента и) И (число элементов на а[) < 2п йеп включение и в страницу а[ и установка й в уа1зв е[эе расщепление страницы и передача вверх среднего элемента епй епй ева (4.83) ница-корень содержит только один элемент.
Детали можно посмотреть в программе 4.7. На рпс. 4.48 показан результат работы программы 4.7 прн построении Б-дерева со следующей последовательностью вставляемых ключей: 20;401030 15;35 7261822;5;4213 46 27 832; 38 244525; Точки с запятой указываюг моменты размещения новых страниц. Включение последнего ключа вызывает два расщепления и размещение трех новых страниц. Отметим особую роль в этой программе оператора присоединения тч!(п. Это видно уже в (4.83). В первую очередь он означает, что внутри оператора, перед которым стоит соответствующий заголовок, идентификаторы компонент (полей) страницы автоматически относятся к страцпце а [. Если реально страницы размещаются во внешней памяти, что, разумеется, необходимо в больших системах банков данных, то оператор тч1(п дополнительно означает передачу указанной страшщы в оперативную намять.
Поэтому каждое обращение к аеагсй предполагает размещение в оперативной памяти 287 4.5. Сильно ветвящиеся деревья одной страницы, всего же необходимо самое большее й = = )Однй) рЕКурСПВНЫХ ОбращЕНИй, СЛЕдОВатЕЛЬНО, ЕСЛИ дврево содержит Л5 этементов, мы должны иметь возможность рззместнть в оперативной памяти й страниц, Это накладывает 1е' )ь) 20 ЗО 40 1с) )й) )е) 8 7 8 (й Ряс.
4А8. Росс Ь.дереве горядяз 2 ограшшение на размер странпцы 2п, На самом деле нам нужно иметь возможность разместить даже больше, чем сс страниц, так как включение может вызвать их расщепление. Естественно, что корневую страницу лучше постоянно хранить в оперативной памяти, поскольку каждый поиск всегда начинасстс55 с корня. Еше одно положительное качество Б-деревьев — это пх удобство и экономичность в случае чисто последовательного ввв 4. Димаиинеские информационные стрингеры изменения всего банка данных.
При этом каждая страница вызывается в оперативную память ровно один раз. Удаление элементов из Б-дерева очень просто в общих чертах, но сложно з деталях. Мы можем выделить дпз различных случая: Элемент, который нужно удалить, находятся на страпнцелисге, тогда алгоритм удаления прост н очевиден. 2 Этот элемент не на странице-листе; тогда его нужно заменить иа один илп два лекспкографическп смежных элемента, которые находятся на страницах-листьях и которые легко удалить.
В случае 2 поиск смежного ключа аналогичен поиску такого же ключа при удалевии из бинарных деревьев. Мы спускаемся по самым правым указателям вниз к листу Р, заменяем удаляемый элемент на самый правый элемент Р н затем уменьшаем размер Р на 1. В любом случае после уменьшения размера нужно проверить число элементов ш на уменьшенной странице, так как, сслн сп и, будет нарушено основное свойство Б-деревьев. Если это произошло, нужно совершить некоторые дополнительнь:е действия; это условие недостатки обозначается булевской переменной-параметром А.
Единственный выход — одолжить плн отобрать элемент с одной из соседних страниц, а поскольку это требует вызова страницы Я в оперативную память — относительно дорогостоящей операцви, — то мы попытаемся наилучшим образом воспользоваться этой нежелательной ситуацией и заберем сразу больше одного элемента. Обычно элементы Р и О поровну распределяются на обе страницы. Это назь.вается балпнсйроакой. Разумеется, может оказаться, что с О нельзя забирать элементы, так как оиа тоже уже достигла своего минимального размера и.
В этом случае общее число элементов иа Р и Я разно 2п — 1, н мы можем слить эти две страшщы в одну, добавив средний элемент со страницы-предка Р и ф а затем можем полностью располагать страницей Я. Это — процесс, в точности обратный расгцеплению страниц. Его можно наблюдать, рассматривая удаление ключа 22 на рпс. 4.47. Удаление среднего ключа на странице-предке может вновь умен шить ее размер ниже допустимой границы и, требуя тем самым дальнейших специальных мер (балансг|ровки плн слияння1 на более высоком уровне. В экстремальном случае слияние страниц может распространиться по всему пути к корню.
Если корень уменьшается до размера О, оп удаляется, что вызывает уменьшение высоты Б-дерева. Это сдпнствснный случай, когда высота Б-д=рева может 1меиьшигься. 4.6. Сильно ветвящиеся оеревья На рнс. 4.49 показан постепенный распад Б-дерева с рис. 4.48 при последовательном удалении ключей: 25 45 24; 38 32; 8 27 46 13 42; 5 22 18 26; 7 35 15; Точки с запятой снова указывают места «скачков», т. е. освобождения страниц. Алгоритм удаления включен в программу (е) 1В 7 1О 12о ззо о ззв до 83 1то о20 Зово Рас.
4.49. Распад Б-дарсаа порядка 2. 4.7. Особенно примечательно его сходство с алгоритмом удаления из сбалансированного дерева. Йсчерпываюпгий анализ свойств Б-деревьев выполнсн в статье Бэйера и Мак-Крейта 14.21. В частности, в ней рас- ргорагв ВггееЦириг,ои)риг)„ )поиск, включение и удаление в Е-дереве» еоозг и = 2; пп = 4; [размер страничы» Фуре гег ' 7рауе; гует гесог4 Ьеу: Фп!ееег; р: геД свинг: тгееег еп4; ра4е =- гееог4 т: О., пп; [число элементов» рО: ггГ; е: аггау [1,,пп» о1дет,' ео4; чаг гвоЬ Д: гег; х: Фпге4ег; Ь: Ьао1еап; и: 12ет; ргоседиге хеагсЬ(х: тгееег; и: ге»; уаг Л: Ьао)еап; гаг о: Нет) 1 [ 17оиск ключа х в Б-дереве с корнем а; если найден, увеличение счетчика, иначе включение в дерево элемента с ключом х и счетчиком 1.
Если элемент должен передаваться на низизий уровень, присвоить его у; Ьз«дерево стало выше») эаг lг,),г: тгеаег; д: ге»'; и; ист; ргоседоге ихем; гаг 1: Фп!екег; Ь: геу. Ьед)о [ вкточение и справа огп а1, е[г) ) зг)Ф)г а; 4о Ье$)а)Фт < пп ФЬеп Ьев)о т:= т+1," Ь: = уаЬег зог Ф:= т 4оэгоФо г+2 до е[1»:= е[г' — Ц~ е[г+Ц:=- и еа4 е1зе ЬеК)а [страница а1 заполнена; расщепить ее и присвоить по лученный элемент у) пев[Ь); ФФ г ( п ФЬео Ье4)п 11 г == п Ф)геп о; =- и е)зе Ма!а о:= е[п):, 1ог 1:=- п 4оппФо г+2 4о с[1):= с[1-1»; е[г+Ц:= и еп4; Фог 1:= 1 Фо п 4о Ь).е[1»:= — а).е[[тп» еи4 е1зе ЬьФп [включение и в первую страницу) г:= г-и; о:= е[п+Ц: Фог 1:= 1 Фо г-1 4о Ь[,еЯ:= а»,е[1+и+Ц) Ь[,е[г»;= и Гог 1:= г+1 1о и йо Ь|.еЩ 1= а1 «11+п1 епд; т: — и; Ь1.т: п; Ь~.рО: е .р; е,р; Ь епй епй (ач1Ь1 епд (Ывг11 1 Ъей!п (поиск ключа х на странице а1; Ь-1а1ве1 11 а пй йка Ъей1п (элемента с ключом х нет в дереве1 Ь:=- ггие,' яйЬ е до Ъек1и ансер;= х; соип1: 1; р:= пй еий еид е1ее 'вйЬ а~ йо Ъей1п 1: 1; г: т; (двоичный поиск в массиве1 кереае Ф:= (1+г) д1« 2; П.' х е(Ц .Феу «Ь«п г ~= Й вЂ” 1; 11 х ~ сЯ .Фсу 1Ь«п 1;=* А+1; пп1йг <1; 11 1 — г > 1 1Ь«п Ъерп 1найдено1 «Я,соипс: — еЯ .свинг + 1; Ь 1 ЯаЫе епй е1ае Ъеи1п (элемента нет на этой странице1 11 г = 0 1Ь«п ц:= р0 е1ее ц: =- еЯ .р1 веагсБ(х,у,д,й11 К Ь 1Ьеп 1пгег1 «ий епа епд (веагсЬ1 1 ицей,' ')ноеейвге Ые!еге(х: 1игейег; а: ге1; чаг Ь: Ьоо!еап)! (поиск и Удаление ключа х в Б-дереве а если на странице не хватает элементов, то балансировка с соседней спцэан если это воэможно, иначе — слияние; Ь: = «на странице а не хватает элементов» ) чаг 1,Ь,!,г: 1игекег; ц: ге~; ргосейпге ипйегйом(с,а ге1; э; тгекег; чаг Ь: Ьоо!еап); (а-страница с нехваткой, с-страница-предок) чаг Ь: ге!; 1,ЬаиЬ,тс: 1игекег; Ьейш тс:= с!.т; (Ь = ггие, а[.щ = и — Ц И" э С тс йеп Ьей!и [Ь:=..страница справа от а) э:= э+!'! Ь:= с1.е[э).р; тЬ:= Ь[.т; 1с:= (тБ — п+1) й!» 21 (Ь-число элементов на соседней странице Ь) а[.е[и):= с[.е[4; а!.е[и) .р:= Ь),рО; !1Ь > Ойеп Ьеп!п (пересылка Ь элементвв с Ь на а) Еог 1:= 1 го 1с — 1 йо а).е[1+п):= 6(.е[1); с(.е[э):= Ь(.е[Ц; с[.е[э) .р:= Ь; Ь|.рО:= Ь(.е[Ц .р; тЬ:= тЬ вЂ” Ь; 1ог 1 .'= 1 Го тЬ йо Ь[.е[1):=' Ь).с[1+4; Ь(.т:= тЬ; а[.ги:= и — 1+А-, Ь:= (а!ге евй е!ае Ьек)п (слияние страниц а и Ь) [ Еог, 1:= 1 )о' и йо а+.с[1+и):=- Ь[,с[1); Ког 1.=.
э го тс — 1 йо с!.с[1):= с(.е[1+Ц; а[.т:= пп; с(.т;= тс — 1; [гЬвроэе(Ь)) Ь:= с1,тСи евй евй е!эе Бек!п (Ь:= сираницв слева от а) !! э = 1 йев Ь:= с).рО е)эе Ь:= с!.с[э — Ц .р; тЬ:= Ь(.т + 1; 1с:= (тЬ вЂ” и) й!ч 2; !!й ) Ойеп Бей(п (пересылка 1с элементов со страница Ь на а) Йи 1:= и — 1 йони!о 1 йо а[.е[1+Ц:= а[.с[1)," а[.е[Ь):= с(,е[г); а).е[Ь) .р:=- а!.рО; гиЬ:= тЬ Уае 1:= 1с-1 йово!о 1 йо а).е [1):= Ъ[.е[1+тЬ); а).рО:= Ь[.е[тЬ),р; с).е[э);= Ь1.е[тЬ); с).е[э) .р:= а; Ь!.т:= тЬ вЂ” 1; а[.т;= п — 1+!с; Ь:=,фа)гв евй е)ае ЬеФп (слияние странно а и Ь) Ь(.ЖИЬ):= сТ.е(е); ЬТ..е(тЬ),р '.= а(.рОс М 1.'= 1 Фо л-1 йо Ь~.е(1+тЬ):= «1.е(ф Ь|.т:= лп; ст,т:= тс — 1; (Яироее(а)) Ь:= сТ. <и епй евй (ын1еГ11«п) ргесейете ае1(р: ге1'; чее Ь: Ьоо1еап); чес д: ге~; 1глобальный а, Ь) Ъед(п йр'1 й Ъед1п д:= е(т1 .р; И д '~ ш1йеп Ъеп1п ае1(д,Ь); И Ь йеп ипае4оп(рд,т,Ь) епд еЬе ЪщпрТ.е(т) р:= «ТЖЧ р' «ЯЧ:= ИеИ' и;= т-1; Ь:= т<п ° еай еай еа| (йе1); Ъее(п (Яе1еге) И а = ш1йеа Ъерп егйе1п 1кеч гв нот ~н тяее); Ь:= ~а(ее епй еЬе чг(й «1 йо Ъеп(п 1:= 1; г:= т; (двоичный поиск в массиве) герееФ 1с: — (1+г) йч 2; И х ~ е~Ц .Ьеу ФЪеа г:= Ь вЂ” 1; И х; еЩ,Ьеу йеп 1: Ь+1; паИ11> г; И' г=О йеа д; рО еЬе д;= е(г) .р; И 1 — г > 1 йев Ъед(в '1найден, 'теперь удаление еЩ'1 И д = а6 йеп Ъед)в (а-термин«лен«в страница) т;*= т-1, Ь: дое1:* 1с ао т йо еД:= е(1+Ц; еай еЬе Ъефв йе!(д,Ь); И Ь йеп ипйегрою(ад,г,Ь) еш1 епй е1ее Ъеп1п ае1е1е(х,д,Ь); И Ь йеа ши3аЯ«гг(а,д,г,Ь) еай 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
