Un montón B es un montón binario implementado para mantener subárboles en una sola página . Esto reduce el número de páginas a las que se accede hasta en un factor de diez para grandes montones cuando se usa memoria virtual , en comparación con la implementación tradicional. [1] El mapeo tradicional de elementos a ubicaciones en una matriz coloca casi todos los niveles en una página diferente.
Hay otras variantes de montón que son eficientes en computadoras que usan memoria virtual o cachés, como algoritmos que ignoran caché , k-heaps, [2] y diseños de van Emde Boas . [3]
Motivación
Tradicionalmente, los árboles binarios se colocan en la memoria consecutiva de acuerdo con una n -> {2n, 2n+1}
regla, lo que significa que si un nodo está en la posición n
, su hijo izquierdo y derecho se toman para estar en las posiciones 2n
y 2n+1
en la matriz. La raíz está en la posición 1. Una operación común en árboles binarios es el recorrido vertical; bajar a través de los niveles de un árbol para llegar a un nodo buscado. Sin embargo, debido a la forma en que la memoria está organizada en las computadoras modernas en páginas en la memoria virtual, este esquema de diseñar el árbol binario puede ser muy ineficaz. La razón es que, como cuando se atraviesa más profundamente en el árbol, la distancia al siguiente nodo crece exponencialmente, por lo que cada nodo siguiente recuperado probablemente estará en una página de memoria separada. Esto aumentará el número de páginas perdidas , que son muy caras. El B-heap resuelve este problema colocando los nodos secundarios en la memoria de una manera diferente, tratando tanto como sea posible de colocar los subárboles dentro de una sola página. Por lo tanto, a medida que avanza un recorrido vertical, varios de los nodos recuperados consecutivos se colocarán en la misma página, lo que provocará un número reducido de páginas perdidas.
Implementación
En detalle, un b-heap se puede implementar de la siguiente manera. Poul-Henning Kamp [4] ofrece dos opciones para el diseño de los nodos: una en la que se desperdician dos posiciones por página, pero se conserva la estructura binaria estricta del árbol, y otra que utiliza todo el espacio disponible de las páginas. pero el árbol no se expande en un nivel al ingresar a una nueva página (los nodos en ese nivel tienen solo un hijo). En cualquier caso, un punto importante es que al salir de una página, ambos nodos hijo están siempre en una otra página común, ya que en una transversal vertical el algoritmo normalmente comparará a ambos hijos con el padre para saber cómo proceder. Por esta razón, se puede decir que cada página contiene dos subárboles paralelos, intercalados entre sí. Las páginas en sí pueden verse como un árbol m-ario , y dado que la mitad de los elementos de cada página serán hojas (dentro de la página), el "árbol de páginas" tiene un factor de división de pagesize/2
.
Función principal
En contraste con el diseño clásico similar a una matriz, la función principal en un montón B es más compleja porque el índice del padre de un nodo debe calcularse de manera diferente según el lugar de la página en el que se encuentre. Suponiendo que las posiciones dentro de una página están etiquetadas de 0 a pagesize
, la función principal puede ser la siguiente.
Para los nodos 0 y 1, estos solo se utilizan en la variante que está explotando todo el espacio posible. En este caso, el índice principal de ambos nodos es el mismo, está en una página diferente y su desplazamiento específico dentro de esa página solo depende del número de página actual. Específicamente, para calcular el número de página principal, simplemente divida el número de página del nodo actual por el factor de división del "árbol de página", que es pagesize/2
. Para obtener el desplazamiento correcto dentro de la página, considere que debe ser uno de los nodos hoja dentro de la página principal, así que comience en el desplazamiento pagesize/2
. Luego, agregue la diferencia entre el número de página actual y el número de página principal, menos uno, ya que la primera página después de la página principal tiene su nodo principal en index ( pagesize/2
).
Para los nodos 2 y 3, el padre es diferente según el modo. En el modo de ahorro de espacio, los padres son simplemente los nodos 0 y 1, respectivamente, por lo que solo se necesita restar con 2. Por otro lado, en el modo de árbol binario estricto, estos nodos son las raíces de la página. de 0 y 1, por lo que su padre común se calcula de la misma manera que se describe anteriormente.
Para todos los demás nodos, su padre estará dentro de la misma página, y es suficiente dividir su desplazamiento dentro de su página por 2, sin cambiar el número de página.
Ver también
Referencias
- ↑ Kamp, Poul-Henning (26 de julio de 2020). "Lo estás haciendo mal" . Cola de ACM .
- ^ Naor, Dalit; Martel, Charles U .; Matloff, Norman S. (1991). "Rendimiento de estructuras de cola de prioridad en un entorno de memoria virtual" . Computación. J. 34 (5): 428–437. doi : 10.1093 / comjnl / 34.5.428 .
- ^ van Emde Boas, P .; Kaas, R .; Zijlstra, E. (1976). "Diseño e implementación de una cola prioritaria eficiente". Teoría de sistemas matemáticos . 10 : 99-127. doi : 10.1007 / BF01683268 .
- ^ phk.freebsd.dk http://phk.freebsd.dk/B-Heap/ . Consultado el 8 de junio de 2019 . Falta o vacío
|title=
( ayuda )
enlaces externos
- Las implementaciones en https://github.com/varnish/Varnish-Cache/blob/master/lib/libvarnish/binary_heap.c y http://phk.freebsd.dk/B-Heap/binheap.c
- Implementación de pila genérica con soporte B-heap .
- Para obtener más información sobre los diseños de van Emde Boas, consulte Benjamin Sach Descent into Cache-Oblivion o Estructuras de datos Cache-inconscientes .