Formato de archivo de índice compacto de Visual FoxPro

Question

Estoy tratando de entender el formato de archivo de un índice compacto de Visual FoxPro (* .IDX). Actualmente me refiero a documentación de Microsoft para orientación .

El índice es un árbol B de nodos de 512 bytes. Cada nodo de hoja (" exterior ") contiene varias entradas. Cada entrada consta de cuatro datos:

• Número de fila [LONGITUD FIJA]
• Recuento de bytes duplicados (la documentación no explica esto) [LONGITUD FIJA]
• Recuento de bytes al final (la documentación no explica esto) [LONGITUD FIJA]
• Tecla [LONGITUD VARIABLE]

Las entradas (sin sus claves) se almacenan al principio del nodo, inmediatamente después del encabezado de 24 bytes del nodo. Sus claves no se incluyen en esta ubicación porque las claves varían en longitud, mientras que el número de fila, el conteo de bytes duplicados y los conteos de bytes finales son fijos en longitud. Las claves se almacenan al final del nodo y avanzan hacia atrás. Por ejemplo:

• encabezado de 24 bytes
• número de fila, recuento de bytes duplicados, recuento de bytes remanentes (entrada # 1)
• número de fila, recuento de bytes duplicados, recuento de bytes remanentes (entrada n.º 2)
• número de fila, recuento de bytes duplicados, recuento de bytes remanentes (entrada # 3)
• ...
• clave (entrada # 3)
• clave (entrada # 2)
• clave (entrada # 1)

¿Cómo puedo determinar las longitudes individuales de las teclas? La documentación no parece especificar esto. Son perfectamente contiguos (sin separadores de nulos).

Puedo aislar las teclas manualmente mediante inspección visual. Sospeché que el conteo de bytes al final representaba la longitud de la clave. Sin embargo, no se correlacionó con las longitudes determinadas por esta inspección.

Creo que los formatos de archivo FoxPro se derivan del estándar xBase. Tal vez esto suena una campana?

Answer 1

Después de descubrir el módulo XBase :: Index Perl, he determinado que las claves en el nodo exterior tienen efectivamente la misma longitud que las claves de longitud fija que se encuentran en los nodos interiores, excepto que se eliminan los espacios finales. Eso es lo que el " número de bytes final " mencionado en la documentación se refiere a (cuántos espacios finales se truncaron al final de la clave). Todavía no he determinado cuál es el " recuento de bytes duplicados " es, pero el módulo al menos aclaró su relación:

variable_key_length = fixed_key_length - duplicate_byte_count - trailing_byte_count

Por ejemplo, supongamos que la longitud de clave fija para este índice era de 10 bytes. Ahora suponga que la clave "PERRO" fue almacenado en un nodo externo. Su recuento de bytes duplicados (según lo que he observado) probablemente será cero, mientras que su recuento de bytes posterior será 7 (el número de espacios truncados). Por lo tanto, solo los tres bytes que representan " DOG " sería almacenado.

Answer 2

Sobre el recuento de bytes duplicados: esto significa el número de primeros bytes, que son los mismos en la clave actual y en la clave anterior. La primera entrada de clave almacenada al final del nodo tiene una longitud completa, excepto los espacios en blanco finales; la entrada de clave sucesiva solo tiene símbolos diferentes de la entrada de clave anterior.

Answer 3

En Xbase, la indexación rara vez supera los 10 caracteres o 15 (raramente) cuando se usan índices (índices que analizan textos).

En cualquier caso, si sabe cuál es el número de claves, se divide proporcionalmente la porción binaria. Cuando crea un algoritmo que almacena datos, o almacena los datos usando: marcadores o pestañas iniciales o finales, o deja un tamaño estático para que no lo deje en blanco. El formato estático es menos eficiente pero proporciona mayor velocidad en la lectura y, obviamente, genera estructuras más predecibles.

Answer 4

Microsoft dice esto sobre el IDX estructura de archivos (y en la parte inferior de la página hay enlaces a todos los demás, como Formato de índice compacto .)