Estructura de Índices de Firebird para Firebird 2.0 (ODS 11 y superiores)
Estructura de Índices de Firebird ODS11 y superiores
La razón de una nueva estructura es:
- mejor soporte para eliminar una clave de índice entre muchos duplicados (causaba una recolección de basura lenta)
- soporte para números de registro más grandes que 32 bits (40 bits)
- aumentar el tamaño de la clave de índice (1/4 del tamaño de página)
Estructura existente (ODS10 e inferiores):
| cabecera | nodo | nodo | nodo | nodo | nodo | nodo | |||
| nodo | nodo | nodo | nodo | nodo | nodo | nodo | … | marcador final |
cabecera =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // página hermana derecha
SLONG btr\_left\_sibling; // página hermana izquierda
SLONG btr\_prefix\_total; // suma de todos los prefijos en la página
USHORT btr\_relation; // id de relación para consistencia
USHORT btr\_length; // longitud de datos en el bucket
UCHAR btr\_id; // id de índice para consistencia
UCHAR btr\_level; // nivel de índice (0 = hoja)
struct btn btr\_nodes\[1.;
};
nodo =
struct btn {
UCHAR btn\_prefix; // tamaño del prefijo comprimido
UCHAR btn\_length; // longitud de datos en el nodo
UCHAR btn\_number\[4.; // número de página o registro
UCHAR btn\_data\[1.;
};
marcador final = END_BUCKET o END_LEVEL
Estos están en lugar del número de registro para nodos hoja y en lugar del número de página para nodos no hoja.
Si el nodo es un marcador END_BUCKET, debe contener los mismos datos que el primer nodo de la siguiente página hermana.
Con un marcador END_LEVEL, el prefijo y la longitud son cero, por lo que no contiene datos.
Además, cada primer nodo en un nivel (excepto páginas hoja) contiene un nodo de longitud cero de degeneración.
Nueva estructura ODS11:
| cabecera | info de salto | nodos de salto | … | nodo [*] | nodo | nodo | |||
| nodo | nodo | nodo | nodo | nodo | nodo | nodo | … | marcador final |
info de salto =
struct IndexJumpInfo {
USHORT firstNodeOffset; // desplazamiento al primer nodo en la página \[\*\]
USHORT jumpAreaSize; // tamaño del área antes de crear un nuevo nodo de salto
UCHAR jumpers; // número de nodos de salto en la página, con un máximo de 255
};
nodo de salto =
struct IndexJumpNode {
UCHAR\* nodePointer; // puntero a donde este nodo puede leerse desde la página
USHORT prefix; // longitud del prefijo contra el nodo de salto anterior
USHORT length; // longitud de datos en el nodo de salto (junto con el prefijo esto
es el prefijo para el nodo apuntado)
USHORT offset; // desplazamiento al nodo en la página
UCHAR\* data; // Los datos pueden leerse desde aquí
};
Nueva bandera para la nueva estructura de índice:
Se añaden nuevas banderas a header->pag_flags.
La bandera btr_large_keys (32) es para almacenar longitud/prefijo comprimidos y número de registro. Esto también significó que la longitud y el prefijo pueden ser de hasta 1/4 del tamaño de página (1024 para un tamaño de página de 4096) y es fácilmente extensible en el futuro sin cambiar la estructura de disco nuevamente. También el número de registro puede extenderse fácilmente a, por ejemplo, 40 bits. Esos números se almacenan por cada 7 bits con 1 bit (el más alto) como marcador (codificación de longitud variable). Cada nuevo byte que necesita almacenarse se desplaza por 7. Ejemplos: 25 se almacena como 1 byte 0x19, 130 = 2 bytes 0x82 0x01, 65535 = 3 bytes 0xFF 0xFF 0x03.
Nodos duplicados:
También se añade una nueva bandera para almacenar el número de registro en cada nodo (páginas no hoja). Esto acelera la recuperación de índices con muchos duplicados. La bandera es btr_all_recordnumber (16). Con esta información añadida, la búsqueda de claves en inserciones/eliminaciones con muchos duplicados (NULLs en claves foráneas, por ejemplo) se vuelve mucho más rápida (¡como la recolección de basura!). Además, los nodos duplicados (longitud = 0) no almacenan su información de longitud; se usan 3 bits del primer byte almacenado para determinar si este nodo es un duplicado. Además de ZERO_LENGTH (4), también existen los marcadores END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) y ONE_LENGTH (5). Los números 6 y 7 están reservados para uso futuro.
Nodos de salto:
Un nodo de salto es una referencia a un nodo en algún lugar de la página.
Contiene información de desplazamiento sobre el nodo específico y los datos de prefijo del nodo referenciado, pero en los propios nodos de salto también se realiza compresión de prefijo.
Idealmente, se genera un nuevo nodo de salto después del primer nodo que se encuentra después de cada jumpAreaSize, pero eso solo ocurre al desactivar/activar un índice o al insertar nodos en el mismo orden en que se almacenarán en el índice.
Si se insertan nodos entre dos referencias de nodos de salto, solo se actualizan los desplazamientos, pero solo si los desplazamientos no exceden un umbral específico (+/-10 %).
Cuando se elimina un nodo, solo se actualizan los desplazamientos o se elimina un nodo de salto. Esto significa que puede existir un pequeño hueco entre el último nodo de salto y el primer nodo, para no perder tiempo generando nuevos nodos de salto.
El prefijo y la longitud también se almacenan mediante codificación de longitud variable.
Datos de ejemplo:
(x) = tamaño en x bytes
| cabecera (34) | ||||
| 52 (2) | 256 (2) | 2 (1) | 30 (2) | 0 (1) |
| 2 (1) | 260 (2) | FI (2) | 1 (1) | 1 (1) |
| 514 (2) | U (1) | 0 (1) | 1 (1) | 0 (1) |
| A (1) | … | |||
| 2 (1) | 6 (1) | 21386 (3) | REBIRD (6) | … |
| 2 (1) | 2 (1) | 1294 (2) | EL (2) | … |
Puntero después de la cabecera fija = 0x22
Puntero después de la info de salto = 0x29
Puntero al primer nodo de salto = 0x29 + 6 (nodo de salto 1) + 5 (nodo de salto 2) = 0x34
El nodo de salto 1 referencia al nodo que representa FIREBIRD como datos, porque este nodo tiene un prefijo de 2; los primeros 2 caracteres FI también se almacenan en el nodo de salto.
Nuestro siguiente nodo de salto apunta a un nodo que representa FUEL con también un prefijo de 2. Por lo tanto, el nodo de salto 2 debería contener FU, pero nuestro nodo anterior ya contenía la F, por lo que debido a la compresión de prefijo esta se ignora y solo se almacena U.
Estado NULL:
Los datos que necesitan almacenarse se determinan en el procedimiento compress() en btr.cpp.
Para índices ASC (ascendentes), no se almacenarán datos (la clave tiene longitud cero). Esto los colocará automáticamente como primera entrada en el índice y, por lo tanto, en el orden correcto (para índices de campo único, la longitud y el prefijo del nodo son cero).
Los índices DESC (descendentes) almacenarán un solo byte con el valor 0xFF (255). Para distinguir entre un valor (una cadena vacía puede ser 255) y un estado NULL, insertamos un byte de 0xFE (254) al frente de los datos. Esto solo se hace para valores que comienzan con 0xFF (255) o 0xFE (254), para mantener el orden correcto.
Ejemplos:
| nodos índice ASC, 1 segmento | |||
| prefijo | longitud | datos almacenados | valor/estado real |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| nodos índice DESC, 1 segmento | |||
| prefijo | longitud | datos almacenados | valor/estado real |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| nodos índice ASC, 3 segmentos | |||
| prefijo | longitud | datos almacenados | valor/estado real |
| 0 | 0 | NULL,NULL, NULL | |
| 0 | 10 | x01(1) x70(F) x73(I) x82(R) x69(E) x01(1) x66(B) x73(I) x82(R) x68(D) | NULL, NULL, FIREBIRD |
| 0 | 10 | x02(2) x70(F) x73(I) x82(R) x69(E) x02(2) x66(B) x73(I) x82(R) x68(D) | NULL, FIREBIRD, NULL |
| 0 | 10 | x03(3) x70(F) x73(I) x82(R) x69(E) x03(3) x66(B) x73(I) x82(R) x68(D) | FIREBIRD, NULL, NULL |
| 3 | 9 | x00(0) x00(0) x02(2) x65(A) x00(0) x00(0) x00(0) x01(1) x66(B) | FI, A, B |
| … | … | … | … |
| nodos índice DESC, 3 segmentos | |||
| prefijo | longitud | datos almacenados | valor/estado real |
| 0 | 12 | xFC xB9 xB6 xFF xFF xFD xBE xFF xFF xFF xFE xBD | FI, A, B |
| 3 | 17 | xAD xBA xFC xBD xB6 xAD xBB xFD xFF xFF xFF xFF xFE xFF xFF xFF xFF | FIREBIRD, NULL, NULL |
| 1 | 19 | xFF xFF xFF xFF xFD xB9 xB6 xAD xBA xFD xBD xB6 xAD xBB xFE xFF xFF xFF xFF | NULL, FIREBIRD, NULL |
| 6 | 14 | xFF xFF xFF xFF xFE xB9 xB6 xAD xBA xFE xBD xB6 xAD xBB | NULL, NULL, FIREBIRD |
| 11 | 4 | xFF xFF xFF xFF | NULL,NULL, NULL |
| END_LEVEL |
c ABVisie 2005, Arno Brinkman