29
Implémentation des SGBD Stockage des données, indexation

Implémentation des SGBD Stockage des données, indexation

Embed Size (px)

Citation preview

Page 1: Implémentation des SGBD Stockage des données, indexation

Implémentation des SGBD

Stockage des données, indexation

Page 2: Implémentation des SGBD Stockage des données, indexation

Représenter : • Entier (court) : 2 octets

ex: 35 par 00000000 00100011• Réel : n bits pour la mantisse, m pour l ’exposant.• Caractère : plusieurs possibilités.

ASCII : A 1000001

a 1100001 etc….

• Booléen : TRUE 11111111,

FALSE 00000000.

Page 3: Implémentation des SGBD Stockage des données, indexation

Représenter :• type spécifique (énuméré)

ex: rouge = 1, vert = 2, bleu = 3….• Date ex: YYYYMMDD (pourquoi pas YYMMDD ?)

• Chaine de caractères :

– terminé par nul. Ex:

– donné avec longueur. Ex:

– longueur fixée.

• Ensembles de bits. Ex:

c h a t

c h a t4

long bits

Page 4: Implémentation des SGBD Stockage des données, indexation

Stockage: données codées suivant un format fixe (ex. 2 octets pour un caractère) ou variable (longueur précisée dans ce cas).

Données

Record (enregistrement)

Blocs

Fichiers

Memoire

Page 5: Implémentation des SGBD Stockage des données, indexation

Record (enregistrement) - Collection de données (de champs) de types prédéfinis.

Ex : record employe, champs : nom, salaire, type-de-job,...

Plusieurs choix pour les formats (i.e. organisation interne) et longueurs d’enregistrement:

• format fixe vs. format variable

• longueur fixe vs.longueur variable

Page 6: Implémentation des SGBD Stockage des données, indexation

Format d ’enregistrement fixe - caractéristiques

Un schéma (de record) contient les informations suivantes: nombre de champs, type de chaque champs, ordre des champs dans le record, signification de chaque champ.

Exemple: format et longueur fixe - record employe

(1) E#, entier 2 octets

(2) E.name, char(10). Schema

(3) Dept, code sur 2 octets

55 s m i t h 02

Page 7: Implémentation des SGBD Stockage des données, indexation

Format et longueur de record variables

Utile pour des enregistrements hétérogènes (champs qui se répètent, grande différence de taille entre deux valeurs possibles d ’un même champs…)

Exemple 1: - info. sur les enfants d ’un employé (long. de chaque champs fixe).

5 octets

3 Tom Ted (enf 2)Sally (enf 1)

Page 8: Implémentation des SGBD Stockage des données, indexation

Exemple 2: liens vers les films d ’un acteur (nombre variable de champs de taille fixes ou variables).

Eastwood21 Californie

Autres info. d ’en-tète

longueur du record

Vers adresse (champs variable)

Vers pointeur de films

Pointeurs vers films

numéro de tuple (champs fixe ex. sur 3 octets)

Page 9: Implémentation des SGBD Stockage des données, indexation

• Remarques sur exemple précédent :

– Il faut maintenir un pointeur vers le début de chaque champs de taille variable (à partir du deuxième).

– Les records peuvent contenir à la fois des données mais aussi des adresses (vers mémoire centrale, secondaire ?)

– on a besoin de connaître la longueur totale du record.

Page 10: Implémentation des SGBD Stockage des données, indexation

Caractéristique des records - en-tète

En plus des données, les records doivent contenir un certain nombre d ’informations stockés en en-tète:

