Maitriser les donnees

Construire des bases de donnees, un moteur de recherche et des pipelines de zéro. Comprendre le stockage.

Sommaire

1. Introduction aux donnees

Une base de donnees, c'est comme une bibliothèque.

Tu pourrais jeter tous les livres dans une pile sur le sol. C'est simple, mais pour retrouver un livre, t'y passes l'après-midi. En plus, si deux personnes veulent le même livre en même temps, c'est le chaos.

Une bibliothèque, elle, range les livres par thème, auteur, format. Chaque livre a une place précise. Et y'a des registres pour savoir où chercher. C'est plus de travail au début, mais après, on gagne un temps fou.

Une base de données, c'est exactement ça.

FICHIERS PLATS                BASE DE DONNEES
     │                              │
     │  tous_donnees.txt            │  db.sqlite
     │  ┌─────────────────┐        │  ┌─────────────────┐
     │  │ Alice,alice@... │        │  │ Tables indexees  │
     │  │ Bob,bob@...     │        │  │ Requetes rapides │
     │  │ ...             │        │  │ Concurrent safe  │
     │  │ (tout en vrac)  │        │  └─────────────────┘
     │  └─────────────────┘        │
     │                              │
     │  Recherche = scanner tout  │  Recherche = O(log n)
     │  Concurrité = probleme      │  Concurrité = geree
     │  Corruption = facile        │  Transaction = ACID

L'histoire du stockage

Les systèmes de stockage ont évolué pour répondre à des problèmes de plus en plus complexes :

Epoque Systeme Probleme resolu
1950s Fichiers séquentiels Stocker des données, point
1960s BDD hiérarchiques Structure parent-enfant
1970s BDD relationnelles Relations entre tables, SQL
2000s NoSQL Scale horizontal, flexibilité
2010s+ NewSQL, Distributed DBs Performance + ACID + Scale

Pourquoi les BDD existent

Les bases de données résolvent des problèmes que les fichiers simples ne peuvent pas gérer :

  • Persistance : Les données survivent à un redémarrage
  • Concurrité : Plusieurs utilisateurs/programmes peuvent accéder en même temps
  • Atomicité : Une transaction est tout ou rien (pas de demi-état)
  • Cohérence : Les données respectent des règles (ex: email unique)
  • Isolation : Les transactions parallèles ne s'interfèrent pas
  • Durabilité : Les données validées ne sont pas perdues

Ensemble, ces propriétés forment ACID. C'est ce qui distingue une vraie BDD d'un simple fichier.

La grande division : SQL vs NoSQL

SQL (relationnel) NoSQL (non relationnel)
Structure fixe (schéma) Structure flexible (schema-less)
Tables avec relations Documents, clé-valeur, colonnes, graphes
SQL (langage standardisé) API propre à chaque BDD
Ex: PostgreSQL, MySQL, SQLite Ex: MongoDB, Redis, Cassandra
Quand la structure est stable Quand les données évoluent souvent
Ce qu'on va faire : Dans ce tutoriel, on va construire chaque brique à la main. Tu vas comprendre pourquoi les BDD font ce qu'elles font. Et après, tu pourras utiliser SQLite, PostgreSQL ou Redis en sachant exactement ce qui se passe sous le capot.

2. Stockage simple

Debutant Commençons par le plus simple : écrire et lire des fichiers.

Le format JSON

JSON est le format le plus répandu pour stocker des données structurées. C'est lisible, simple, et compris par tous les langages.

Code en JavaScript

const fs = require('fs');

// ===================
// ECRITURE EN JSON
// ===================

const contacts = [
  { id: 1, nom: 'Alice', email: 'alice@test.com' },
  { id: 2, nom: 'Bob', email: 'bob@test.com' },
  { id: 3, nom: 'Charlie', email: 'charlie@test.com' }
];

// Ecrire dans un fichier JSON
fs.writeFileSync('contacts.json', JSON.stringify(contacts, null, 2));
console.log('Fichier ecrit !');

// ===================
// LECTURE EN JSON
// ===================

const data = fs.readFileSync('contacts.json', 'utf-8');
const contactsLus = JSON.parse(data);
console.log('Contacts lus:', contactsLus);

// ===================
// AJOUT D'UN CONTACT
// ===================

function ajouterContact(nom, email) {
  // 1. Lire le fichier existant
  const data = fs.readFileSync('contacts.json', 'utf-8');
  const contacts = JSON.parse(data);
  
  // 2. Calculer le nouvel ID
  const maxId = contacts.reduce((max, c) => Math.max(max, c.id), 0);
  const nouvelId = maxId + 1;
  
  // 3. Ajouter le nouveau contact
  contacts.push({ id: nouvelId, nom, email });
  
  // 4. Re-ecrire le fichier
  fs.writeFileSync('contacts.json', JSON.stringify(contacts, null, 2));
  console.log(`Contact ajoute: ${nom}`);
}

ajouterContact('David', 'david@test.com');

// ===================
// RECHERCHE D'UN CONTACT
// ===================

function trouverContact(query) {
  const data = fs.readFileSync('contacts.json', 'utf-8');
  const contacts = JSON.parse(data);
  
  return contacts.filter(c => 
    c.nom.toLowerCase().includes(query.toLowerCase()) ||
    c.email.toLowerCase().includes(query.toLowerCase())
  );
}

console.log('Recherche "ali":', trouverContact('ali'));

// ===================
// SUPPRESSION D'UN CONTACT
// ===================

function supprimerContact(id) {
  const data = fs.readFileSync('contacts.json', 'utf-8');
  const contacts = JSON.parse(data);
  
  const index = contacts.findIndex(c => c.id === id);
  if (index !== -1) {
    contacts.splice(index, 1);
    fs.writeFileSync('contacts.json', JSON.stringify(contacts, null, 2));
    console.log(`Contact ${id} supprime`);
  } else {
    console.log('Contact non trouve');
  }
}

supprimerContact(2);
import json

# ===================
# ECRITURE EN JSON
# ===================

contacts = [
    {'id': 1, 'nom': 'Alice', 'email': 'alice@test.com'},
    {'id': 2, 'nom': 'Bob', 'email': 'bob@test.com'},
    {'id': 3, 'nom': 'Charlie', 'email': 'charlie@test.com'}
]

# Ecrire dans un fichier JSON
with open('contacts.json', 'w', encoding='utf-8') as f:
    json.dump(contacts, f, indent=2, ensure_ascii=False)
print('Fichier ecrit !')

# ===================
# LECTURE EN JSON
# ===================

with open('contacts.json', 'r', encoding='utf-8') as f:
    contacts_lus = json.load(f)
print('Contacts lus:', contacts_lus)

# ===================
# AJOUT D'UN CONTACT
# ===================

def ajouter_contact(nom, email):
    # 1. Lire le fichier existant
    with open('contacts.json', 'r', encoding='utf-8') as f:
        contacts = json.load(f)
    
    # 2. Calculer le nouvel ID
    max_id = max(c['id'] for c in contacts) if contacts else 0
    nouvel_id = max_id + 1
    
    # 3. Ajouter le nouveau contact
    contacts.append({'id': nouvel_id, 'nom': nom, 'email': email})
    
    # 4. Re-ecrire le fichier
    with open('contacts.json', 'w', encoding='utf-8') as f:
        json.dump(contacts, f, indent=2, ensure_ascii=False)
    print(f'Contact ajoute: {nom}')

ajouter_contact('David', 'david@test.com')

# ===================
# RECHERCHE D'UN CONTACT
# ===================

def trouver_contact(query):
    with open('contacts.json', 'r', encoding='utf-8') as f:
        contacts = json.load(f)
    
    return [c for c in contacts if 
            query.lower() in c['nom'].lower() or 
            query.lower() in c['email'].lower()]

