README.md 5.91 KB
Newer Older
alec.schmidt's avatar
alec.schmidt committed
1
# Énoncé – Travail Pratique B+ Tree
alec.schmidt's avatar
alec.schmidt committed
2

alec.schmidt's avatar
alec.schmidt committed
3
## Introduction
alec.schmidt's avatar
alec.schmidt committed
4

alec.schmidt's avatar
alec.schmidt committed
5
Le but de ce travail pratique est d'implémenter un annuaire pour une école basé sur une structure de données B+ Tree. Un annuaire est une liste contenant des informations sur des membres d'une organisation, ces informations sont par exemples leur prénom, nom, âge, etc. Cet annuaire doit pouvoir s'utiliser depuis la ligne de commande (interface CLI). Les 4 fonctionnalités principales de l'application sont les suivantes :
alec.schmidt's avatar
alec.schmidt committed
6

alec.schmidt's avatar
alec.schmidt committed
7
8
9
- Ajouter un nouveau membre dans l'annuaire (avec toutes ces informations personnelles) ;
- Rechercher un membre via son numéro de téléphone ;
  - Si un enregistrement est trouvé, il faut l'afficher ;
alec.schmidt's avatar
alec.schmidt committed
10

alec.schmidt's avatar
alec.schmidt committed
11
12
- Supprimer un membre de l'annuaire ;
- Afficher tous les enregistrements.
alec.schmidt's avatar
alec.schmidt committed
13

alec.schmidt's avatar
alec.schmidt committed
14
À cet effet, l'implémentation en C contient les éléments suivants :
alec.schmidt's avatar
alec.schmidt committed
15

alec.schmidt's avatar
alec.schmidt committed
16
17
- Un B+ Tree qui est utilisé comme index de recherche où le numéro de téléphone est le champ qui doit être indexé ;
- Une base de données qui contient les données de l'annuaire.
alec.schmidt's avatar
alec.schmidt committed
18

alec.schmidt's avatar
alec.schmidt committed
19
## Travail à réaliser
alec.schmidt's avatar
alec.schmidt committed
20

alec.schmidt's avatar
alec.schmidt committed
21
22
23
24
25
26
27
28
29
30
31
### Structure de l'annuaire

Chaque enregistrement de l'annuaire contient les données suivantes :

- Numéro de téléphone (type: string, longueur: 10 bytes, format: 0xxxxxxxxx) ;
- Prénom (type: string, longueur: 20 bytes) ;
- Nom (type: string, longueur: 20 bytes) ;
- Date de naissance (type: mixed, longueur: 4 bytes, format: YYYY-MM-DD) ;
    - Les 2 premiers bytes sont utilisés pour stocker l'année ;
    - Le 3e byte est utilisé pour stocker le mois ;
    - Le 4e byte est utilisé pour stocker le jour.
alec.schmidt's avatar
alec.schmidt committed
32

alec.schmidt's avatar
alec.schmidt committed
33
### Étape 1 :
alec.schmidt's avatar
alec.schmidt committed
34

alec.schmidt's avatar
alec.schmidt committed
35
Cette première étape a pour but d'implémenter un B+ Tree où les clés sont des nombres entiers qui ont une taille de 64 bits. L'implémentation doit contenir les 3 fonctionnalités suivantes :
alec.schmidt's avatar
alec.schmidt committed
36

alec.schmidt's avatar
alec.schmidt committed
37
38
39
- Insertion d'une clé ;
- Recherche d'une clé ;
- Suppression d'une clé.
alec.schmidt's avatar
alec.schmidt committed
40

alec.schmidt's avatar
alec.schmidt committed
41
Dans les feuilles, les clés doivent être associées à des pointeurs qui plus tard permettront de retrouver l'enregistrement correspondant à la recherche. L'image ci-dessous représente une feuille d'un B+ Tree où les pointeurs de données sont stockés en parallèle des clés.
alec.schmidt's avatar
alec.schmidt committed
42
43
44



alec.schmidt's avatar
alec.schmidt committed
45
![](images/bptree_leaf.jpg)
alec.schmidt's avatar
alec.schmidt committed
46

alec.schmidt's avatar
alec.schmidt committed
47
<center>Figure 1 - Pointeurs sur les données dans une feuille d'un B+ Tree</center>
alec.schmidt's avatar
alec.schmidt committed
48

alec.schmidt's avatar
alec.schmidt committed
49
### Étape 2 :
alec.schmidt's avatar
alec.schmidt committed
50

