Estrutura de Índice do Firebird para Firebird 2.0 (ODS 11 e superior)
Estrutura de Índice do Firebird ODS11 e superior
A razão para uma nova estrutura é:
- melhor suporte para excluir uma chave de índice entre muitas duplicatas (causava coleta de lixo lenta)
- suporte a números de registro maiores que 32 bits (40 bits)
- aumentar o tamanho da chave de índice (1/4 do tamanho da página)
Estrutura existente (ODS10 e inferior):
| cabeçalho | nó | nó | nó | nó | nó | nó | |||
| nó | nó | nó | nó | nó | nó | nó | … | marcador final |
cabeçalho =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // página irmã direita
SLONG btr\_left\_sibling; // página irmã esquerda
SLONG btr\_prefix\_total; // soma de todos os prefixos na página
USHORT btr\_relation; // id da relação para consistência
USHORT btr\_length; // comprimento dos dados no bucket
UCHAR btr\_id; // id do índice para consistência
UCHAR btr\_level; // nível do índice (0 = folha)
struct btn btr\_nodes\[1.;
};
nó =
struct btn {
UCHAR btn\_prefix; // tamanho do prefixo compactado
UCHAR btn\_length; // comprimento dos dados no nó
UCHAR btn\_number\[4.; // número da página ou do registro
UCHAR btn\_data\[1.;
};
marcador final = END_BUCKET ou END_LEVEL
Estes estão no lugar do número do registro para nós folha e no lugar do número da página para nós não folha.
Se o nó é um marcador END_BUCKET, então ele deve conter os mesmos dados que o primeiro nó na próxima página irmã.
Por um marcador END_LEVEL, prefixo e comprimento são zero, portanto não contém dados.
Além disso, todo primeiro nó em um nível (exceto páginas folha) contém um nó de degeneração de comprimento zero.
Nova estrutura ODS11:
| cabeçalho | info de salto | nós de salto | … | nó [*] | nó | nó | |||
| nó | nó | nó | nó | nó | nó | nó | … | marcador final |
info de salto =
struct IndexJumpInfo {
USHORT firstNodeOffset; // deslocamento para o primeiro nó na página \[\*\]
USHORT jumpAreaSize; // tamanho da área antes de um novo nó de salto ser criado
UCHAR jumpers; // nº de nós de salto na página, com um máximo de 255
};
nó de salto =
struct IndexJumpNode {
UCHAR\* nodePointer; // ponteiro para onde este nó pode ser lido da página
USHORT prefix; // comprimento do prefixo contra o nó de salto anterior
USHORT length; // comprimento dos dados no nó de salto (junto com o prefixo isto
é o prefixo para o nó apontado)
USHORT offset; // deslocamento para o nó na página
UCHAR\* data; // Os dados podem ser lidos daqui
};
Nova flag para a nova estrutura de índice:
Novas flags são adicionadas ao header->pag_flags.
A flag btr_large_keys (32) é para armazenar comprimento/prefixo compactado e número do registro. Isso também significou que comprimento e prefixo podem ser de até 1/4 do tamanho da página (1024 para tamanho de página 4096) e é facilmente extensível no futuro sem alterar a estrutura do disco novamente. Também o número do registro pode ser facilmente estendido para, por exemplo, 40 bits. Esses números são armazenados em grupos de 7 bits com 1 bit (o mais alto) como marcador (codificação de comprimento variável). Cada novo byte que precisa ser armazenado é deslocado por 7. Exemplos: 25 é armazenado como 1 byte 0x19, 130 = 2 bytes 0x82 0x01, 65535 = 3 bytes 0xFF 0xFF 0x03.
Nós duplicados:
Também uma nova flag é adicionada para armazenar o número do registro em todo nó (páginas não folha). Isso acelera a recuperação do índice em muitas duplicatas. A flag é btr_all_recordnumber (16). Com esta informação adicionada, a busca de chave em inserções/exclusões com muitas duplicatas (NULLs em chaves estrangeiras, por exemplo) torna-se muito mais rápida (como a coleta de lixo!). Além disso, nós duplicados (comprimento = 0) não armazenam suas informações de comprimento; 3 bits do primeiro byte armazenado são usados para determinar se este nó é uma duplicata. Além do marcador ZERO_LENGTH (4), há também END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) e ONE_LENGTH (5). Os números 6 e 7 são reservados para uso futuro.
Nós de salto:
Um nó de salto é uma referência a um nó em algum lugar da página.
Ele contém informações de deslocamento sobre o nó específico e os dados de prefixo do nó referenciado, mas nos próprios nós de salto também é feita compactação de prefixo.
Idealmente, um novo nó de salto é gerado após o primeiro nó que é encontrado após cada jumpAreaSize, mas isso só é o caso ao desativar/ativar um índice ou inserir nós na mesma ordem em que serão armazenados no índice.
Se nós são inseridos entre duas referências de nós de salto, apenas os deslocamentos são atualizados, mas somente se os deslocamentos não excederem um limite específico (+/-10 %).
Quando um nó é excluído, apenas os deslocamentos são atualizados ou um nó de salto é removido. Isso significa que um pequeno buraco pode existir entre o último nó de salto e o primeiro nó, para não perdermos tempo gerando novos nós de salto.
O prefixo e o comprimento também são armazenados por codificação de comprimento variável.
Exemplo de dados:
(x) = tamanho em x bytes
| cabeçalho (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) | … |
Ponteiro após o cabeçalho fixo = 0x22
Ponteiro após a info de salto = 0x29
Ponteiro para o primeiro nó de salto = 0x29 + 6 (nó de salto 1) + 5 (nó de salto 2) = 0x34
O nó de salto 1 está referenciando o nó que representa FIREBIRD como dados, porque este nó tem um prefixo de 2; os primeiros 2 caracteres FI também são armazenados no nó de salto.
Nosso próximo nó de salto aponta para um nó que representa FUEL com também um prefixo de 2. Assim, o nó de salto 2 deveria conter FU, mas nosso nó anterior já continha o F, então devido à compactação de prefixo este é ignorado e apenas U é armazenado.
Estado NULL:
Os dados que precisam ser armazenados são determinados no procedimento compress() em btr.cpp.
Para índices ASC (ascendentes), nenhum dado será armazenado (a chave tem comprimento zero). Isso os colocará automaticamente como primeira entrada no índice e, portanto, na ordem correta (para índice de campo único, comprimento e prefixo do nó são zero).
Índices DESC (descendentes) armazenarão um único byte com o valor 0xFF (255). Para distinguir entre um valor (string vazia pode ser 255) e um estado NULL, inserimos um byte de 0xFE (254) no início dos dados. Isso é feito apenas para valores que começam com 0xFF (255) ou 0xFE (254), para mantermos a ordem correta.
Exemplos:
| nós índice ASC, 1 segmento | |||
| prefixo | comprimento | dados armazenados | valor/estado real |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| nós índice DESC, 1 segmento | |||
| prefixo | comprimento | dados armazenados | 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 |
| nós índice ASC, 3 segmentos | |||
| prefixo | comprimento | dados armazenados | 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 |
| … | … | … | … |
| nós índice DESC, 3 segmentos | |||
| prefixo | comprimento | dados armazenados | 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