PostgreSQL incluye una implementación de índices hash persistentes en disco, los cuales son completamente recuperables ante fallos. Cualquier tipo de datos puede ser indexado por un índice hash, incluyendo tipos de datos que no tienen un orden lineal bien definido. Los índices hash almacenan solo el valor hash de los datos indexados, por lo que no hay restricciones en el tamaño de la columna de datos indexada.

Los índices hash solo soportan índices de una sola columna y no permiten la verificación de unicidad.

Los índices hash solo soportan el operador =, por lo que las cláusulas WHERE que especifican operaciones de rango no podrán aprovechar los índices hash.

Cada tupla del índice hash almacena solo el valor hash de 4 bytes, no el valor real de la columna. Como resultado, los índices hash pueden ser mucho más pequeños que los B-trees al indexar elementos de datos más largos como UUIDs, URLs, etc. La ausencia del valor de la columna también hace que todos los escaneos de índices hash sean con pérdida (lossy). Los índices hash pueden participar en escaneos de índices por mapa de bits (bitmap index scans) y escaneos hacia atrás (backward scans).

Los índices hash están optimizados para cargas de trabajo con un alto uso de SELECT y UPDATE que utilizan escaneos de igualdad en tablas grandes. En un índice B-tree, las búsquedas deben descender a través del árbol hasta encontrar la página hoja. En tablas con millones de filas, este descenso puede aumentar el tiempo de acceso a los datos. El equivalente a una página hoja en un índice hash se denomina página de bucket (bucket page). En contraste, un índice hash permite acceder directamente a las páginas de bucket, lo que reduce potencialmente el tiempo de acceso al índice en tablas más grandes. Esta reducción en la "E/S lógica" (logical I/O) se vuelve aún más pronunciada en índices/datos más grandes que shared_buffers/RAM.

Los índices hash han sido diseñados para lidiar con distribuciones desiguales de valores hash. El acceso directo a las páginas de bucket funciona bien si los valores hash están distribuidos uniformemente. Cuando las inserciones hacen que la página de bucket se llene, se encadenan páginas de desbordamiento (overflow pages) adicionales a esa página de bucket específica, expandiendo localmente el almacenamiento para las tuplas del índice que coinciden con ese valor hash. Al escanear un bucket hash durante las consultas, necesitamos escanear todas las páginas de desbordamiento. Por lo tanto, un índice hash desbalanceado podría ser de hecho peor que un B-tree en términos de cantidad de accesos a bloques requeridos para algunos datos.

Como resultado de los casos de desbordamiento, podemos decir que los índices hash son más adecuados para datos únicos, casi únicos, o datos con un bajo número de filas por bucket hash. Una forma posible de evitar problemas es excluir los valores altamente no únicos del índice utilizando una condición de índice parcial, pero esto puede no ser adecuado en muchos casos.

Al igual que los B-trees, los índices hash realizan una eliminación simple de tuplas de índice. Esta es una operación de mantenimiento diferida que elimina las tuplas de índice que se sabe que es seguro eliminar (aquellas cuyo bit LP_DEAD del identificador de elemento ya está establecido). Si una inserción encuentra que no hay espacio disponible en una página, intentamos evitar la creación de una nueva página de desbordamiento tratando de eliminar las tuplas de índice muertas. La eliminación no puede ocurrir si la página está fijada (pinned) en ese momento. La eliminación de punteros de índice muertos también ocurre durante VACUUM.

Si puede, VACUUM también intentará compactar las tuplas del índice en el menor número posible de páginas de desbordamiento, minimizando la cadena de desbordamiento. Si una página de desbordamiento queda vacía, las páginas de desbordamiento se pueden reciclar para su reutilización en otros buckets, aunque nunca las devolvemos al sistema operativo. Actualmente no existe ninguna disposición para reducir el tamaño de un índice hash, excepto reconstruyéndolo con REINDEX. Tampoco existe disposición para reducir el número de buckets.

Los índices hash pueden expandir el número de páginas de bucket a medida que crece el número de filas indexadas. El mapeo de clave hash a número de bucket se elige de manera que el índice pueda expandirse incrementalmente. Cuando se va a agregar un nuevo bucket al índice, exactamente un bucket existente necesitará ser "dividido" (split), y algunas de sus tuplas se transferirán al nuevo bucket de acuerdo con el mapeo actualizado de clave a número de bucket.

La expansión ocurre en primer plano (foreground), lo que podría aumentar el tiempo de ejecución de las inserciones de los usuarios. Por lo tanto, los índices hash pueden no ser adecuados para tablas con un número de filas que aumenta rápidamente.

Hay cuatro tipos de páginas en un índice hash: la metapágina (página cero), que contiene información de control asignada estáticamente; páginas de bucket primarias; páginas de desbordamiento (overflow pages); y páginas de mapa de bits (bitmap pages), que realizan un seguimiento de las páginas de desbordamiento que se han liberado y están disponibles para su reutilización. A efectos de direccionamiento, las páginas de mapa de bits se consideran un subconjunto de las páginas de desbordamiento.

Tanto el escaneo del índice como la inserción de tuplas requieren localizar el bucket donde debería ubicarse una tupla dada. Para hacer esto, necesitamos la cantidad de buckets, el highmask y el lowmask de la metapágina; sin embargo, por razones de rendimiento, no es deseable tener que bloquear y fijar la metapágina para cada operación de este tipo. En su lugar, mantenemos una copia almacenada en caché de la metapágina en la entrada relcache de cada backend. Esto producirá el mapeo de bucket correcto siempre que el bucket objetivo no se haya dividido desde la última actualización de la caché.

Las páginas de bucket primarias y las páginas de desbordamiento se asignan de forma independiente, ya que cualquier índice dado podría necesitar más o menos páginas de desbordamiento en relación con su número de buckets. El código hash utiliza un conjunto interesante de reglas de direccionamiento para soportar un número variable de páginas de desbordamiento sin tener que mover las páginas de bucket primarias después de que se crean.

Cada fila de la tabla indexada está representada por una sola tupla en el índice hash. Las tuplas del índice hash se almacenan en páginas de bucket y, si existen, en páginas de desbordamiento. Aceleramos las búsquedas manteniendo las entradas del índice en cualquier página de índice ordenadas por código hash, lo que permite utilizar la búsqueda binaria dentro de una página de índice. Ten en cuenta, sin embargo, que *no* se asume nada sobre el orden relativo de los códigos hash entre diferentes páginas de índice de un bucket.

Los algoritmos de división de buckets para expandir el índice hash son demasiado complejos para ser mencionados aquí, aunque se describen con más detalle en src/backend/access/hash/README. El algoritmo de división es seguro ante fallos y se puede reiniciar si no se completó con éxito.