Войти
A B-heap - это двоичная куча реализован для хранения поддеревьев на одной странице . Это уменьшает количество страниц, к которым осуществляется доступ, до десяти раз для больших куч при использовании виртуальной памяти по сравнению с традиционной реализацией. Традиционное сопоставление элементов с местоположениями в массиве помещает почти каждый уровень на другую страницу.
Существуют и другие варианты кучи, которые эффективны на компьютерах, использующих виртуальную память или кеши, такие как алгоритмы без учета кеша, k-heaps и макеты ван Эмде Боаса.
Традиционно двоичный деревья располагаются в последовательной памяти в соответствии с правилом n ->{2n, 2n + 1}, что означает, что если узел находится в позиции n, его левый и правый дочерний элемент считается находящимся в позициях 2nи 2n + 1в массиве. Корень находится в позиции 1. Обычной операцией с бинарными деревьями является вертикальный обход; переход по уровням дерева вниз, чтобы добраться до искомого узла. Однако из-за того, как память на современных компьютерах организована в виде страниц в виртуальной памяти, такая схема построения двоичного дерева может быть крайне неэффективной. Причина в том, что, как и при углублении в дерево, расстояние до следующего узла растет экспоненциально, поэтому каждый следующий извлеченный узел, вероятно, будет на отдельной странице памяти. Это увеличит количество пропущенных страниц, что очень дорого. B-куча решает эту проблему, размещая дочерние узлы в памяти другим способом, стараясь как можно больше позиционировать поддеревья на одной странице. Следовательно, по мере вертикального обхода несколько последовательных извлекаемых узлов будут лежать на одной странице, что приведет к небольшому количеству пропусков страниц.
Подробно, b-куча может быть реализована следующим образом. Пол-Хеннинг Камп предлагает два варианта компоновки узлов: один, при котором две позиции на странице теряются, но сохраняется строгая двоичная структура дерева, и другой, который использует все доступное пространство страниц, но имеет дерево не может развернуться на один уровень при входе на новую страницу (узлы на этом уровне имеют только одного дочернего элемента). В любом случае важным моментом является то, что при выходе со страницы оба дочерних узла всегда находятся на общей другой странице, поскольку при вертикальном переходе алгоритм обычно сравнивает обоих дочерних узлов с родительским, чтобы знать, как действовать дальше. По этой причине можно сказать, что каждая страница содержит два параллельных поддерева, перемежающихся друг с другом. Сами страницы можно рассматривать как м-арное дерево, и поскольку половина элементов на каждой странице будут листьями (внутри страницы), «дерево страниц» имеет коэффициент разделения pagesize / 2.
В отличие от классической компоновки, подобной массиву, родительская функция в B-куче более сложна, потому что индекс родительского узла должен вычисляться по-разному в зависимости от того, где на странице это есть. Предполагая, что позиции внутри страницы помечены от 0 до размер страницы, родительская функция может быть следующей.
Для узлов 0 и 1 они используются только в варианте, который использует все возможное пространство. В этом случае родительский индекс обоих узлов одинаков, он находится на другой странице, и его конкретное смещение на этой странице зависит только от номера текущей страницы. В частности, чтобы вычислить номер родительской страницы, просто разделите номер страницы текущего узла на коэффициент разделения «дерева страниц», который равен размер страницы / 2. Чтобы получить правильное смещение внутри страницы, учтите, что это должен быть один из конечных узлов родительской страницы, поэтому начните со смещения размер страницы / 2. Затем добавьте разницу между номером текущей страницы и номером родительской страницы минус один, поскольку первая страница после родительской страницы имеет родительский узел в индексе (размер страницы / 2).
Для узлов 2 и 3 родительский элемент различается в зависимости от режима. В режиме экономии места родителями являются просто узлы 0 и 1 соответственно, поэтому достаточно вычесть только с 2. С другой стороны, в режиме строгого двоичного дерева эти узлы являются корнями страницы. из 0 и 1, поэтому их общий родительский элемент вычисляется так же, как описано выше.
Для всех остальных узлов их родительский элемент будет на той же странице, и достаточно разделить их смещение внутри их страницы на 2, не меняя номера страницы.