print('Recherche "ali":', trouver_contact('ali'))

# ===================
# SUPPRESSION D'UN CONTACT
# ===================

def supprimer_contact(id_contact):
    with open('contacts.json', 'r', encoding='utf-8') as f:
        contacts = json.load(f)
    
    contacts = [c for c in contacts if c['id'] != id_contact]
    
    with open('contacts.json', 'w', encoding='utf-8') as f:
        json.dump(contacts, f, indent=2, ensure_ascii=False)
    print(f'Contact {id_contact} supprime')

supprimer_contact(2)

Les problemes du stockage simple

Cette approche a de graves limitations :
  • Performance : Pour ajouter un contact, on relit tout le fichier → O(n)
  • Concurrité : Si deux processus ecrivent en même temps, corruption
  • Recherche : Trouver un contact = scanner tout le fichier → O(n)
  • Atomicité : Si le programme plante pendant l'écriture, fichier corrompu
  • Scale : 1000 contacts = OK, 1 million = catastrophe

C'est pour ça que les vraies bases de données utilisent des structures plus intelligentes. C'est ce qu'on va construire.

3. Data structures

Intermediaire Les structures de données utilisées dans les bases de données.

Hash Table (Table de hachage)

Une hash table permet de stocker des paires clé-valeur avec un accès en O(1) (temps constant). C'est la structure utilisée par Redis et les caches.

        HASH TABLE
       
   "alice" -> hash("alice") = 3 -> bucket[3] -> [{key: "alice", value: ...}]
   "bob"   -> hash("bob")   = 7 -> bucket[7] -> [{key: "bob", value: ...}]
   "carol" -> hash("carol") = 3 -> bucket[3] -> [{key: "alice", ...}, {key: "carol", ...}]
                                                    (collisions gerees par liste)
                                                    
   Taille: 10 buckets
   Lookup: O(1) en moyenne, O(n) dans le pire cas (toutes collisions)

Implémentation Hash Table

// Hash Table implementee from scratch

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []);
  }
  
  // Fonction de hachage : transforme une cle en index
  hash(key) {
    let hash = 0;
    const str = String(key);
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 31 + str.charCodeAt(i)) % this.size;
    }
    return Math.abs(hash);
  }
  
  // Ajouter ou mettre a jour une valeur
  set(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    // Verifier si la cle existe deja
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i].key === key) {
        bucket[i].value = value;
        return;
      }
    }
    
    // Sinon, ajouter
    bucket.push({ key, value });
  }
  
  // Recuperer une valeur
  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    for (const pair of bucket) {
      if (pair.key === key) {
        return pair.value;
      }
    }
    return undefined;
  }
  
  // Supprimer une valeur
  delete(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i].key === key) {
        bucket.splice(i, 1);
        return true;
      }
    }
    return false;
  }
  
  // Verifier si une cle existe
  has(key) {
    return this.get(key) !== undefined;
  }
  
  // Lister toutes les cles
  keys() {
    const keys = [];
    for (const bucket of this.buckets) {
      for (const pair of bucket) {
        keys.push(pair.key);
      }
    }
    return keys;
  }
}

// Test
const ht = new HashTable();

ht.set('alice', { email: 'alice@test.com', age: 30 });
ht.set('bob', { email: 'bob@test.com', age: 25 });
ht.set('charlie', { email: 'charlie@test.com', age: 35 });

console.log('alice:', ht.get('alice'));
console.log('bob existe?', ht.has('bob'));
console.log('david existe?', ht.has('david'));
console.log('toutes les cles:', ht.keys());

ht.delete('bob');
console.log('apres suppression, bob existe?', ht.has('bob'));
# Hash Table implementee from scratch

class HashTable:
    def __init__(self, size=100):
        self.size = size
        self.buckets = [[] for _ in range(size)]
    
    def _hash(self, key):
        """Fonction de hachage : transforme une cle en index"""
        hash_val = 0
        for char in str(key):
            hash_val = (hash_val * 31 + ord(char)) % self.size
        return abs(hash_val)
    
    def set(self, key, value):
        """Ajouter ou mettre a jour une valeur"""
        index = self._hash(key)
        bucket = self.buckets[index]
        
        # Verifier si la cle existe deja
        for i, pair in enumerate(bucket):
            if pair['key'] == key:
                bucket[i]['value'] = value
                return
        
        # Sinon, ajouter
        bucket.append({'key': key, 'value': value})
    
    def get(self, key):
        """Recuperer une valeur"""
        index = self._hash(key)
        bucket = self.buckets[index]
        
        for pair in bucket:
            if pair['key'] == key:
                return pair['value']
        return None
    
    def delete(self, key):
        """Supprimer une valeur"""
        index = self._hash(key)
        bucket = self.buckets[index]
        
        for i, pair in enumerate(bucket):
            if pair['key'] == key:
                del bucket[i]
                return True
        return False
    
    def has(self, key):
        """Verifier si une cle existe"""
        return self.get(key) is not None
    
    def keys(self):
        """Lister toutes les cles"""
        keys = []
        for bucket in self.buckets:
            for pair in bucket:
                keys.append(pair['key'])
        return keys

# Test
ht = HashTable()

ht.set('alice', {'email': 'alice@test.com', 'age': 30})
ht.set('bob', {'email': 'bob@test.com', 'age': 25})
ht.set('charlie', {'email': 'charlie@test.com', 'age': 35})

print('alice:', ht.get('alice'))
print('bob existe?', ht.has('bob'))
print('david existe?', ht.has('david'))
print('toutes les cles:', ht.keys())

ht.delete('bob')
print('apres suppression, bob existe?', ht.has('bob'))

B-Tree

Un B-Tree est un arbre équilibré utilisé pour stocker des données ordonnées. C'est la structure utilisée par les index dans les bases de données relationnelles.

                    B-TREE (ordre 3)
                    
                         [50]
                        /    \
                  [20, 30]   [70, 80]
                  /  |  \    /  |  \
                10  25  35  60  75  90
                
   - Chaque noeud a entre 2 et 4 enfants (ordre * 2)
   - Les feuilles sont au meme niveau (arbre equilibre)
   - Hauteur = O(log n)
   - Recherche = O(log n)
   - Insertion = O(log n)
Implementation simplifiee d'un B-Tree

Un B-Tree complet est complexe. Voici une version simplifiée pour comprendre le concept :

// B-Tree simplifie (version pedagogique)

class BTreeNode {
  constructor(isLeaf = true) {
    this.keys = [];
    this.values = [];
    this.children = [];
    this.isLeaf = isLeaf;
  }
}

class BTree {
  constructor(order = 3) {
    this.order = order;
    this.root = new BTreeNode(true);
  }
  
  // Recherche d'une cle
  get(key) {
    return this._get(this.root, key);
  }
  
  _get(node, key) {
    let i = 0;
    while (i < node.keys.length && key > node.keys[i]) {
      i++;
    }
    
    if (i < node.keys.length && key === node.keys[i]) {
      return node.values[i];
    }
    
    if (node.isLeaf) {
      return undefined;
    }
    
    return this._get(node.children[i], key);
  }
  
  // Insertion d'une cle (version simplifiee)
  set(key, value) {
    const root = this.root;
    
    if (root.keys.length === 2 * this.order - 1) {
      // Racine pleine, il faut splitter
      const newRoot = new BTreeNode(false);
      newRoot.children.push(this.root);
      this._splitChild(newRoot, 0);
      this.root = newRoot;
    }
    
    this._insertNonFull(this.root, key, value);
  }
  
