Hashing Extendible

Este esquema de hashing funciona, en promedio, cuando se almacenan $N = O(MB)$ datos en total, es decir, unas miles de veces el tamaño de la memoria principal. Inicialmente, la estructura es una única página en disco, $H$, donde los datos se insertan de cualquier manera, al costo de $O(1)$ I/Os (o incluso gratis si la tenemos en memoria principal). Las búsquedas se hacen leyendo la página $H$ y buscando secuencialmente la clave que se desea.

Una vez que esta página se llena, la siguiente inserción provoca que la dividamos en dos, $H_0$ y $H_1$. Para ello, releemos cada dato $y$ de $H$ y calculamos $h(y)$. Según el primer bit de $h(y)$ sea $0$ ó $1$, insertamos el elemento en $H_0$ o $H_1$, respectivamente. Luego, creamos un nodo en memoria principal con dos hijos: el izquierdo apunta a la página de disco donde almacenamos $H_0$, y el derecho a la de $H_1$. Supongamos que, más adelante, la página de $H_0$ rebalsa por una inserción. Recorreremos todos los elementos $y$ de $H_0$ y consideraremos el segundo bit de $h(y)$ para separar los elementos en dos hojas, $H_{00}$ y $H_{01}$. La hoja de $H_0$ se reemplazará entonces por un nodo interno, cuyos hijos izquierdo y derecho serán, respectivamente, $H_{00}$ y $H_{01}$.

En general, tendremos un árbol en memoria de tipo trie (que volveremos a ver en el capítulo de universos discretos), con $k-1$ nodos y $k$ hojas, donde cada hoja almacena datos en una página de disco. Las búsquedas por una clave $x$ parten por calcular $h(x)$, y usan sus bits para recorrer el trie, desde la raíz hasta llegar a una hoja. En ese momento leen la página correspondiente del disco y buscan $x$ secuencialmente entre las claves. El costo de búsqueda es, en principio, siempre de 1 lectura, y el de inserción agrega 1 ó 2 escrituras.

Note que, cuando se divide una página, no hay garantía de que la división sea equitativa. Una hoja podría quedar con más elementos que la otra. Esto significa que no hay una ocupación mínima garantizada, y que en particular no podemos garantizar que la cantidad de nodos del trie es $O(k)=O(N/B)$. Es decir, con mala suerte se nos podría acabar la memoria disponible para un $N$ mucho menor que $\Theta(MB)$. En promedio, sin embargo, si consideramos que los valores $h(y)$ son aleatorios, las páginas estarán llenas a un 69%.

Incluso podría ocurrir que, al dividir una página, todas las claves se fueran a una de las dos páginas. En ese caso, no se necesita crear una página vacía en disco. Basta que el puntero desde el árbol sea nulo para indicar esa situación, y deberemos volver a particionar la otra página, que continuará rebalsada, todas las veces que sea necesario. Note que, aún en este caso, realizamos solamente 2 escrituras a disco.

También puede ocurrir que la página que rebalsa ya sea de profundidad $|h(y)|$, es decir, que ya se hayan usado todos los bits de la función de hashing. Esto equivale a decir que tenemos más de una página de elementos que colisionan en el hash provisto por $h(\cdot)$. Si bien esto no debería ocurrir con una $h(\cdot)$ bien diseñada, debe haber una provisión para este caso. Lo que se hace es tener una lista enlazada de las páginas que rebalsan en el último nivel. Por ello, si la función $h(\cdot)$ produce una colisión entre $t$ elementos, que requerirían tiempo $O(t)$ para buscarse en memoria principal, el costo en disco será $O(\lceil t/B\rceil)$ lecturas.

Finalmente, para borrar un elemento, debe encontrarse su página y eliminarlo. Luego de esto, puede ocurrir que la página quede vacía, en cuyo caso se elimina y el puntero en el árbol se hace nulo. Más probable, sin embargo, es el caso en que el nodo hermano en el árbol también sea una hoja y que ambas quepan en una sola. En este caso se pueden unir y reemplazar el nodo padre de ambas páginas por la página unida. Esta unión puede hacerse exigiendo que la nueva página esté, por ejemplo, $\frac{2}{3}$ llena, para evitar secuencias de uniones y divisiones muy seguidas para una página que almacena cerca de $B$ elementos y sufre inserciones y borrados consecutivos. Asismismo, debe verificarse que la nueva página no tenga como hermano un puntero nulo, ya que en ese caso se puede reemplazar al nodo padre por la hoja creada. Esto puede ocurrir repetidamente para varios ancestros de la página creada. En total, sin embargo, un borrado requiere de 1 ó 2 lecturas y 1 escritura.