data structures - ¿Entendiendo los árboles de fusión?
data-structures tree (3)
Me topé con la página de Wikipedia para ellos:
Y leí los pdfs de notas de clase vinculados en la parte inferior, pero se pone muy claro acerca de la estructura de datos en sí y entra en muchos detalles sobre la función de sketch(x) . Creo que parte de mi confusión es que los documentos están tratando de ser muy generales, y me gustaría un ejemplo específico para visualizar.
¿Es esta estructura de datos adecuada para almacenar datos basados en claves enteras arbitrarias de 32 o 64 bits? ¿En qué se diferencia de un árbol B? Hay una sección que dice que es básicamente un árbol B con un factor de bifurcación B = (lg n)^(1/5) . Para un árbol completamente poblado con claves de 32 bits, B sería 2. ¿Se convierte esto simplemente en un árbol binario? ¿Está esta estructura de datos destinada a usar cadenas de bits mucho más largas como claves?
Mi búsqueda en Google no me pareció nada útil, pero agradecería cualquier buen enlace sobre el tema. Esto es realmente solo una curiosidad pasajera, por lo que no he estado dispuesto a pagar los archivos PDF en portal.acm.org todavía.
He leído (solo un pase rápido) el artículo seminal y me parece interesante. También responde la mayoría de tus preguntas en la primera página.
Puede descargar el documento desde here
HTH!
He leído el papel del árbol de fusión. Las ideas son bastante inteligentes, y en términos de notación O puede hacer un caso para una victoria.
No me queda claro que sea una victoria en la práctica. El factor constante importa mucho, y los diseñadores de chips trabajan muy duro para gestionar referencias locales baratas.
Tiene que tener B en sus árboles B falsos bastante pequeños para máquinas reales (B = 5 para 32 bits, quizás 10 para 64 bits). Que muchos punteros encajan más o menos en una línea de caché. Después del primer toque de línea de caché (que no puede evitar) de varios cientos de ciclos, puede hacer una búsqueda lineal a través de las teclas en unos pocos ciclos por tecla, lo que significa que una implementación tradicional de B-tree cuidadosamente codificada parece Debería superar los árboles de fusión. (He creado dicho código de árbol B para admitir nuestro sistema de transformación de programas).
Él reclama una lista de aplicaciones, pero no hay números comparativos.
¿Alguien tiene alguna evidencia? (¿Implementaciones y comparaciones?)
La idea detrás del árbol de fusión es bastante simple. Supongamos que tiene teclas w-bit (por ejemplo, 64 bits), la idea es comprimir (es decir, dibujar) cada 64 teclas consecutivas en una matriz de 64 elementos. La función de boceto asegura una asignación de tiempo constante entre las claves originales y el índice de matriz para un grupo determinado. Luego, buscar la clave se convierte en buscar el grupo que contiene la clave, que es O (log (n / 64)). Como puede ver, el principal desafío es la función de boceto.