  _insertNonFull(node, key, value) {
    let i = node.keys.length - 1;
    
    if (node.isLeaf) {
      // Inserer dans la feuille
      while (i >= 0 && key < node.keys[i]) {
        i--;
      }
      node.keys.splice(i + 1, 0, key);
      node.values.splice(i + 1, 0, value);
    } else {
      // Descendre vers le bon enfant
      while (i >= 0 && key < node.keys[i]) {
        i--;
      }
      i++;
      
      if (node.children[i].keys.length === 2 * this.order - 1) {
        this._splitChild(node, i);
        if (key > node.keys[i]) {
          i++;
        }
      }
      
      this._insertNonFull(node.children[i], key, value);
    }
  }
  
  _splitChild(parent, index) {
    const order = this.order;
    const child = parent.children[index];
    const newNode = new BTreeNode(child.isLeaf);
    
    // Deplacer la mediane vers le parent
    const medianIndex = order - 1;
    parent.keys.splice(index, 0, child.keys[medianIndex]);
    parent.values.splice(index, 0, child.values[medianIndex]);
    
    // Deplacer les cles et valeurs vers le nouveau noeud
    newNode.keys = child.keys.splice(medianIndex + 1);
    newNode.values = child.values.splice(medianIndex + 1);
    child.keys.pop();
    child.values.pop();
    
    // Deplacer les enfants si c'est pas une feuille
    if (!child.isLeaf) {
      newNode.children = child.children.splice(medianIndex + 1);
    }
    
    parent.children.splice(index + 1, 0, newNode);
  }
}

// Test
const bt = new BTree(3);
bt.set(10, 'dix');
bt.set(20, 'vingt');
bt.set(5, 'cinq');
bt.set(15, 'quinze');
bt.set(30, 'trente');

console.log('Recherche 10:', bt.get(10));
console.log('Recherche 99:', bt.get(99));
Pourquoi B-Tree dans les BDD ?
  • Les données sont sur disque, pas en mémoire
  • Un B-Tree minimise les lectures disque (hauteur faible)
  • Les noeuds sont alignés avec les pages disque (4KB, 8KB...)
  • Les range queries (BETWEEN, >, <) sont efficaces

4. Key-Value store (Redis-like)

Intermediaire Construisons un mini Redis.

Objectif

Créer un stockage clé-valeur en mémoire avec :

  • Commandes : SET, GET, DEL, KEYS, EXISTS
  • Expiration optionnelle (TTL)
  • Persistance sur disque (optionnel)
  • API HTTP

Architecture

┌─────────────────────────────────────────────────────────────┐
│                    KEY-VALUE STORE                          │
│                                                             │
│   CLIENT          API HTTP           HASH TABLE     DISK    │
│   ┌─────┐        ┌─────┐            ┌─────┐      ┌─────┐  │
│   │     │ ──────▶│/set │ ──────────▶ │     │ ────▶│dump │  │
│   │     │        │/get │            │ Map │      │     │  │
│   │     │ ◀──────│/del │ ◀───────── │     │      │     │  │
│   └─────┘        └─────┘            └─────┘      └─────┘  │
│                                                             │
│   Commandes: SET key value [EX seconds]                     │
│             GET key                                         │
│             DEL key                                         │
│             KEYS pattern                                    │
│             EXISTS key                                      │
└─────────────────────────────────────────────────────────────┘

Implémentation complète en JavaScript

// Key-Value Store complet (Redis-like)

const fs = require('fs');

class KeyValueStore {
  constructor persistenceFile = 'kvstore.json') {
    this.data = new Map();
    this.ttls = new Map(); // expiration timestamps
    this.persistenceFile = persistenceFile;
    
    // Charger depuis le disque si existe
    this.loadFromDisk();
    
    // Nettoyer les expirees toutes les secondes
    setInterval(() => this.cleanExpired(), 1000);
  }
  
  // ===================
  // COMMANDES PRINCIPALES
  // ===================
  
  SET(key, value, ttlSeconds = null) {
    this.data.set(key, value);
    
    if (ttlSeconds !== null) {
      this.ttls.set(key, Date.now() + ttlSeconds * 1000);
    } else {
      this.ttls.delete(key);
    }
    
    this.saveToDisk();
    return { ok: true, message: 'OK' };
  }
  
  GET(key) {
    this._checkExpired(key);
    
    if (this.data.has(key)) {
      return { ok: true, value: this.data.get(key) };
    }
    return { ok: false, error: 'Key not found' };
  }
  
  DEL(key) {
    this._checkExpired(key);
    
    if (this.data.has(key)) {
      this.data.delete(key);
      this.ttls.delete(key);
      this.saveToDisk();
      return { ok: true, deleted: 1 };
    }
    return { ok: true, deleted: 0 };
  }
  
  EXISTS(key) {
    this._checkExpired(key);
    return { ok: true, exists: this.data.has(key) };
  }
  
  KEYS(pattern = '*') {
    this._cleanAllExpired();
    
    const keys = Array.from(this.data.keys());
    
    if (pattern === '*') {
      return { ok: true, keys: keys };
    }
    
    // Pattern simple : * = wildcard
    const regex = new RegExp('^' + pattern.replace(/\*/g, '.*') + '$');
    const matched = keys.filter(k => regex.test(k));
    
    return { ok: true, keys: matched };
  }
  
  INCR(key) {
    this._checkExpired(key);
    
    const current = this.data.get(key);
    const newVal = (parseInt(current) || 0) + 1;
    this.data.set(key, newVal);
    this.saveToDisk();
    
    return { ok: true, value: newVal };
  }
  
  // ===================
  // GESTION DE L'EXPIRATION
  // ===================
  
  _checkExpired(key) {
    if (this.ttls.has(key) && Date.now() > this.ttls.get(key)) {
      this.data.delete(key);
      this.ttls.delete(key);
    }
  }
  
  _cleanAllExpired() {
    const now = Date.now();
    for (const [key, expireTime] of this.ttls) {
      if (now > expireTime) {
        this.data.delete(key);
        this.ttls.delete(key);
      }
    }
  }
  
  cleanExpired() {
    this._cleanAllExpired();
  }
  
  // ===================
  // PERSISTANCE
  // ===================
  
  saveToDisk() {
    const obj = {};
    for (const [key, value] of this.data) {
      obj[key] = {
        value,
        expire: this.ttls.get(key) || null
      };
    }
    fs.writeFileSync(this.persistenceFile, JSON.stringify(obj, null, 2));
  }
  
  loadFromDisk() {
    try {
      if (fs.existsSync(this.persistenceFile)) {
        const raw = fs.readFileSync(this.persistenceFile, 'utf-8');
        const obj = JSON.parse(raw);
        
        for (const [key, data] of Object.entries(obj)) {
          if (data.expire && Date.now() > data.expire) {
            continue;
          }
          this.data.set(key, data.value);
          if (data.expire) {
            this.ttls.set(key, data.expire);
          }
        }
        console.log(`Charge ${this.data.size} cles depuis ${this.persistenceFile}`);
      }
    } catch (e) {
      console.log('Erreur chargement:', e.message);
    }
  }
}

// ===================
// API HTTP
// ===================

const http = require('http');
const url = require('url');

const store = new KeyValueStore('data/kvstore.json');

