Tries y árboles B para claves grandes
Un trie comparte prefijos entre cadenas y un árbol B agrupa muchas claves por nodo. Ambos adaptan la búsqueda a un costo que un ABB binario no modela bien.
Para este tema conviene tener claro:Árboles binarios de búsqueda
No toda búsqueda está dominada por la cantidad de claves. Con texto importa cuántos caracteres leemos; con disco importa cuántos bloques transferimos. Tries y árboles B nacen de optimizar esas dos realidades distintas.
El trie: la clave es un camino
Un trie representa una clave como un camino de caracteres o símbolos. Las palabras sol,
solo y sopa comparten el camino inicial so; después se ramifican. Un marcador indica
qué nodos terminan una clave válida.
Buscar una palabra de longitud cuesta si acceder al hijo correspondiente es constante. El costo depende de la longitud consultada, no directamente de cuántas palabras guarda el conjunto.
El trie con sol, solo y sopa. Cada arista es un carácter y cada camino desde la raíz, un prefijo.
Antes de seguir, predecí
Buscar por prefijo sale natural
Para buscar por prefijo seguimos sus caracteres y, si el camino existe, recorremos las claves que cuelgan de ese nodo. Esto hace naturales el autocompletado, los diccionarios y el ruteo por prefijos.
El precio es memoria: cada nodo puede necesitar referencias a muchos símbolos y los nodos poco poblados desperdician espacio. Mapas dispersos, tries comprimidos y árboles Patricia reducen ese costo agrupando caminos sin ramificaciones.
El árbol B resuelve otro cuello de botella
Un árbol B resuelve otro cuello de botella. En almacenamiento secundario, leer un bloque es mucho más caro que comparar varias claves ya cargadas. En vez de dos hijos por nodo, guarda muchas claves ordenadas y muchos hijos dentro de cada bloque.
Un nodo con claves divide el espacio en rangos. Una búsqueda elige el rango correcto con comparaciones locales y realiza muy pocos saltos entre bloques.
Ramificación alta, árbol bajo
El alto factor de ramificación produce árboles muy bajos. Si cada nodo tiene cientos de hijos, unas pocas lecturas alcanzan para indexar millones de registros. Todos los nodos hoja quedan a la misma profundidad, por lo que las búsquedas tienen un costo predecible.
La complejidad asintótica sigue siendo logarítmica, pero la base grande del logaritmo refleja la optimización real: reducir accesos a disco o páginas de memoria.
Dividir un nodo lleno y promover
Al insertar en un nodo lleno, el árbol B lo divide y promueve una clave separadora al padre. La división puede propagarse hasta la raíz; si la raíz se divide, la altura aumenta uno. Al borrar, nodos con pocas claves pueden pedir prestado a un hermano o fusionarse.
Estas operaciones conservan ocupación mínima y hojas al mismo nivel. Son más complejas que las rotaciones binarias porque mueven grupos de claves, no sólo enlaces individuales.
Cada uno explota algo distinto
El trie explota la estructura interna de cadenas y responde prefijos. El árbol B explota el tamaño de bloque del almacenamiento y mantiene claves generales ordenadas. Un ABB compara claves completas y toma una decisión binaria por nodo.
Las bases de datos y sistemas de archivos suelen usar variantes B o B+; routers y motores de autocompletado aprovechan variantes de tries. Elegir depende de cuál operación física domina.
Dos formas de no ser un árbol binario
| Trie | Árbol B+ | Tabla hash | |
|---|---|---|---|
| Buscar una clave | O(largo de la clave) | O(log n) con base grande | O(1) promedio |
| Buscar por prefijo | natural: es su razón de ser | sí, si el índice empieza por ahí | no puede |
| Recorrer en orden | sí | sí, y las hojas están enlazadas | no puede |
| Memoria | mucha: un nodo por carácter | compacta: una página por nodo | media |
| Dónde vive | en memoria: autocompletado, enrutadores | en disco: índices de bases y sistemas de archivos | en memoria |
Los dos resuelven lo mismo que un ABB y dejan de ser binarios por motivos opuestos. El trie abre un hijo por símbolo del alfabeto para que la búsqueda no dependa de cuántas claves hay, sino de cuán larga es la clave. El árbol B abre cientos de hijos por nodo para que la altura sea de tres o cuatro, porque cada nivel cuesta un acceso a disco y ésa es la única unidad que importa.
Más a fondo · nivel seniorPor qué el disco cambia la estructura
Leer un byte de disco o leer cuatro kilobytes cuesta prácticamente lo mismo, porque el costo está en llegar, no en transferir. Esa asimetría es lo único que hace falta para explicar el árbol B.
Con un ABB de un millón de claves, la altura es 20, y como cada nodo puede estar en cualquier parte del disco, son 20 accesos. Con un árbol B+ donde cada nodo es una página de cuatro kilobytes y entra un centenar de claves, la altura baja a 3: la raíz y el segundo nivel están casi siempre en memoria, así que la consulta real es un acceso a disco.
Es la misma estructura de datos con otro parámetro, y la diferencia de rendimiento es de un orden de magnitud. La lección general vale más que el caso: cuando cambia la unidad de costo —de la operación al acceso, del acceso a la llamada por red—, la estructura óptima cambia con ella, aunque la complejidad asintótica diga lo mismo.
Lo que preguntan sobre esto
Cierre
Un trie convierte caracteres compartidos en caminos compartidos. Un árbol B convierte cada lectura costosa en muchas decisiones locales. No son versiones exóticas del mismo árbol: optimizan modelos de costo diferentes, longitud de clave y acceso por bloques.
Autoevaluación
¿Lo entendiste?
Práctica