alec.schmidt's avatar
alec.schmidt committed
51
Dans cette deuxième étape, la base de données de l'annuaire doit être implémentée en mémoire RAM, celle-ci est simplement une liste d'enregistrements (voir "Structure de l'annuaire"). Il faut ensuite développer l'interface CLI où l'on doit pouvoir ajouter un nouveau membre. Au niveau de l'implémentation, il faut donc créer un enregistrement et l'ajouter à la base de données (ajouter l'enregistrement à la fin de la liste). Une fois l'enregistrement ajouté à la base de données, il doit être inséré dans le B+ Tree (l'index de recherche) cependant, le numéro de téléphone ne peut pas être littéralement utilisé en tant que clé. Un hash est utilisé pour régler ce problème.
alec.schmidt's avatar
alec.schmidt committed
52

alec.schmidt's avatar
alec.schmidt committed
53
Pour pouvoir convertir le numéro de téléphone en nombre entier, il faut utiliser l'algorithme de hachage SHA-256. 256 bits étant trop grand pour être stocké dans un entier de 64 bits, il faut tronquer le hash. Le troncage s'effectue sur les 64 premiers bits.
alec.schmidt's avatar
alec.schmidt committed
54

alec.schmidt's avatar
alec.schmidt committed
55
La seule librairie requise à installer est openssl, celle-ci s'installe sur Ubuntu avec la commande suivante : 
alec.schmidt's avatar
alec.schmidt committed
56

alec.schmidt's avatar
alec.schmidt committed
57
58
59
```
sudo apt install libssl-dev 
```
alec.schmidt's avatar
alec.schmidt committed
60

alec.schmidt's avatar
alec.schmidt committed
61
62
63
64
65
En C, le header suivant est importé dans tous les projets :

```c
#include <openssl/sha.h>
```
alec.schmidt's avatar
alec.schmidt committed
66

alec.schmidt's avatar
alec.schmidt committed
67
Maintenant que le B+ Tree est utilisable, il faut ajouter à l'interface CLI la fonctionnalité de recherche d'enregistrement via le numéro de téléphone. Il faut également implémenter la suppression d'un enregistrement qui se fait également avec le numéro de téléphone.
alec.schmidt's avatar
alec.schmidt committed
68

alec.schmidt's avatar
alec.schmidt committed
69
### Étape 3 :
alec.schmidt's avatar
alec.schmidt committed
70

alec.schmidt's avatar
alec.schmidt committed
71
À ce stade, l'annuaire fonctionne correctement, cependant dès que l'on quitte l'application, les données sont perdues. La base de données doit être maintenant entièrement enregistré dans la mémoire non-volatile (sur le disque). La base donnée est enregistrée dans un fichier binaire où chaque enregistrement a une taille en bytes fixe, exactement 54 bytes + 1 byte pour savoir si l'enregistrement est supprimé. Les enregistrements sont enregistrés de manière continue.
alec.schmidt's avatar
alec.schmidt committed
72

alec.schmidt's avatar
alec.schmidt committed
73
Dès lors, l'enregistrement correspondant à une recherche doit être chargé dans la mémoire volatile (la RAM) sans chargé l'entièreté de la base de données. Pour simplifier le projet, il faut au lancement de l'application reconstituer le B+ Tree à partir de la base de données.
alec.schmidt's avatar
alec.schmidt committed
74

alec.schmidt's avatar
alec.schmidt committed
75
76
77
### Étape 4 (bonus) :
- Enregistrer le B+ Tree dans la mémoire non-volatile (sur le disque) ;
- Faire une recherche par nom (gérer les collisions liées au fait que plusieurs personnes peuvent avoir le même nom).
alec.schmidt's avatar
alec.schmidt committed
78

alec.schmidt's avatar
alec.schmidt committed
79
## Exemples de tests à implémenter
alec.schmidt's avatar
alec.schmidt committed
80

alec.schmidt's avatar
alec.schmidt committed
81
Afin de valider que l'annuaire est correctement implémenté, les tests suivant doivent tous être validé.
alec.schmidt's avatar
alec.schmidt committed
82

alec.schmidt's avatar
alec.schmidt committed
83
Tests fonctionnels :
alec.schmidt's avatar
alec.schmidt committed
84

alec.schmidt's avatar
alec.schmidt committed
85
86
87
88
89
90
- Une fois qu'un membre a été ajouté, on doit pouvoir le retrouver en listant tous les membres ;
- La fonctionnalité qui liste les membres de l'annuaire doit tous les afficher ;
- La fonctionnalité de recherche doit retourner le bon membre si le numéro de téléphone correspond un à un membre ;
- La fonctionnalité de recherche doit retourner qu'aucun membre n'a été trouvé si et seulement si le numéro de téléphone ne correspond à aucun membre ;
- Une fois un membre supprimé, on ne doit pas pouvoir le retrouver quand on liste tous les membres ;
- Une fois un membre supprimé, on ne doit pas pouvoir le retrouver avec la fonctionnalité de recherche.
alec.schmidt's avatar
alec.schmidt committed
91

alec.schmidt's avatar
alec.schmidt committed
92
Tests unitaires :
alec.schmidt's avatar
alec.schmidt committed
93

alec.schmidt's avatar
alec.schmidt committed
94
95
96
- Toutes les clés insérées dans un B+ Tree doivent être retrouvées dans l'ordre en utilisant le chaînage des nœuds feuilles ;
- Une clé insérée dans un B+ Tree doit pouvoir être retrouvé en utilisant la fonctionnalité de recherche (celle du B+ Tree) ;
- Une clé supprimée d'un B+ Tree ne doit pas pouvoir être retrouvé en utilisant la fonctionnalité de recherche (celle du B+ Tree).