const server = http.createServer((req, res) => {
  const parsedUrl = url.parse(req.url, true);
  const path = parsedUrl.pathname;
  const query = parsedUrl.query;
  
  res.setHeader('Content-Type', 'application/json');
  
  // CORS
  res.setHeader('Access-Control-Allow-Origin', '*');
  res.setHeader('Access-Control-Allow-Methods', 'GET, POST, DELETE');
  
  try {
    // GET /set?key=name&value=alice&ttl=60
    if (path === '/set' && req.method === 'GET') {
      const { key, value, ttl } = query;
      if (!key || value === undefined) {
        res.writeHead(400);
        res.end(JSON.stringify({ error: 'key and value required' }));
        return;
      }
      const result = store.SET(key, value, ttl ? parseInt(ttl) : null);
      res.writeHead(200);
      res.end(JSON.stringify(result));
    }
    
    // GET /get?key=name
    else if (path === '/get' && req.method === 'GET') {
      const { key } = query;
      if (!key) {
        res.writeHead(400);
        res.end(JSON.stringify({ error: 'key required' }));
        return;
      }
      const result = store.GET(key);
      res.writeHead(result.ok ? 200 : 404);
      res.end(JSON.stringify(result));
    }
    
    // GET /del?key=name
    else if (path === '/del' && req.method === 'GET') {
      const { key } = query;
      if (!key) {
        res.writeHead(400);
        res.end(JSON.stringify({ error: 'key required' }));
        return;
      }
      const result = store.DEL(key);
      res.writeHead(200);
      res.end(JSON.stringify(result));
    }
    
    // GET /keys?pattern=*
    else if (path === '/keys' && req.method === 'GET') {
      const { pattern } = query;
      const result = store.KEYS(pattern || '*');
      res.writeHead(200);
      res.end(JSON.stringify(result));
    }
    
    // GET /exists?key=name
    else if (path === '/exists' && req.method === 'GET') {
      const { key } = query;
      if (!key) {
        res.writeHead(400);
        res.end(JSON.stringify({ error: 'key required' }));
        return;
      }
      const result = store.EXISTS(key);
      res.writeHead(200);
      res.end(JSON.stringify(result));
    }
    
    // POST /set (body JSON)
    else if (path === '/set' && req.method === 'POST') {
      let body = '';
      req.on('data', chunk => body += chunk);
      req.on('end', () => {
        try {
          const { key, value, ttl } = JSON.parse(body);
          if (!key || value === undefined) {
            res.writeHead(400);
            res.end(JSON.stringify({ error: 'key and value required' }));
            return;
          }
          const result = store.SET(key, value, ttl || null);
          res.writeHead(200);
          res.end(JSON.stringify(result));
        } catch (e) {
          res.writeHead(400);
          res.end(JSON.stringify({ error: 'invalid JSON' }));
        }
      });
    }
    
    // GET /
    else if (path === '/' && req.method === 'GET') {
      res.writeHead(200, { 'Content-Type': 'text/html' });
      res.end(`
        <h1>Key-Value Store</h1>
        <h2>Endpoints</h2>
        <ul>
          <li>GET /set?key=name&value=alice&ttl=60</li>
          <li>GET /get?key=name</li>
          <li>GET /del?key=name</li>
          <li>GET /keys?pattern=*</li>
          <li>GET /exists?key=name</li>
          <li>POST /set { key, value, ttl }</li>
        </ul>
      `);
    }
    
    else {
      res.writeHead(404);
      res.end(JSON.stringify({ error: 'Not found' }));
    }
  } catch (e) {
    res.writeHead(500);
    res.end(JSON.stringify({ error: e.message }));
  }
});

// Creer le dossier data si n'existe pas
if (!fs.existsSync('data')) {
  fs.mkdirSync('data');
}

server.listen(3000, () => {
  console.log('Key-Value Store sur http://localhost:3000');
  console.log('Endpoints: /set, /get, /del, /keys, /exists');
});

Tester le store

# Definir une valeur
curl "http://localhost:3000/set?key=session:1&value={\"user\":\"alice\"}&ttl=60"

# Recuperer une valeur
curl "http://localhost:3000/get?key=session:1"

# Lister toutes les cles
curl "http://localhost:3000/keys"

# Supprimer une cle
curl "http://localhost:3000/del?key=session:1"

# Verifier si une cle existe
curl "http://localhost:3000/exists?key=session:1"

5. Indexation

Intermediaire Accélérer les recherches.

Le probleme

Sans index, pour trouver une valeur, on doit scanner toutes les données. C'est O(n). Avec un million de lignes, c'est trop lent.

Un index, c'est un annuaire. Au lieu de scanner, on regarde directement au bon endroit.

Index inverse

Un index inverse mappe des termes vers des documents. C'est ce qui est utilisé dans les moteurs de recherche.

DOCUMENTS                    INDEX INVERSE
                            
Doc 1: "Le chat dort"        Termes -> Documents
Doc 2: "Le chien court"     ┌────────────────────┐
Doc 3: "Le chat mange"      │ "chat"  -> [1, 3]  │
                             │ "dort"  -> [1]     │
QUESTION                     │ "chien" -> [2]     │
"chat"                       │ "court" -> [2]     │
     │                       │ "mange" -> [3]     │
     ▼                       │ "le"    -> [1,2,3] │
Recherche "chat"             └────────────────────┘
     │
     ▼
Resultat: Doc 1, Doc 3

Implémentation d'un index inverse

// Index inverse pour la recherche full-text

class InvertedIndex {
  constructor() {
    this.documents = new Map(); // id -> document
    this.index = new Map();     // terme -> Set(documentIds)
    this.docCounter = 0;
  }
  
  // Tokenisation simple (minuscules, suppression ponctuation)
  tokenize(text) {
    return text
      .toLowerCase()
      .replace(/[^\w\s]/g, '')
      .split(/\s+/)
      .filter(t => t.length > 1); // ignorer les caracteres seuls
  }
  
  // Ajouter un document
  addDocument(text) {
    const docId = ++this.docCounter;
    this.documents.set(docId, text);
    
    const tokens = this.tokenize(text);
    
    for (const token of tokens) {
      if (!this.index.has(token)) {
        this.index.set(token, new Set());
      }
      this.index.get(token).add(docId);
    }
    
    return docId;
  }
  
  // Rechercher des documents (AND par defaut)
  search(query, operator = 'AND') {
    const tokens = this.tokenize(query);
    
    if (tokens.length === 0) {
      return [];
    }
    
    // Recuperer les sets de documents pour chaque token
    const docSets = tokens
      .map(t => this.index.get(t) || new Set())
      .sort((a, b) => a.size - b.size); // optimiser: commencer par le plus petit
    
    if (docSets.length === 0) {
      return [];
    }
    
    let result = new Set(docSets[0]);
    
    for (let i = 1; i < docSets.length; i++) {
      if (operator === 'AND') {
        result = new Set([...result].filter(id => docSets[i].has(id)));
      } else { // OR
        for (const id of docSets[i]) {
          result.add(id);
        }
      }
    }
    
    // Retourner les documents
    return [...result].map(id => ({
      id,
      text: this.documents.get(id)
    }));
  }
  
  // Statistiques
  stats() {
    return {
      documentCount: this.documents.size,
      termCount: this.index.size,
      avgTermsPerDoc: this.index.size / Math.max(1, this.documents.size)
    };
  }
}

// Test
const idx = new InvertedIndex();

const doc1 = idx.addDocument('Le chat dort sur le canape');
const doc2 = idx.addDocument('Le chien court dans le jardin');
const doc3 = idx.addDocument('Le chat mange des croquettes');
const doc4 = idx.addDocument('Les chats et les chiens sont des animaux');

console.log('Stats:', idx.stats());
console.log('\nRecherche "chat":');
console.log(idx.search('chat'));

console.log('\nRecherche "chat chien" (AND):');
console.log(idx.search('chat chien', 'AND'));

console.log('\nRecherche "chat chien" (OR):');
console.log(idx.search('chat chien', 'OR'));

console.log('\nRecherche "dort canape":');
console.log(idx.search('dort canape'));
# Index inverse pour la recherche full-text
import re

