Организация внешнего поиска с помощью Б-деревьев.

Данный способ употребляет понятие двоичного дерева поиска, но видоизменит это понятие таким макаром, что дерево получает страничную компанию. Потому Б-деревья нередко именуют деревьями со страничной организацией.

Представим, что мы желаем организовать в оперативки дерево поиска с очень огромным числом вершин (миллионы и поболее). Пусть при всем этом свободной ОП не Организация внешнего поиска с помощью Б-деревьев. довольно для одновременного хранения сходу всех вершин. Часть (и при том очень значимая) вершин должна оставаться на диске. Появляется задачка таковой организации дерева, чтоб можно было считывать и обрабатывать сходу группу вершин. Такая группа вершин получила заглавие “страничка”. Тем, все сверхбольшое дерево поиска разбивается на ряд страничек и чтение вершин Организация внешнего поиска с помощью Б-деревьев. с диска производится постранично. Это позволяет значительно уменьшить количество воззваний к наружной памяти.

В качестве примера разглядим обыденное дерево поиска из 15 вершин. Пусть для простоты оно является совершенно равновесным. Выделим в нем 5 простых поддеревьев по 3 верхушки в каждом и логически объединим эти верхушки совместно в виде страничек. Если Организация внешнего поиска с помощью Б-деревьев. в дереве нужно отыскать какую-либо терминальную верхушку, и верхушки считываются в ОП по одной, то для этого в обыкновенном дереве будет нужно 4 воззвания к наружной памяти. А в дереве со страничной организацией будет нужно считать из наружной памяти только 2 странички – корневую и одну из терминальных. Даже в этом простом примере страничная Организация внешнего поиска с помощью Б-деревьев. организация дерева позволяет уменьшить число воззваний к диску вдвое. Для сверхбольших деревьев этот эффект становится еще больше приметным.


Для действенной страничной организации сверхбольшого дерева поиска очень принципиальным условием является равномерность его роста, наибольшее соответствие безупречной сбалансированности. К огорчению, условие безупречной сбалансированности приводит к очень сложным методам, потому Байером и было Организация внешнего поиска с помощью Б-деревьев. введено понятие дерева со страничной организацией (Б-дерево).

Б-дерево порядка m со страничной организацией - это структура данных, удовлетворяющая последующим условиям:

· весь набор из n частей разбивается на отдельные странички, при этом любая страничка может содержать от m до 2m вершин, кроме корневой странички, для которой число вершин Организация внешнего поиска с помощью Б-деревьев. может изменяться от 1 до 2m

· любая страничка является или терминальной (потомков нет), или имеет ровно на 1-го потомка больше по сопоставлению с текущим числом вершин на этой страничке

· все терминальные странички находятся на этом же уровне

Пример. Разглядим простейшее Б-дерево порядка m=2 с ключами целого типа. В согласовании с приведенными выше правилами Организация внешнего поиска с помощью Б-деревьев., любая страничка такового дерева содержит от 2 до 4 вершин, а корневая – от 1 до 4. Любая нетерминальная страничка может иметь от 3 до 5 потомков. Пример дерева – на рисунке (к огорчению, терминальные странички приходится располагать на различных уровнях).


Так как Б-дерево является обобщением традиционного дерева поиска, то оно обладает последующими качествами:

· на каждой Организация внешнего поиска с помощью Б-деревьев. страничке элементы упорядочены по возрастанию ключей

· любая страничка–потомок содержит ключи в строго определенном спектре, который задается родительскими ключами

Последнее свойство является обобщением основного правила дерева поиска. К примеру, страничка с ключами 40, 50 и 60 имеет 4 потомков, при этом самый левый потомок содержит ключи меньше 40 (но больше 30), более правая страничка содержит ключи в спектре от 40 до Организация внешнего поиска с помощью Б-деревьев. 50, еще больше правая – в спектре от 50 до 60, а самая правая – больше 60.

Эффективность использования Б-дерева для поиска ключей в сверхбольших наборах данных можно оценить последующим образом.. Если Б-дерево имеет порядок m, а число частей – n, то самым наихудшим случаем будет случай, когда на каждой страничке находится мало Организация внешнего поиска с помощью Б-деревьев. вероятное число частей, а конкретно - m. В данном случае высота Б-дерева определяется величиной logmn, а конкретно высота и определяет количество воззваний к наружной памяти.

К примеру, если число частей в наборе данных n = 1 миллион, а порядок Б-дерева m = 100, то log1001000000 = 3, т.е. максимум может потребоваться 3 воззвания к наружной Организация внешнего поиска с помощью Б-деревьев. памяти. С другой стороны, даже в этом наихудшем случае оперативка употребляется довольно отлично (приблизительно половина памяти от заявленного объема).


organizaciya-vzaimodejstviya-s-rabotodatelyami-b-a-kugan-rektor-gaou-dpo-irost-d-p-n-professor.html
organizaciya-vzaimodejstviya-v-seti-internet.html
organizaciya-yazikovoj-podderzhki-v-mezhdunarodnih-peregovorah.html