En informática , una matriz Judy es una estructura de datos que implementa un tipo de matriz asociativa con alto rendimiento y bajo uso de memoria. [1] A diferencia de la mayoría de otros almacenes de clave-valor , las matrices Judy no utilizan hash, aprovechan la compresión de sus claves (que pueden ser números enteros o cadenas) y pueden representar de manera eficiente datos dispersos; es decir, pueden tener grandes rangos de índices no asignados sin aumentar en gran medida el uso de memoria o el tiempo de procesamiento. Están diseñadas para seguir siendo eficientes incluso en estructuras con tamaños en el rango de petaelementos, con un escalado de rendimiento del orden de O(log n ). [2] En términos generales, las matrices Judy son árboles de radix 256-arios altamente optimizados . [3]
Los árboles Judy suelen ser más rápidos que los árboles AVL , los árboles B , las tablas hash y las listas de omisión porque están altamente optimizados para maximizar el uso de la memoria caché de la CPU . Además, no requieren ningún equilibrio de árboles y no se utiliza ningún algoritmo hash. [4]
El conjunto Judy fue inventado por Douglas Baskins y recibió el nombre de su hermana. [5]
Las matrices Judy son dinámicas y pueden crecer o reducirse a medida que se agregan o eliminan elementos de la matriz. La memoria que utilizan las matrices Judy es casi proporcional a la cantidad de elementos que contienen.
Las matrices Judy están diseñadas para minimizar la cantidad de costosos rellenos de líneas de caché desde la RAM , por lo que el algoritmo contiene mucha lógica compleja para evitar errores de caché con la mayor frecuencia posible. Debido a estas optimizaciones de caché , las matrices Judy son rápidas, especialmente para conjuntos de datos muy grandes. En conjuntos de datos que son secuenciales o casi secuenciales, las matrices Judy pueden incluso superar a las tablas hash, ya que, a diferencia de las tablas hash, la estructura de árbol interna de las matrices Judy mantiene el orden de las claves. [6]
Las matrices Judy son extremadamente complicadas. Las implementaciones más pequeñas son de miles de líneas de código. [5] Además, las matrices Judy están optimizadas para máquinas con líneas de caché de 64 bytes, lo que las hace esencialmente imposibles de transportar sin una reescritura significativa. [6]