class InvertedIndex:
    def __init__(self):
        self.documents = {}  # id -> document
        self.index = {}      # terme -> set(documentIds)
        self.doc_counter = 0
    
    def tokenize(self, text):
        """Tokenisation simple"""
        text = text.lower()
        text = re.sub(r'[^\w\s]', '', text)
        tokens = text.split()
        return [t for t in tokens if len(t) > 1]
    
    def add_document(self, text):
        """Ajouter un document"""
        self.doc_counter += 1
        doc_id = self.doc_counter
        self.documents[doc_id] = text
        
        tokens = self.tokenize(text)
        
        for token in tokens:
            if token not in self.index:
                self.index[token] = set()
            self.index[token].add(doc_id)
        
        return doc_id
    
    def search(self, query, operator='AND'):
        """Rechercher des documents"""
        tokens = self.tokenize(query)
        
        if not tokens:
            return []
        
        doc_sets = [self.index.get(t, set()) for t in tokens]
        
        if not doc_sets:
            return []
        
        result = doc_sets[0].copy()
        
        for doc_set in doc_sets[1:]:
            if operator == 'AND':
                result = result & doc_set
            else:
                result = result | doc_set
        
        return [{'id': doc_id, 'text': self.documents[doc_id]} for doc_id in result]
    
    def stats(self):
        return {
            'documentCount': len(self.documents),
            'termCount': len(self.index),
            'avgTermsPerDoc': len(self.index) / max(1, len(self.documents))
        }

# Test
idx = InvertedIndex()

doc1 = idx.add_document('Le chat dort sur le canape')
doc2 = idx.add_document('Le chien court dans le jardin')
doc3 = idx.add_document('Le chat mange des croquettes')
doc4 = idx.add_document('Les chats et les chiens sont des animaux')

print('Stats:', idx.stats())
print('\nRecherche "chat":')
print(idx.search('chat'))

print('\nRecherche "chat chien" (AND):')
print(idx.search('chat chien', 'AND'))

print('\nRecherche "chat chien" (OR):')
print(idx.search('chat chien', 'OR'))

6. Database from scratch (SQLite-like)

Avance Construire une vraie base de données relationnelle.

Architecture

┌─────────────────────────────────────────────────────────────┐
│                      DATABASE ARCHITECTURE                   │
│                                                              │
│   SQL Parser          Query Engine         Storage Engine    │
│   ┌─────────┐        ┌─────────┐          ┌─────────┐       │
│   │ "SELECT"│        │         │          │ Pages   │       │
│   │ "* FROM"│───────▶│ Execute │─────────▶│ (4KB)   │       │
│   │ "users" │        │ Query   │          │ B-Tree  │       │
│   └─────────┘        └─────────┘          └─────────┘       │
│                           │                      │           │
│                           ▼                      ▼           │
│                     ┌─────────┐          ┌─────────┐       │
│                     │ Schema   │          │ File    │       │
│                     │ Tables   │          │ .db     │       │
│                     └─────────┘          └─────────┘       │
│                                                              │
└─────────────────────────────────────────────────────────────┘

Cette section est la plus complexe. On va simplifier en implémentant :

  • Tables avec schéma
  • SQL basique : CREATE TABLE, INSERT, SELECT, WHERE, DELETE
  • Stockage en fichier JSON (pas optimisé, mais pédagogique)

Implémentation simplifiée

// Database from scratch (SQLite-like simplifie)

const fs = require('fs');
const path = require('path');

class Database {
  constructor(dbPath = 'database.json') {
    this.dbPath = dbPath;
    this.tables = {};
    this.loadFromDisk();
  }
  
  // ===================
  // CHARGEMENT / SAUVEGARDE
  // ===================
  
  loadFromDisk() {
    try {
      if (fs.existsSync(this.dbPath)) {
        const data = JSON.parse(fs.readFileSync(this.dbPath, 'utf-8'));
        this.tables = data;
      }
    } catch (e) {
      this.tables = {};
    }
  }
  
  saveToDisk() {
    fs.writeFileSync(this.dbPath, JSON.stringify(this.tables, null, 2));
  }
  
  // ===================
  // CREATE TABLE
  // ===================
  
  createTable(name, columns) {
    if (this.tables[name]) {
      throw new Error(`Table ${name} existe deja`);
    }
    
    this.tables[name] = {
      columns: columns, // [{ name, type }, ...]
      data: [],
      nextId: 1
    };
    
    this.saveToDisk();
    return { message: `Table ${name} creee` };
  }
  
  // ===================
  // DROP TABLE
  // ===================
  
  dropTable(name) {
    if (!this.tables[name]) {
      throw new Error(`Table ${name} n'existe pas`);
    }
    
    delete this.tables[name];
    this.saveToDisk();
    return { message: `Table ${name} supprimee` };
  }
  
  // ===================
  // INSERT
  // ===================
  
  insert(tableName, row) {
    const table = this.tables[tableName];
    if (!table) {
      throw new Error(`Table ${tableName} n'existe pas`);
    }
    
    // Valider les colonnes
    const rowWithId = { id: table.nextId };
    
    for (const col of table.columns) {
      if (row[col.name] === undefined && col.type !== 'AUTO_INCREMENT') {
        throw new Error(`Colonne ${col.name} requise`);
      }
      rowWithId[col.name] = row[col.name] !== undefined ? row[col.name] : null;
    }
    
    table.data.push(rowWithId);
    table.nextId++;
    this.saveToDisk();
    
    return { id: rowWithId.id };
  }
  
  // ===================
  // SELECT
  // ===================
  
  select(tableName, options = {}) {
    const table = this.tables[tableName];
    if (!table) {
      throw new Error(`Table ${tableName} n'existe pas`);
    }
    
    let result = [...table.data];
    
    // WHERE
    if (options.where) {
      result = result.filter(row => this._matchWhere(row, options.where));
    }
    
    // ORDER BY
    if (options.orderBy) {
      const { column, direction = 'ASC' } = options.orderBy;
      result.sort((a, b) => {
        if (a[column] < b[column]) return direction === 'ASC' ? -1 : 1;
        if (a[column] > b[column]) return direction === 'ASC' ? 1 : -1;
        return 0;
      });
    }
    
    // LIMIT
    if (options.limit) {
      result = result.slice(0, options.limit);
    }
    
    // OFFSET
    if (options.offset) {
      result = result.slice(options.offset);
    }
    
    // COLUMNS (selection)
    if (options.columns && !options.columns.includes('*')) {
      result = result.map(row => {
        const newRow = {};
        for (const col of options.columns) {
          newRow[col] = row[col];
        }
        return newRow;
      });
    }
    
    return result;
  }
  
  _matchWhere(row, where) {
    // Support: { column: value } ou { column: { op: value } }
    for (const [col, condition] of Object.entries(where)) {
      if (typeof condition === 'object' && condition !== null) {
        // Operateur
        const [op, val] = Object.entries(condition)[0];
        if (!this._compare(row[col], op, val)) {
          return false;
        }
      } else {
        // Egalite
        if (row[col] !== condition) {
          return false;
        }
      }
    }
    return true;
  }
  
  _compare(a, op, b) {
    switch (op) {
      case 'eq': return a === b;
      case 'ne': return a !== b;
      case 'gt': return a > b;
      case 'gte': return a >= b;
      case 'lt': return a < b;
      case 'lte': return a <= b;
      case 'like': return String(a).toLowerCase().includes(String(b).toLowerCase());
      default: return false;
    }
  }
  
  // ===================
  // UPDATE
  // ===================
  
  update(tableName, updates, where) {
    const table = this.tables[tableName];
    if (!table) {
      throw new Error(`Table ${tableName} n'existe pas`);
    }
    
    let count = 0;
    
    for (let i = 0; i < table.data.length; i++) {
      if (this._matchWhere(table.data[i], where)) {
        for (const [key, value] of Object.entries(updates)) {
          if (key !== 'id') {
            table.data[i][key] = value;
          }
        }
        count++;
      }
    }
    
    this.saveToDisk();
    return { updated: count };
  }
  
