Un montón B es un montón binario implementado para mantener subárboles en una sola página . Esto reduce la cantidad de páginas a las que se accede hasta en un factor de diez para montones grandes cuando se usa memoria virtual , en comparación con la implementación tradicional. [1] La asignación tradicional de elementos a ubicaciones en una matriz coloca casi cada nivel en una página diferente.
Existen otras variantes de montón que son eficientes en computadoras que usan memoria virtual o cachés, como algoritmos que ignoran el caché , k-heaps, [2] y diseños de van Emde Boas . [3]
Tradicionalmente, los árboles binarios se disponen en la memoria consecutiva según una n -> {2n, 2n+1}regla, lo que significa que si un nodo está en la posición n, sus hijos izquierdo y derecho se toman como si estuvieran en las posiciones 2ny 2n+1en la matriz. La raíz está en la posición 1. Una operación común en los árboles binarios es el recorrido vertical; descender a través de los niveles de un árbol para llegar a un nodo buscado. Sin embargo, debido a la forma en que se organiza la memoria en las computadoras modernas en páginas en la memoria virtual, este esquema de diseño del árbol binario puede ser altamente ineficaz. La razón es que, como al recorrer más profundamente el árbol, la distancia al siguiente nodo crece exponencialmente, por lo que cada próximo nodo recuperado probablemente estará en una página de memoria separada. Esto aumentará el número de fallas de página , que son muy costosas. El B-heap resuelve este problema al disponer los nodos secundarios en la memoria de una manera diferente, tratando tanto como sea posible de ubicar 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 estarán en la misma página, lo que dará lugar a un bajo número de errores de página.
En detalle, un b-heap puede implementarse de la siguiente manera. Poul-Henning Kamp [4] da dos opciones para la disposición 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 hace que el árbol no se expanda por un nivel al entrar en 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 hijos siempre están en otra página común, ya que en una transversal vertical el algoritmo típicamente comparará 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 como la mitad de los elementos en 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.
A diferencia del diseño clásico de tipo 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 en qué parte de la página 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 explota todo el espacio posible. En este caso, el índice padre 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 del padre, simplemente divida el número de página del nodo actual por el factor de división del "árbol de páginas", 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 padre, 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 del padre, menos uno ya que la primera página después de la página padre tiene su nodo padre en el índice ( 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 es necesario restar 2. Por otro lado, en el modo de árbol binario estricto, estos nodos son las raíces de la página en lugar de 0 y 1, por lo que su padre común se calcula de la misma manera que se describió 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.