Struttura degli indici di Firebird per Firebird 2.0 (ODS 11 e successive)
Struttura degli indici Firebird ODS11 e successive
La ragione di una nuova struttura è:
- migliore supporto per l’eliminazione di una chiave di indice tra molti duplicati (causava una lenta garbage collection)
- supporto per numeri di record più grandi di 32 bit (40 bit)
- aumento della dimensione della chiave di indice (1/4 della dimensione di pagina)
Struttura esistente (ODS10 e precedenti):
| header | node | node | node | node | node | node | |||
| node | node | node | node | node | node | node | … | end marker |
header =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // pagina sorella destra
SLONG btr\_left\_sibling; // pagina sorella sinistra
SLONG btr\_prefix\_total; // somma di tutti i prefissi sulla pagina
USHORT btr\_relation; // id della relazione per coerenza
USHORT btr\_length; // lunghezza dei dati nel bucket
UCHAR btr\_id; // id dell'indice per coerenza
UCHAR btr\_level; // livello dell'indice (0 = foglia)
struct btn btr\_nodes\[1.;
};
node =
struct btn {
UCHAR btn\_prefix; // dimensione del prefisso compresso
UCHAR btn\_length; // lunghezza dei dati nel nodo
UCHAR btn\_number\[4.; // numero di pagina o di record
UCHAR btn\_data\[1.;
};
end marker = END_BUCKET o END_LEVEL
Questi sono al posto del numero di record per i nodi foglia e al posto del numero di pagina per i nodi non foglia.
Se il nodo è un marcatore END_BUCKET, deve contenere gli stessi dati del primo nodo nella pagina sorella successiva.
Con un marcatore END_LEVEL, prefisso e lunghezza sono zero, quindi non contiene dati.
Inoltre, ogni primo nodo su un livello (eccetto le pagine foglia) contiene un nodo di degenerazione a lunghezza zero.
Nuova struttura ODS11:
| header | jump info | jump nodes | … | node [*] | node | node | |||
| node | node | node | node | node | node | node | … | end marker |
jump info =
struct IndexJumpInfo {
USHORT firstNodeOffset; // offset al primo nodo nella pagina \[\*\]
USHORT jumpAreaSize; // dimensione dell'area prima che venga creato un nuovo jumpnode
UCHAR jumpers; // numero di jump-node nella pagina, con un massimo di 255
};
jump node =
struct IndexJumpNode {
UCHAR\* nodePointer; // puntatore al punto in cui questo nodo può essere letto dalla pagina
USHORT prefix; // lunghezza del prefisso rispetto al jump node precedente
USHORT length; // lunghezza dei dati nel jump node (insieme al prefisso questo
è il prefisso per il nodo puntato)
USHORT offset; // offset al nodo nella pagina
UCHAR\* data; // I dati possono essere letti da qui
};
Nuovo flag per la nuova struttura dell’indice:
Nuovi flag vengono aggiunti a header->pag_flags.
Il flag btr_large_keys (32) serve per memorizzare lunghezza/prefisso compressi e numero di record. Questo significa anche che lunghezza e prefisso possono essere fino a 1/4 della dimensione di pagina (1024 per una dimensione di pagina di 4096) ed è facilmente estendibile in futuro senza modificare nuovamente la struttura su disco. Inoltre, il numero di record può essere facilmente esteso, ad esempio, a 40 bit. Questi numeri sono memorizzati per gruppi di 7 bit con 1 bit (il più alto) come marcatore (codifica a lunghezza variabile). Ogni nuovo byte che deve essere memorizzato viene spostato di 7. Esempi: 25 è memorizzato come 1 byte 0x19, 130 = 2 byte 0x82 0x01, 65535 = 3 byte 0xFF 0xFF 0x03.
Nodi duplicati:
Viene anche aggiunto un nuovo flag per memorizzare il numero di record su ogni nodo (pagine non foglia). Questo velocizza il recupero dell’indice su molti duplicati. Il flag è btr_all_recordnumber (16). Con queste informazioni aggiuntive, la ricerca della chiave su inserimenti/eliminazioni con molti duplicati (NULL nelle chiavi esterne, ad esempio) diventa molto più veloce (come la garbage collection!). Inoltre, i nodi duplicati (lunghezza = 0) non memorizzano le informazioni sulla loro lunghezza; 3 bit del primo byte memorizzato vengono usati per determinare se questo nodo è un duplicato. Oltre a ZERO_LENGTH (4), ci sono anche i marcatori END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) e ONE_LENGTH (5). I numeri 6 e 7 sono riservati per uso futuro.
Jump node:
Un jump node è un riferimento a un nodo da qualche parte nella pagina.
Contiene informazioni sull’offset del nodo specifico e i dati del prefisso del nodo referenziato, ma sui jump-node stessi viene anche applicata la compressione del prefisso.
Idealmente, un nuovo jump node viene generato dopo il primo nodo che si trova dopo ogni jumpAreaSize, ma questo accade solo quando si disattiva/attiva un indice o si inseriscono nodi nello stesso ordine in cui verranno memorizzati nell’indice.
Se i nodi vengono inseriti tra due riferimenti di jump node, vengono aggiornati solo gli offset, ma solo se gli offset non superano una soglia specifica (+/-10%).
Quando un nodo viene eliminato, vengono aggiornati solo gli offset o viene rimosso un jump node. Questo significa che può esistere un piccolo buco tra l’ultimo jump node e il primo nodo, così non si spreca tempo nella generazione di nuovi jump-node.
Il prefisso e la lunghezza sono anch’essi memorizzati con codifica a lunghezza variabile.
Dati di esempio:
(x) = dimensione in x byte
| header (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) | … |
Puntatore dopo l’header fisso = 0x22
Puntatore dopo le jump info = 0x29
Puntatore al primo jump node = 0x29 + 6 (jump node 1) + 5 (jump node 2) = 0x34
Il jump node 1 fa riferimento al nodo che rappresenta FIREBIRD come dati, poiché questo nodo ha un prefisso di 2, i primi 2 caratteri FI sono memorizzati anche sul jump node.
Il nostro prossimo jump node punta a un nodo che rappresenta FUEL con anche un prefisso di 2. Quindi il jump node 2 dovrebbe contenere FU, ma il nostro nodo precedente conteneva già la F, quindi a causa della compressione del prefisso questa viene ignorata e viene memorizzata solo la U.
Stato NULL:
I dati che devono essere memorizzati sono determinati nella procedura compress() in btr.cpp.
Per gli indici ASC (ascendenti) non verranno memorizzati dati (la chiave ha lunghezza zero). Questo li metterà automaticamente come prima voce nell’indice e quindi nell’ordine corretto (per un indice a campo singolo, lunghezza e prefisso del nodo sono zero).
Gli indici DESC (discendenti) memorizzeranno un singolo byte con il valore 0xFF (255). Per distinguere tra un valore (una stringa vuota può essere 255) e uno stato NULL, inseriamo un byte di 0xFE (254) all’inizio dei dati. Questo viene fatto solo per i valori che iniziano con 0xFF (255) o 0xFE (254), così manteniamo l’ordine corretto.
Esempi:
| nodi indice ASC, 1 segmento | |||
| prefisso | lunghezza | dati memorizzati | valore/stato reale |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| nodi indice DESC, 1 segmento | |||
| prefisso | lunghezza | dati memorizzati | valore/stato reale |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| nodi indice ASC, 3 segmenti | |||
| prefisso | lunghezza | dati memorizzati | valore/stato reale |
| 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 |
| … | … | … | … |
| nodi indice DESC, 3 segmenti | |||
| prefisso | lunghezza | dati memorizzati | valore/stato reale |
| 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