  // ===================
  // DELETE
  // ===================
  
  delete(tableName, where) {
    const table = this.tables[tableName];
    if (!table) {
      throw new Error(`Table ${tableName} n'existe pas`);
    }
    
    const before = table.data.length;
    table.data = table.data.filter(row => !this._matchWhere(row, where));
    const after = table.data.length;
    
    this.saveToDisk();
    return { deleted: before - after };
  }
  
  // ===================
  // UTILITAIRES
  // ===================
  
  getTables() {
    return Object.keys(this.tables);
  }
  
  getSchema(tableName) {
    const table = this.tables[tableName];
    if (!table) {
      throw new Error(`Table ${tableName} n'existe pas`);
    }
    return table.columns;
  }
  
  count(tableName, where = null) {
    const table = this.tables[tableName];
    if (!table) {
      throw new Error(`Table ${tableName} n'existe pas`);
    }
    
    if (!where) {
      return table.data.length;
    }
    
    return table.data.filter(row => this._matchWhere(row, where)).length;
  }
}

// ===================
// TEST DE LA BASE DE DONNEES
// ===================

const db = new Database('data/mydb.json');

console.log('=== CREATION DES TABLES ===\n');

db.createTable('users', [
  { name: 'id', type: 'AUTO_INCREMENT' },
  { name: 'nom', type: 'TEXT' },
  { name: 'email', type: 'TEXT' },
  { name: 'age', type: 'INT' }
]);

db.createTable('posts', [
  { name: 'id', type: 'AUTO_INCREMENT' },
  { name: 'user_id', type: 'INT' },
  { name: 'title', type: 'TEXT' },
  { name: 'content', type: 'TEXT' }
]);

console.log('Tables:', db.getTables());

console.log('\n=== INSERTIONS ===\n');

db.insert('users', { nom: 'Alice', email: 'alice@test.com', age: 30 });
db.insert('users', { nom: 'Bob', email: 'bob@test.com', age: 25 });
db.insert('users', { nom: 'Charlie', email: 'charlie@test.com', age: 35 });

db.insert('posts', { user_id: 1, title: 'Premier post', content: 'Contenu du post...' });
db.insert('posts', { user_id: 2, title: 'Hello World', content: 'Salut tout le monde!' });

console.log('Utilisateurs inseres:', db.count('users'));
console.log('Posts inseres:', db.count('posts'));

console.log('\n=== SELECT * ===\n');

console.log('Tous les utilisateurs:');
console.log(db.select('users'));

console.log('\n=== SELECT WHERE ===\n');

console.log('Utilisateurs age > 28:');
console.log(db.select('users', { where: { age: { gte: 28 } } }));

console.log('\nRecherche "ali":');
console.log(db.select('users', { where: { nom: { like: 'ali' } } }));

console.log('\n=== UPDATE ===\n');

db.update('users', { age: 31 }, { id: { eq: 1 } });
console.log('Alice apres update:');
console.log(db.select('users', { where: { id: { eq: 1 } } }));

console.log('\n=== DELETE ===\n');

db.delete('users', { id: { eq: 3 } });
console.log('Apres suppression de Charlie:');
console.log(db.select('users'));

console.log('\n=== ORDER BY ===\n');

console.log('Utilisateurs tries par age DESC:');
console.log(db.select('users', { orderBy: { column: 'age', direction: 'DESC' } }));

console.log('\n=== PAGINATION ===\n');

db.insert('users', { nom: 'David', email: 'david@test.com', age: 28 });
db.insert('users', { nom: 'Eve', email: 'eve@test.com', age: 22 });

console.log('Page 1 (limit 2):');
console.log(db.select('users', { limit: 2, offset: 0 }));

console.log('\nPage 2 (limit 2, offset 2):');
console.log(db.select('users', { limit: 2, offset: 2 }));
Note : Cette implémentation est pédagogique. Une vraie BDD utilise des pages disque, un buffer pool, un WAL (Write-Ahead Log), et des B+Trees pour les index. Mais tu comprends maintenant le principe !

7. Search engine (TF-IDF)

Intermediaire Un vrai moteur de recherche avec scoring.

TF-IDF en detail

TF = Term Frequency = combien de fois le mot apparait dans le document

IDF = Inverse Document Frequency = rareté du mot dans tous les documents

TF-IDF = importance du mot pour ce document