– Sur le schéma de la relation à laquelle le record appartient (prend la forme d ’un pointeur vers un zone où le SGBD stocke le schéma.

– Sur la longueur totale du record (surtout pour les records de taille potentiellement variable)

– Sur la date de la dernière modification ou lecture du record (timestamps).

Page 11: Implémentation des SGBD Stockage des données, indexation

Rassembler les records en bloc

Les records sont assemblés par bloc. Le nombre de record par bloc dépend à la fois de la taille des records et de celle d ’un bloc (toujours la même). Chaque bloc sera de la forme suivante :

L ’en-tète de bloc comprend:– liens (offset) vers le début de chaque record du bloc

– un identificateur de bloc

– information sur la relation auquel appartiennet les records du bloc

– liens vers d ’autres blocs (cf. indexation)

– timestamps : temps du dernier accès ou modification

…….. Bloc nBloc 2Bloc 1En-tète

espace perdu

Page 12: Implémentation des SGBD Stockage des données, indexation

Adresses de blocs

• Chaque objet (record, bloc) possède deux types d ’adresse :

– son adresse dans l ’espace d ’adressage du SGBD (i.e. une façon de le localiser dans la mémoire secondaire)

– une adresse (plus petite) en mémoire virtuelle ou centrale.

On a besoin d ’une table pour traduire les adresses (table de

translation).

Quand un bloc est chargé en mémoire centrale les pointeurs des autres blocs vers lui doivent être mis à jour (« swizzled ») ainsi que certains de ses propres pointeurs.

Page 13: Implémentation des SGBD Stockage des données, indexation

« Swizzling » : conversion de l ’adressage lors de chargement (ou déchargement) en mémoire.

Mémoire Disque

Rec A

block 1

Rec Ablock 2 block 2

block 1

Page 14: Implémentation des SGBD Stockage des données, indexation

Remarques

• Grands records et BLOBs (Binary Large Objects)

Il peut arriver que les records soient de très grandes tailles et parfois beaucoup plus grand qu ’un bloc.

• En cas de record occupant une grande partie d ’un seul bloc, on peut décider d ’occuper l ’espace qui reste (trop petit pour un record entier) par une partie d ’un record et ajouter un pointeur vers le bloc contenant le reste du record.

• En cas de très gros record, occupant de nombreux bloc (cas du stockage de vidéo MPEG par exemple), on doit trouver des moyens de stockage permettant le chargement rapide en mémoire centrale de portions du record sans interruptions (stockage sur cylindres consécutifs et découpage du record sur plusieurs disques)

Page 15: Implémentation des SGBD Stockage des données, indexation

Index et B-arbres

Page 16: Implémentation des SGBD Stockage des données, indexation

Indexation

Pour optimiser l ’exécution des requêtes, on a besoin d ’information sur la façon dont les données sont stockées.

Examinons la requête : select * from employe where num=5050

Sans aucune information sur le stockage des tuples de la relation employe on est obligé de les parcourir tous pour trouver celui ou ceux qui satisfont la requête.

Si on suppose qu ’ils sont indéxés suivant un ordre particulier (croissant, décroissant…), la recherche peut devenir plus aisée.

Index : toute structure de données qui prend en entrée une propriété des records (ex. la valeur d ’un ou plusieurs champs) et renvoie « rapidement » les records satisfaisant cette propriété.

Page 17: Implémentation des SGBD Stockage des données, indexation

Indexation

valeur

Rem : des indexs peuvent être crée en SQL par la commande : create index.

On va étudier une des structures les plus répandues d ’indexation : les B-arbres.

index Blocs contenant

les records

records

satisfaisant

Page 18: Implémentation des SGBD Stockage des données, indexation

Les B-arbres

Exemple

87

122

151

180

31

1 6 25 31 46 87 102

111

122

125

151

160

175

180

201

noeud

feuille

Page 19: Implémentation des SGBD Stockage des données, indexation

• Les B-arbres sont des structures de données qui permettent l ’indexation des relations. Ils forment des arbres équilibrés (toutes les feuilles sont au même niveau).

Structure d ’un nœud (non-feuille) : ordre 3

Structure d ’une feuille :

35 9567

k<35 35 k < 67

67 k < 95

95 k

45 8963

k=45 k=63 k=89

vers feuille suivante

Page 20: Implémentation des SGBD Stockage des données, indexation

• Contraintes :

– ordre n : n clés et n+1 pointeurs

– au niveau de chaque feuille : au moins (n+1)/2 pointeurs vers les données (et donc même nombre de clés..

– au niveau de chaque nœud non-feuille :au moins (n+1)/2 pointeurs et (n+1)/2 -1 clés.

– racine : au moins un pointeur et une clé (pas d’autres contraintes)

Page 21: Implémentation des SGBD Stockage des données, indexation

Recherche dans un B-arbre

But : Trouver, le plus rapidement possible, un record dont la clé de recherche K est donnée.

Par induction

• Au niveau d ’une feuille : inspecter les clés de la feuille. Si la clé n°i est égale à K, suivre le pointeur n°i

• Au niveau d ’un nœud (intérieur) : Si les clés de ce nœud sont suivre le pointeur n°i+1 si

Rem : - On démarre la recherche à la racine.

- Nombre d ’étapes proportionnel à la profondeur (et pas au nombre de clés). -> Gain important de temps par rapport à une recherche séquentielle.

1 ii KKKnKK ,...,1

Page 22: Implémentation des SGBD Stockage des données, indexation

Insertion dans un B-arbre

Cas simple : il y a de la place pour insérer (insertion de 83). 7 23 34 62 65 83

60

89

Page 23: Implémentation des SGBD Stockage des données, indexation

Insertion dans un B-arbre

Cas plus complexe : Il n ’y a pas de place (insertion de 15 à partir de l ’exemple précédent).

7 23 34 62 65 83

60

89

7 15

23

Page 24: Implémentation des SGBD Stockage des données, indexation

Insertion dans un B-arbre

Autre exemple : insertion de 160 (à compléter).

100

120

150

180

150

156

179

180

200

Page 25: Implémentation des SGBD Stockage des données, indexation

Insertion dans un B-arbre - Algorithme

1. On cherche la feuille N où insérer la nouvelle clé. S ’il y a de la place dans cette feuille, on ajoute la clé, sinon :

2. On sépare cette feuille en deux : N et M. Puis on répartit les éléments entre les nouvelles feuilles: les (n+1)/2 plus petits restent dans N et les (n+1)/2 plus grands dans M.

On doit maintenant créer un lien d’un nœud intérieur vers M. C’est la plus petite clé atteignable par M qui va servir de séparation et qui être insérée au niveau au dessus dans l’arbre. On relance la procédure

récursivement.

Page 26: Implémentation des SGBD Stockage des données, indexation

Suppression dans un B-arbre

Exemple : suppression de 65 .7 23 34 62 65 83

60

89

Page 27: Implémentation des SGBD Stockage des données, indexation

Suppression dans un B-arbre

Exemple : suppression de 10 (à compléter).

40 4530 3725 2620 2210 141 3

10 20 30 40

25

Page 28: Implémentation des SGBD Stockage des données, indexation

Suppression dans un B-arbre

Exemple : suppression de 32 .

41 5430 3226 2921 2311 131 3

11 21 30 40

26

Page 29: Implémentation des SGBD Stockage des données, indexation

Suppression dans un B-arbre - Algorithme

1. On cherche la feuille N dans laquelle la clé K se trouve puis on supprime K.

2. Si le taux d ’occupation de la feuille est toujours satisfaisant (i.e. supérieur à (n+1)/2), on arrête. Sinon :

- si un des voisins M de N, possede un pointeur de plus que le minimum, alors une des clés de M (la plus grande ou la plus petite suivant le cas), est envoyé vers N.

- sinon, on peut fusionner N avec un de ses voisins (la somme de leur nombre total de pointeurs ne dépassant pas n).

Dans les deux cas, le ou les niveaux au dessus dans l’arbre doivent être mis à jour pour refleter la nouvelle situation.