B-куча

B -куча — это двоичная куча , реализованная для хранения поддеревьев на одной странице . Это уменьшает количество страниц, к которым осуществляется доступ, почти в десять раз для больших куч при использовании виртуальной памяти по сравнению с традиционной реализацией. ^[1] Традиционное сопоставление элементов с местоположениями в массиве помещает почти каждый уровень на отдельную страницу.

Существуют и другие варианты кучи, которые эффективны на компьютерах, использующих виртуальную память или кэши, например алгоритмы, не учитывающие кэш , k-кучи, ^[2] и макеты ван Эмде Боаса . ^[3]

Мотивация

Традиционно бинарные деревья располагаются в последовательной памяти в соответствии с n -> {2n, 2n+1} правило, означающее, что если узел находится в позиции n, его левый и правый дочерние элементы считаются находящимися в позициях 2n и 2n+1 в массиве. Корень находится в позиции 1. Обычной операцией с двоичными деревьями является вертикальный обход; переход вниз по уровням дерева, чтобы добраться до искомого узла. Однако из-за того, как память на современных компьютерах организована в страницы виртуальной памяти, такая схема построения двоичного дерева может оказаться крайне неэффективной. Причина в том, что, как и при более глубоком перемещении по дереву, расстояние до следующего узла растет экспоненциально, поэтому каждый следующий полученный узел, скорее всего, будет находиться на отдельной странице памяти. Это увеличит количество промахов страниц , что очень дорого обходится.B-куча решает эту проблему, по-другому размещая дочерние узлы в памяти, стараясь как можно больше расположить поддеревья в пределах одной страницы. Следовательно, по мере вертикального обхода несколько последовательно извлеченных узлов будут лежать на одной странице, что приведет к небольшому количеству промахов страниц.

Выполнение

Подробно, b-куча может быть реализована следующим образом. Пол-Хеннинг Камп ^[4] дает два варианта расположения узлов: один, при котором две позиции на странице теряются, но сохраняется строгая двоичная структура дерева, и другой, при котором используется все доступное пространство страниц, но дерево не расширяется. для одного уровня при входе на новую страницу (узлы на этом уровне имеют только одного дочернего элемента). В любом случае важным моментом является то, что при выходе со страницы оба дочерних узла всегда находятся на общей другой странице, поскольку при вертикальном обходе алгоритм обычно сравнивает обоих дочерних узлов с родительским, чтобы знать, как действовать дальше. По этой причине можно сказать, что каждая страница содержит два параллельных поддерева, перемежающихся друг с другом. Сами страницы можно рассматривать как m-арное дерево , и поскольку половина элементов на каждой странице будут листьями (внутри страницы), «дерево страниц» имеет коэффициент разделения pagesize/2.

Родительская функция

В отличие от классического макета, подобного массиву, родительская функция в B-куче более сложна, поскольку индекс родительского узла должен вычисляться по-разному в зависимости от того, где он находится на странице. Предполагая, что позиции внутри страницы помечены от 0 до pagesize, родительская функция может быть следующей.

Для узлов 0 и 1 они используются только в варианте, в котором используется все возможное пространство. В этом случае родительский индекс обоих узлов один и тот же, он находится на другой странице, и его конкретное смещение внутри этой страницы зависит только от номера текущей страницы. В частности, чтобы вычислить номер родительской страницы, просто разделите номер страницы текущего узла на коэффициент разделения «дерева страниц», который равен pagesize/2. Чтобы получить правильное смещение внутри страницы, учтите, что это должен быть один из конечных узлов родительской страницы, поэтому начните со смещения. pagesize/2. Затем добавьте разницу между текущим номером страницы и номером родительской страницы минус один, поскольку первая страница после родительской страницы имеет родительский узел в индексе ( pagesize/2).

Для узлов 2 и 3 родительский элемент различается в зависимости от режима. В режиме экономии места родительскими узлами являются просто узлы 0 и 1 соответственно, поэтому нужно вычитать только 2. С другой стороны, в режиме строгого двоичного дерева эти узлы вместо этого являются корнями страницы. из 0 и 1, поэтому их общий родитель вычисляется так же, как описано выше.

Для всех остальных узлов их родитель будет находиться в пределах той же страницы, и достаточно разделить их смещение внутри своей страницы на 2, не меняя номер страницы.

См. также

D-ичная куча

Ссылки

^ Камп, Пол-Хеннинг (26 июля 2020 г.). «Ты делаешь это неправильно» . Очередь АКМ .
^ Наор, Далит; Мартель, Чарльз У.; Матлофф, Норман С. (1991). «Производительность структур очереди приоритетов в среде виртуальной памяти». Вычислить. Дж. 34 (5): 428–437. дои : 10.1093/comjnl/34.5.428 .
^ ван Эмде Боас, П .; Каас, Р.; Зийлстра, Э. (1976). «Проектирование и реализация эффективной очереди приоритетов». Теория математических систем . 10 : 99–127. дои : 10.1007/BF01683268 . S2CID 8105468 .
^ Камп, Пол-Хеннинг. «Ты делаешь это неправильно» . phk.freebsd.dk . Проверено 8 июня 2019 г.

Внешние ссылки

Реализации на https://github.com/varnish/Varnish-Cache/blob/master/lib/libvarnish/binary_heap.c и http://phk.freebsd.dk/B-Heap/binheap.c.
Общая реализация кучи с поддержкой B-кучи .
Дополнительную информацию о макетах ван Эмде Боаса см. в разделе Benjamin Sach Descent to Cache-Oblivion или Cache-Oblivion Structures data .

[:0-1] Камп, Пол-Хеннинг (26 июля 2020 г.). «Ты делаешь это неправильно» . Очередь АКМ .

[2] Наор, Далит; Мартель, Чарльз У.; Матлофф, Норман С. (1991). «Производительность структур очереди приоритетов в среде виртуальной памяти». Вычислить. Дж. 34 (5): 428–437. дои : 10.1093/comjnl/34.5.428 .

[3] ван Эмде Боас, П .; Каас, Р.; Зийлстра, Э. (1976). «Проектирование и реализация эффективной очереди приоритетов». Теория математических систем . 10 : 99–127. дои : 10.1007/BF01683268 . S2CID 8105468 .

[4] Камп, Пол-Хеннинг. «Ты делаешь это неправильно» . phk.freebsd.dk . Проверено 8 июня 2019 г.

[1]

[2]

[3]

[4]