TF (Term Frequency)
  = (nombre d'occurrences du terme t dans le document d) / (nombre total de mots dans d)
  
IDF (Inverse Document Frequency)
  = log(nombre total de documents / nombre de documents contenant t)
  
TF-IDF
  = TF × IDF
  
Plus le score est eleve, plus le terme est pertinent pour ce document

Implémentation

// Moteur de recherche TF-IDF

class SearchEngine {
  constructor() {
    this.documents = new Map();
    this.index = new Map(); // terme -> { docId: tf }
    this.docLengths = new Map();
    this.docCounter = 0;
  }
  
  // Tokenisation
  tokenize(text) {
    return text
      .toLowerCase()
      .replace(/[^\w\s]/g, '')
      .split(/\s+/)
      .filter(t => t.length > 2);
  }
  
  // Ajouter un document
  addDocument(text, metadata = {}) {
    const docId = ++this.docCounter;
    const tokens = this.tokenize(text);
    
    this.documents.set(docId, { id: docId, text, ...metadata });
    this.docLengths.set(docId, tokens.length);
    
    // Calculer TF (term frequency) pour ce document
    const tf = {};
    for (const token of tokens) {
      tf[token] = (tf[token] || 0) + 1;
    }
    
    // Normaliser TF et ajouter a l'index
    for (const [term, count] of Object.entries(tf)) {
      if (!this.index.has(term)) {
        this.index.set(term, {});
      }
      this.index.get(term)[docId] = count / tokens.length;
    }
    
    return docId;
  }
  
  // Calculer IDF
  idf(term) {
    if (!this.index.has(term)) {
      return 0;
    }
    
    const docsWithTerm = Object.keys(this.index.get(term)).length;
    return Math.log(this.documents.size / (1 + docsWithTerm));
  }
  
  // Calculer le score TF-IDF pour un document et une requete
  score(docId, queryTokens) {
    let score = 0;
    
    for (const term of queryTokens) {
      if (this.index.has(term) && this.index.get(term)[docId]) {
        const tf = this.index.get(term)[docId];
        score += tf * this.idf(term);
      }
    }
    
    return score;
  }
  
  // Rechercher
  search(query, limit = 10) {
    const queryTokens = this.tokenize(query);
    
    if (queryTokens.length === 0) {
      return [];
    }
    
    // Trouver tous les documents qui contiennent au moins un terme
    const candidateDocs = new Set();
    for (const term of queryTokens) {
      if (this.index.has(term)) {
        for (const docId of Object.keys(this.index.get(term))) {
          candidateDocs.add(parseInt(docId));
        }
      }
    }
    
    // Calculer les scores
    const results = [];
    for (const docId of candidateDocs) {
      const score = this.score(docId, queryTokens);
      if (score > 0) {
        results.push({
          ...this.documents.get(docId),
          score
        });
      }
    }
    
    // Trier par score decroissant
    results.sort((a, b) => b.score - a.score);
    
    return results.slice(0, limit);
  }
  
  // Statistiques
  stats() {
    return {
      documentCount: this.documents.size,
      termCount: this.index.size,
      avgDocLength: [...this.docLengths.values()].reduce((a, b) => a + b, 0) / Math.max(1, this.documents.size)
    };
  }
}

// Test
const engine = new SearchEngine();

// Ajouter des documents
engine.addDocument('Le chat est un animal domestique populaire', { category: 'animaux' });
engine.addDocument('Le chien est le meilleur ami de l\'homme', { category: 'animaux' });
engine.addDocument('La programmation en JavaScript est tres populaire', { category: 'tech' });
engine.addDocument('Python est un langage de programmation polyvalent', { category: 'tech' });
engine.addDocument('Les chats et les chiens sont des animaux de compagnie', { category: 'animaux' });
engine.addDocument('JavaScript et Python sont des langages de script', { category: 'tech' });

console.log('Stats:', engine.stats());

console.log('\n=== RECHERCHES ===\n');

console.log('Recherche "chat":');
console.log(engine.search('chat').map(r => ({ score: r.score.toFixed(3), text: r.text.substring(0, 50) })));

console.log('\nRecherche "programmation":');
console.log(engine.search('programmation').map(r => ({ score: r.score.toFixed(3), text: r.text.substring(0, 50) })));

console.log('\nRecherche "chat chien":');
console.log(engine.search('chat chien').map(r => ({ score: r.score.toFixed(3), text: r.text.substring(0, 50) })));

console.log('\nRecherche "javascript python":');
console.log(engine.search('javascript python').map(r => ({ score: r.score.toFixed(3), text: r.text.substring(0, 50) })));
# Moteur de recherche TF-IDF
import math
import re

class SearchEngine:
    def __init__(self):
        self.documents = {}
        self.index = {}  # terme -> { docId: tf }
        self.doc_lengths = {}
        self.doc_counter = 0
    
    def tokenize(self, text):
        """Tokenisation"""
        text = text.lower()
        text = re.sub(r'[^\w\s]', '', text)
        tokens = text.split()
        return [t for t in tokens if len(t) > 2]
    
    def add_document(self, text, metadata=None):
        """Ajouter un document"""
        if metadata is None:
            metadata = {}
        
        self.doc_counter += 1
        doc_id = self.doc_counter
        tokens = self.tokenize(text)
        
        self.documents[doc_id] = {'id': doc_id, 'text': text, **metadata}
        self.doc_lengths[doc_id] = len(tokens)
        
        # Calculer TF
        tf = {}
        for token in tokens:
            tf[token] = tf.get(token, 0) + 1
        
        # Normaliser et ajouter a l'index
        for term, count in tf.items():
            if term not in self.index:
                self.index[term] = {}
            self.index[term][doc_id] = count / len(tokens)
        
        return doc_id
    
    def idf(self, term):
        """Calculer IDF"""
        if term not in self.index:
            return 0
        docs_with_term = len(self.index[term])
        return math.log(len(self.documents) / (1 + docs_with_term))
    
    def score(self, doc_id, query_tokens):
        """Calculer TF-IDF score"""
        score = 0
        for term in query_tokens:
            if term in self.index and doc_id in self.index[term]:
                tf = self.index[term][doc_id]
                score += tf * self.idf(term)
        return score
    
    def search(self, query, limit=10):
        """Rechercher"""
        query_tokens = self.tokenize(query)
        
        if not query_tokens:
            return []
        
        # Trouver les documents candidats
        candidate_docs = set()
        for term in query_tokens:
            if term in self.index:
                candidate_docs.update(self.index[term].keys())
        
        # Calculer les scores
        results = []
        for doc_id in candidate_docs:
            score = self.score(doc_id, query_tokens)
            if score > 0:
                doc = self.documents[doc_id].copy()
                doc['score'] = score
                results.append(doc)
        
        # Trier
        results.sort(key=lambda x: x['score'], reverse=True)
        
        return results[:limit]
    
    def stats(self):
        return {
            'documentCount': len(self.documents),
            'termCount': len(self.index),
            'avgDocLength': sum(self.doc_lengths.values()) / max(1, len(self.documents))
        }

# Test
engine = SearchEngine()

# Ajouter des documents
engine.add_document('Le chat est un animal domestique populaire', {'category': 'animaux'})
engine.add_document('Le chien est le meilleur ami de l\'homme', {'category': 'animaux'})
engine.add_document('La programmation en JavaScript est tres populaire', {'category': 'tech'})
engine.add_document('Python est un langage de programmation polyvalent', {'category': 'tech'})
engine.add_document('Les chats et les chiens sont des animaux de compagnie', {'category': 'animaux'})
engine.add_document('JavaScript et Python sont des langages de script', {'category': 'tech'})

print('Stats:', engine.stats())

print('\n=== RECHERCHES ===\n')

print('Recherche "chat":')
for r in engine.search('chat'):
    print(f"  Score: {r['score']:.3f} - {r['text'][:50]}")

print('\nRecherche "programmation":')
for r in engine.search('programmation'):
    print(f"  Score: {r['score']:.3f} - {r['text'][:50]}")

print('\nRecherche "chat chien":')
for r in engine.search('chat chien'):
    print(f"  Score: {r['score']:.3f} - {r['text'][:50]}")

8. Data pipeline / ETL

Intermediaire Extraction, Transformation, Loading.

Qu'est-ce qu'un ETL ?

ETL = Extract, Transform, Load. C'est le processus de déplacer des données d'un endroit à un autre en les transformant.

EXTRACT               TRANSFORM                 LOAD
   │                      │                       │
   ▼                      ▼                       ▼
┌─────────┐          ┌─────────┐           ┌─────────┐
│ Source  │          │ Clean   │           │ Target  │
│ API     │─────────▶│ Format  │─────────▶│ Database│
│ File    │          │ Filter  │           │ File    │
│ DB      │          │ Enrich  │           │ API     │
└─────────┘          └─────────┘           └─────────┘
   │                      │                       │
   │   Donnees brutes    │   Donnees propres    │   Donnees chargees
   │   (JSON, CSV...)    │   (formatées)        │   (stockées)

Implémentation d'un pipeline

// Data Pipeline / ETL

class Pipeline {
  constructor(name) {
    this.name = name;
    this.steps = [];
    this.extractor = null;
    this.transformers = [];
    this.loader = null;
    this.errorHandler = null;
  }
  
  // ===================
  // CONFIGURATION
  // ===================
  
  extract(fn) {
    this.extractor = fn;
    return this;
  }
  
  transform(fn) {
    this.transformers.push(fn);
    return this;
  }
  
  load(fn) {
    this.loader = fn;
    return this;
  }
  
  onError(fn) {
    this.errorHandler = fn;
    return this;
  }
  
  // ===================
  // EXECUTION
  // ===================
  
  async run() {
    console.log(`Pipeline "${this.name}" demarre...`);
    const startTime = Date.now();
    
    try {
      // 1. EXTRACT
      if (!this.extractor) {
        throw new Error('Pas d\'extracteur defini');
      }
      
      console.log('  [EXTRACT] Extraction des donnees...');
      let data = await this.extractor();
      console.log(`  [EXTRACT] ${Array.isArray(data) ? data.length : 1} enregistrements extraits`);
      
      // 2. TRANSFORM
      for (let i = 0; i < this.transformers.length; i++) {
        console.log(`  [TRANSFORM] Transformation ${i + 1}/${this.transformers.length}...`);
        data = await this.transformers[i](data);
        console.log(`  [TRANSFORM] ${Array.isArray(data) ? data.length : 1} enregistrements apres transformation`);
      }
      
      // 3. LOAD
      if (this.loader) {
        console.log('  [LOAD] Chargement des donnees...');
        await this.loader(data);
        console.log('  [LOAD] Chargement termine');
      }
      
      const duration = Date.now() - startTime;
      console.log(`Pipeline "${this.name}" termine en ${duration}ms`);
      
      return { success: true, data, duration };
      
    } catch (error) {
      console.error(`Pipeline "${this.name}" EN ERREUR:`, error.message);
      
      if (this.errorHandler) {
        await this.errorHandler(error);
      }
      
      return { success: false, error: error.message };
    }
  }
}

// ===================
// EXEMPLE CONCRET
// ===================

const fs = require('fs');

// Creer le dossier data si n'existe pas
if (!fs.existsSync('data')) {
  fs.mkdirSync('data');
}

// Pipeline: API -> Clean -> Save
const pipeline = new Pipeline('Import utilisateurs');

// EXTRACT: Simuler un appel API
pipeline.extract(async () => {
  // En realite, ce serait un fetch()
  const fakeApiData = [
    { id: 1, name: 'alice', email: 'ALICE@TEST.COM', age: '30', created_at: '2024-01-15' },
    { id: 2, name: 'bob', email: 'bob@test.com', age: '25', created_at: '2024-02-20' },
    { id: 3, name: 'charlie', email: 'CHARLIE@TEST.COM', age: '35', created_at: '2024-03-10' },
    { id: 4, name: 'david', email: 'david@test.com', age: 'invalid', created_at: '2024-04-05' },
    { id: 5, name: 'eve', email: 'EVE@TEST.COM', age: '28', created_at: '2024-05-01' }
  ];
  
  // Simuler un delai
  await new Promise(r => setTimeout(r, 100));
  
  return fakeApiData;
});

// TRANSFORM: Normaliser les donnees
pipeline.transform(data => {
  return data.map(row => {
    return {
      id: row.id,
      name: row.name.toLowerCase(),
      email: row.email.toLowerCase(),
      age: parseInt(row.age) || null, // Gerer les invalides
      created_at: new Date(row.created_at),
      processed_at: new Date()
    };
  });
});

// TRANSFORM: Filtrer les invalides
pipeline.transform(data => {
  return data.filter(row => row.age !== null);
});

// TRANSFORM: Ajouter des metadonnees
pipeline.transform(data => {
  return data.map(row => ({
    ...row,
    age_group: row.age < 30 ? 'young' : 'adult',
    source: 'api_import'
  }));
});

// LOAD: Sauvegarder en JSON
pipeline.load(async data => {
  fs.writeFileSync('data/users_processed.json', JSON.stringify(data, null, 2));
});

// ERROR HANDLER
pipeline.onError(async error => {
  fs.writeFileSync('data/pipeline_errors.log', `${new Date().toISOString()}: ${error.message}\n`, { flag: 'a' });
});

// Lancer le pipeline
pipeline.run().then(result => {
  if (result.success) {
    console.log('\nDonnees finales:');
    console.log(result.data);
  }
});

// ===================
// PIPELINE PLUS COMPLEXE
// ===================

console.log('\n\n=== PIPELINE CSV -> DB ===\n');

const csvToDbPipeline = new Pipeline('Import CSV');

// EXTRACT: Lire un CSV
csvToDbPipeline.extract(async () => {
  // Simuler un CSV
  const csvData = `id,product,price,category
1,Apple,1.50,fruit
2,Banana,0.80,fruit
3,Carrot,1.20,vegetable
4,Milk,2.50,dairy
5,Cheese,4.00,dairy`;
  
  const lines = csvData.trim().split('\n');
  const headers = lines[0].split(',');
  
  return lines.slice(1).map(line => {
    const values = line.split(',');
    const row = {};
    headers.forEach((h, i) => row[h] = values[i]);
    return row;
  });
});

// TRANSFORM: Convertir les types
csvToDbPipeline.transform(data => {
  return data.map(row => ({
    id: parseInt(row.id),
    product: row.product,
    price: parseFloat(row.price),
    category: row.category
  }));
});

// TRANSFORM: Ajouter tax
csvToDbPipeline.transform(data => {
  return data.map(row => ({
    ...row,
    price_with_tax: +(row.price * 1.2).toFixed(2) // 20% tax
  }));
});

// LOAD: Grouper par categorie et sauvegarder
csvToDbPipeline.load(async data => {
  const grouped = {};
  for (const item of data) {
    if (!grouped[item.category]) {
      grouped[item.category] = [];
    }
    grouped[item.category].push(item);
  }
  
  fs.writeFileSync('data/products_by_category.json', JSON.stringify(grouped, null, 2));
  console.log('Produits sauvegardes par categorie');
});

csvToDbPipeline.run();

9. Integration avec n8n

Debutant+ Connecter ton ETL à n8n (déjà installé dans ta sandbox).

Concept

Ton n8n tourne en local. Tu peux créer des workflows qui déclenchent tes pipelines via webhook.

Architecture

n8n WORKFLOW                      TON API
                                    
┌─────────────┐                  ┌─────────────┐
│  Webhook    │                  │  POST      │
│  Trigger    │─────────────────▶│  /run-pipe │
│             │    HTTP Request  │             │
└─────────────┘                  └──────┬──────┘
                                        │
                                 ┌──────▼──────┐
                                 │  Pipeline   │
                                 │  ETL        │
                                 └──────┬──────┘
                                        │
┌─────────────┐                  ┌──────▼──────┐
│  Response   │◀─────────────────│  Resultat  │
│  Workflow  │   JSON            │  JSON      │
└─────────────┘                  └─────────────┘

Creer un endpoint pour n8n

// API pour n8n - ajouter a ton pipeline

const express = require('express');
const app = express();
app.use(express.json());

// Instance du pipeline (depuis section precedente)
const pipeline = new Pipeline('Import pour n8n');

pipeline.extract(async () => {
  // Ton extraction
  return [];
});

pipeline.transform(data => data);

pipeline.load(async data => {
  // Ton chargement
});

// Endpoint pour n8n
app.post('/run-pipeline', async (req, res) => {
  const result = await pipeline.run();
  res.json(result);
});

// Endpoint avec parametres
app.post('/run-pipeline/:name', async (req, res) => {
  const { name } = req.params;
  const { params } = req.body;
  
  // Lancer le pipeline specifie avec les params
  // ...
  
  res.json({ success: true, pipeline: name, params });
});

app.listen(3001, () => {
  console.log('API ETL sur http://localhost:3001');
  console.log('POST /run-pipeline');
  console.log('POST /run-pipeline/:name');
});

Dans n8n

  1. Créer un nouveau workflow
  2. Ajouter un Webhook Trigger (ou Schedule)
  3. Ajouter un HTTP Request node
  4. Configurer :
    • Method: POST
    • URL: http://host.docker.internal:3001/run-pipeline
    • Body: JSON avec tes paramètres
  5. Ajouter un node pour traiter la réponse
Tip : host.docker.internal permet d'atteindre ta machine depuis Docker. Si n8n est dans un conteneur, utilise cette adresse pour contacter ton API locale.

10. Deploiement

Dockerfile pour l'API

FROM node:20-alpine

WORKDIR /app

COPY package*.json ./
RUN npm ci --only=production || true

COPY . .

# Creer le dossier data
RUN mkdir -p /app/data

EXPOSE 3000

CMD ["node", "server.js"]

docker-compose.yml

services:
  kv-store:
    build: .
    container_name: kv-store
    restart: unless-stopped
    ports:
      - "3000:3000"
    volumes:
      - ./data:/app/data
    environment:
      - NODE_ENV=production

Lancer

docker-compose up -d
curl http://localhost:3000/keys

11. Pour aller plus loin

Bases de données réelles

  • SQLite — La vraie base de données légère
  • PostgreSQL — BDD relationnelle de production
  • Redis — Key-value store de production
  • MongoDB — Document store

Moteurs de recherche

Ressources d'apprentissage

Bravo ! Tu as construit un key-value store, un moteur de recherche, une base de données et un pipeline ETL from scratch. Tu comprends maintenant ce qui se passe "sous le capot" quand tu utilises Redis, SQLite ou Elasticsearch. C'est pas de la magie noire, c'est des structures de données et des algorithmes classiques.
Retour aux tutoriels