Structure des index Firebird pour Firebird 2.0 (ODS 11 et supérieur)
Structure des index Firebird ODS11 et versions ultérieures
La raison d’une nouvelle structure est :
- meilleure prise en charge de la suppression d’une clé d’index parmi de nombreux doublons (causait une lente collecte des déchets)
- prise en charge de numéros d’enregistrement plus grands que 32 bits (40 bits)
- augmentation de la taille des clés d’index (1/4 de la taille de page)
Structure existante (ODS10 et versions antérieures) :
| en-tête | nœud | nœud | nœud | nœud | nœud | nœud | |||
| nœud | nœud | nœud | nœud | nœud | nœud | nœud | … | marqueur de fin |
en-tête =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // page sœur droite
SLONG btr\_left\_sibling; // page sœur gauche
SLONG btr\_prefix\_total; // somme de tous les préfixes sur la page
USHORT btr\_relation; // identifiant de relation pour la cohérence
USHORT btr\_length; // longueur des données dans le seau
UCHAR btr\_id; // identifiant d'index pour la cohérence
UCHAR btr\_level; // niveau d'index (0 = feuille)
struct btn btr\_nodes\[1.;
};
nœud =
struct btn {
UCHAR btn\_prefix; // taille du préfixe compressé
UCHAR btn\_length; // longueur des données dans le nœud
UCHAR btn\_number\[4.; // numéro de page ou d'enregistrement
UCHAR btn\_data\[1.;
};
marqueur de fin = END_BUCKET ou END_LEVEL
Ceux-ci sont utilisés à la place du numéro d’enregistrement pour les nœuds feuilles et à la place du numéro de page pour les nœuds non-feuilles.
Si le nœud est un marqueur END_BUCKET, il doit contenir les mêmes données que le premier nœud de la page sœur suivante.
Pour un marqueur END_LEVEL, le préfixe et la longueur sont nuls, il ne contient donc aucune donnée.
De plus, chaque premier nœud d’un niveau (sauf les pages feuilles) contient un nœud de dégénérescence de longueur nulle.
Nouvelle structure ODS11 :
| en-tête | infos de saut | nœuds de saut | … | nœud [*] | nœud | nœud | |||
| nœud | nœud | nœud | nœud | nœud | nœud | nœud | … | marqueur de fin |
infos de saut =
struct IndexJumpInfo {
USHORT firstNodeOffset; // décalage vers le premier nœud de la page \[\*\]
USHORT jumpAreaSize; // taille de zone avant qu'un nouveau nœud de saut soit créé
UCHAR jumpers; // nombre de nœuds de saut dans la page, avec un maximum de 255
};
nœud de saut =
struct IndexJumpNode {
UCHAR\* nodePointer; // pointeur vers l'endroit où ce nœud peut être lu depuis la page
USHORT prefix; // longueur du préfixe par rapport au nœud de saut précédent
USHORT length; // longueur des données dans le nœud de saut (avec le préfixe, cela
est le préfixe pour le nœud pointé)
USHORT offset; // décalage vers le nœud dans la page
UCHAR\* data; // Les données peuvent être lues à partir d'ici
};
Nouveau drapeau pour la nouvelle structure d’index :
De nouveaux drapeaux sont ajoutés aux pag_flags de l’en-tête.
Le drapeau btr_large_keys (32) sert à stocker la longueur/le préfixe compressés et le numéro d’enregistrement. Cela signifie également que la longueur et le préfixe peuvent atteindre 1/4 de la taille de page (1024 pour une taille de page de 4096) et sont facilement extensibles à l’avenir sans modifier à nouveau la structure sur disque. Le numéro d’enregistrement peut également être facilement étendu, par exemple à 40 bits. Ces nombres sont stockés par groupes de 7 bits avec 1 bit (le plus élevé) comme marqueur (encodage de longueur variable). Chaque nouvel octet à stocker est décalé de 7. Exemples : 25 est stocké sur 1 octet 0x19, 130 = 2 octets 0x82 0x01, 65535 = 3 octets 0xFF 0xFF 0x03.
Nœuds en double :
Un nouveau drapeau est également ajouté pour stocker le numéro d’enregistrement sur chaque nœud (pages non-feuilles). Cela accélère la récupération d’index sur de nombreux doublons. Le drapeau est btr_all_recordnumber (16). Avec ces informations ajoutées, la recherche de clé lors des insertions/suppressions avec de nombreux doublons (NULL dans les clés étrangères par exemple) devient beaucoup plus rapide (comme la collecte des déchets !). En outre, les nœuds en double (longueur = 0) ne stockent pas leurs informations de longueur ; 3 bits du premier octet stocké sont utilisés pour déterminer si ce nœud est un doublon. Outre le marqueur ZERO_LENGTH (4), il existe également les marqueurs END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) et ONE_LENGTH (5). Les numéros 6 et 7 sont réservés pour une utilisation future.
Nœuds de saut :
Un nœud de saut est une référence à un nœud quelque part dans la page.
Il contient des informations de décalage sur le nœud spécifique et les données de préfixe du nœud référencé, mais une compression de préfixe est également effectuée sur les nœuds de saut eux-mêmes.
Idéalement, un nouveau nœud de saut est généré après le premier nœud trouvé après chaque jumpAreaSize, mais cela n’est le cas que lors de la désactivation/activation d’un index ou de l’insertion de nœuds dans le même ordre que celui dans lequel ils seront stockés dans l’index.
Si des nœuds sont insérés entre deux références de nœuds de saut, seuls les décalages sont mis à jour, mais uniquement si les décalages ne dépassent pas un seuil spécifique (+/-10 %).
Lorsqu’un nœud est supprimé, seuls les décalages sont mis à jour ou un nœud de saut est supprimé. Cela signifie qu’un petit trou peut exister entre le dernier nœud de saut et le premier nœud, afin de ne pas perdre de temps à générer de nouveaux nœuds de saut.
Le préfixe et la longueur sont également stockés par encodage de longueur variable.
Exemple de données :
(x) = taille en x octets
| en-tête (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) | … |
Pointeur après l’en-tête fixe = 0x22
Pointeur après les infos de saut = 0x29
Pointeur vers le premier nœud de saut = 0x29 + 6 (nœud de saut 1) + 5 (nœud de saut 2) = 0x34
Le nœud de saut 1 référence le nœud qui représente FIREBIRD comme données, car ce nœud a un préfixe de 2 ; les 2 premiers caractères FI sont également stockés sur le nœud de saut.
Notre nœud de saut suivant pointe vers un nœud qui représente FUEL avec également un préfixe de 2. Ainsi, le nœud de saut 2 devrait contenir FU, mais notre nœud précédent contenait déjà le F ; en raison de la compression de préfixe, celui-ci est ignoré et seul U est stocké.
État NULL :
Les données à stocker sont déterminées dans la procédure compress() dans btr.cpp.
Pour les index ASC (ascendants), aucune donnée ne sera stockée (la clé est de longueur nulle). Cela les placera automatiquement comme première entrée de l’index et donc dans le bon ordre (pour un index à champ unique, la longueur et le préfixe du nœud sont nuls).
Les index DESC (descendants) stockeront un seul octet avec la valeur 0xFF (255). Pour distinguer entre une valeur (une chaîne vide peut être 255) et un état NULL, nous insérons un octet de 0xFE (254) au début des données. Cela n’est fait que pour les valeurs qui commencent par 0xFF (255) ou 0xFE (254), afin de conserver le bon ordre.
Exemples :
| nœuds index ASC, 1 segment | |||
| préfixe | longueur | données stockées | valeur/état réel |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| nœuds index DESC, 1 segment | |||
| préfixe | longueur | données stockées | valeur/état réel |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| nœuds index ASC, 3 segments | |||
| préfixe | longueur | données stockées | valeur/état réel |
| 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œuds index DESC, 3 segments | |||
| préfixe | longueur | données stockées | valeur/état réel |
| 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