ART Árboles de Prefijos: Optimización de Memoria y Caché

Optimizando árboles de prefijos: de 825 MB a 18 MB para autocompletar

Un trie para buscar 50.000 comandos consumía 825 MB de memoria y era 8 veces más lento que una tabla hash (4,8 millones de ciclos frente a 600K). Cada nodo ocupaba 2.064 bytes con un array de 256 punteros, causando frecuentes fallos en la caché durante las búsquedas.

El benchmark perf stat reveló 125K fallos en caché frente a solo 18K en la tabla hash. Buscar una cadena de 5 caracteres provocaba 5 fallos porque cada nodo no cabía en una única línea de caché.

Estructura de nodos y uso de memoria

Implementación estándar de nodo:

typedef struct trie_node {
    struct trie_node *children[256];  // 2048 bytes
    void *value;                      // 8 bytes
    bool is_end;                      // 1 byte
    // Total: 2064 bytes
} trie_node_t;

Para un conjunto de datos de 50K comandos (longitud promedio de 8 caracteres), se necesitaban ~400K nodos—825 MB frente a solo 1,2 MB de una tabla hash, una diferencia de 687×.

Tries compactos: compresión de cadenas

Solución: Tries compactos (tries Patricia), donde las cadenas de nodos con un único hijo se comprimen en prefijos. Los nodos almacenan cadenas de prefijo en lugar de caracteres individuales.

typedef struct radix_node {
    char *prefix;
    int prefix_len;
    struct radix_node *children[256];
    void *value;
} radix_node_t;

Algoritmo de búsqueda:

void* radix_search(radix_node_t *node, const char *key) {
    while (node) {
        int i = 0;
        while (i < node->prefix_len && key[i] == node->prefix[i]) {
            i++;
        }
        if (i < node->prefix_len) return NULL;
        if (key[i] == '\0') return node->value;
        node = node->children[(unsigned char)key[i]];
        key += i + 1;
    }
    return NULL;
}

Resultado: la memoria bajó a 330 MB, los ciclos a 2,4M y los fallos en caché a 6,8—aumento de velocidad del 2×.

Árboles radicales adaptativos (ART)

El problema persistía: el 98% de los arrays de 256 punteros estaban vacíos. Solución: nodos adaptativos basados en el número de hijos.

• Node4 (1–4 hijos): 40 bytes
• Node16 (5–16 hijos): 152 bytes
• Node48 (17–48 hijos): 640 bytes
• Node256 (49+ hijos): 2048 bytes

Estrategia de crecimiento: Node4 → Node16 → Node48 → Node256 cuando se superan los límites.

Tamaño promedio de nodo: 40–152 bytes frente a 2048—ahorro de memoria de 10 a 50×.

Resultados de pruebas

Comparación en 1 millón de búsquedas sobre 50K comandos:

| Estructura | Memoria | Ciclos | Fallos en caché | Mejora |

|-----------|--------|--------|----------------|--------|

| Trie | 825 MB | 4.800 | 12,5 | 1× |

| Radix | 330 MB | 2.400 | 6,8 | 2× |

| ART | 18 MB | 1.200 | 3,2 | 4× |

| Hash | 1,2 MB | 600 | 1,8 | 8× |

ART es 45× más compacto que el trie estándar; los nodos Node4/Node16 caben en 1–2 líneas de caché.

Casos de uso para árboles de prefijos

Usa ART cuando necesites operaciones de prefijo:

• Autocompletado: recorrido del subárbol en O(k + m), donde m es el número de coincidencias. Las tablas hash requieren escaneo completo.
• Enrutamiento IP: coincidencia de prefijo más largo por bits de dirección.
• Corrección ortográfica: búsqueda mediante distancia de edición usando prefijos.
• Arreglos dispersos: como se usa en el kernel de Linux (caché de páginas, IDR, XArray).

Evita usarlo para búsquedas exactas, conjuntos pequeños (<1.000 elementos) o cadenas sin prefijos compartidos.

Tries compactos en el kernel de Linux

El kernel utiliza radix_tree_node con 64 ranuras (6 bits por nivel). Para un índice de 32 bits, son 6 niveles—~6 fallos en caché frente a 32 del árbol binario de búsqueda.

Ventajas:

• Soporte para operaciones de rango
• Complejidad predecible O(log₆₄ n)
• Eficiente para datos dispersos

Conclusiones clave

• Los tries estándar usan 687× más memoria por los arrays de 256 punteros
• ART reduce la memoria a 18 MB y los fallos en caché a 3,2 gracias a nodos adaptativos
• Usa para consultas de prefijo; las tablas hash ganan en búsquedas exactas
• Los tries compactos comprimen cadenas, ofreciendo un aumento de velocidad del 2×
• El kernel de Linux los usa para arreglos dispersos y asignación de IDs

— Editorial Team