Structures de données¶

La structure de données est le premier choix d'architecture à l'échelle d'une fonction — elle conditionne toutes les complexites qui suivent.

Pourquoi le choix de structure précédé le choix d'algorithme¶

Un algorithme brillant sur une mauvaise structure sera toujours battu par un algorithme ordinaire sur la bonne. Donald Knuth formule cela simplement : "Premature optimization is the root of all evil, but choosing the wrong data structure is premature pessimization." Le choix de structure impacte la complexité des opérations, la localité mémoire (cache-friendliness), et la lisibilite du code.

La question a se poser avant d'écrire la première ligne : quelles opérations sont fréquentes ? Accès par clé, insertion en bout, suppression en milieu, recherche par intervalle ? Chaque réponse pointe vers une famille de structures.

Tableaux et listes chaînées¶

Ces deux structures sont les primitives fondamentales. Tout le reste en dérivé ou les combine.

Tableau (Array)¶

Un tableau est un bloc contigu de mémoire. L'élément à l'indice i est à l'adresse base + i * taille_element. L'accès est O(1), independamment de n.

Cache-friendliness : la contiguïte mémoire est un avantage majeur. Quand on accede a a[i], le processeur prefetche automatiquement les éléments suivants dans la ligne de cache (64 octets sur x86). Parcourir un tableau de 10⁶ entiers est souvent 10 a 50 fois plus rapide que parcourir une liste chaînée de même taille, car chaque nœud de liste implique un accès mémoire indirect (dereferencement de pointeur).

Liste chaînée¶

Chaque nœud contient la valeur et un pointeur vers le suivant (liste simplement chaînée) ou vers le suivant et le précédent (doublement chaînée). La mémoire n'est pas contigue.

Quand préférer une liste chaînée : insertions/suppressions fréquentes en milieu de collection quand on detient déjà le pointeur sur le nœud (ex : file de priorité avec O(1) à la suppression). En pratique, les listes chaînées sont rarement la meilleure option en Python ou Java car la surchargé des objets/pointeurs efface souvent les gains théoriques face à un tableau avec décalage.

Piles et files¶

Ces deux structures abstraites définissent une politique d'accès, independamment de leur implémentation.

Pile (Stack) — LIFO¶

Last In, First Out. La dernière entree est la première sortie. Opérations : push (empiler), pop (depiler), peek (consulter le sommet).

Implémentation : tableau dynamique (Python list, Java Deque) ou liste chaînée. La version tableau est préférée pour le cache.

Cas d'usage :

• Évaluation d'expressions (notation polonaise inverse, parsing de parentheses)
• Gestion de la pile d'appels (call stack des langages)
• DFS iteratif (simulation de la recursion)
• Annuler/refaire (undo/redo)
• Vérification syntaxique (compilateurs, linters)

# Verification d'equilibrage de parentheses — O(n) temps, O(n) espace
def equilibre(s: str) -> bool:
    pile = []
    correspondance = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in '([{':
            pile.append(c)
        elif c in ')]}':
            if not pile or pile[-1] != correspondance[c]:
                return False
            pile.pop()
    return len(pile) == 0

File (Queue) — FIFO¶

First In, First Out. Opérations : enqueue (enfiler), dequeue (defiler), peek (consulter la tete).

Implémentation : collections.deque en Python (tableau circulaire doublement chaînée), ArrayDeque en Java. Ne pas utiliser une liste Python comme file (le pop(0) est O(n)).

Cas d'usage :

• BFS (parcours en largeur de graphe)
• Buffer d'événements (systèmes de messagerie, Kafka)
• Gestion des tâches en attente (thread pools, job queues)
• Impression de fichiers (FIFO des spouleurs)

File de priorité (Priority Queue) — variante ou chaque élément a une priorité. L'élément dequeue est toujours celui de plus haute (ou basse) priorité. Implémentée par un tas (heap). Cas d'usage : Dijkstra, A*, ordonnancement de processus, flux de données tries.

Arbres¶

Les arbres sont des structures hierarchiques qui permettent de concilier accès efficace et modification dynamique.

Arbre binaire de recherche (BST)¶

Invariant : pour tout nœud N, tous les éléments du sous-arbre gauche sont < N, et tous du sous-arbre droit sont > N. Recherche, insertion, suppression en O(log n) si l'arbre est équilibre.

Problème : un BST naif peut degenerer en liste chaînée si les insertions sont faites dans l'ordre croissant ou decroissant. La hauteur devient O(n) et toutes les opérations aussi.

Arbre AVL¶

Invente par Adelson-Velsky et Landis en 1962. Maintient un invariant d'équilibre strict : la différence de hauteur entre le sous-arbre gauche et droit de tout nœud est au plus 1. Toute insertion ou suppression qui viole cet invariant déclenche une rotation locale.

Rotations :

Rotation droite sur N :          Rotation gauche sur N :
    N                 G               N                 D
   / \               / \             / \               / \
  G   D    ->       A   N           G   D    ->       N   B
 / \                   / \         / \               / \
A   B                 B   D       A   B             G   A

Les rotations sont O(1) et restaurent l'équilibre localement. L'arbre AVL garantit une hauteur de O(log n), donc toutes les opérations restent O(log n) dans le pire cas.

Quand utiliser : collections dynamiques ordonnées avec nombreuses recherches. Moins utile si les modifications sont rares (un tableau trie avec recherche dichotomique suffira).

B-tree et B+tree¶

Invente par Rudolf Bayer et Edward McCreight chez Boeing en 1970. Un B-tree d'ordre t est un arbre équilibre ou chaque nœud contient entre t-1 et 2t-1 clés, et chaque nœud non-feuille a entre t et 2t enfants.

Propriété clé : un B-tree de hauteur h sur n clés vérifié n ≥ 2t^(h-1) - 1, soit une hauteur de O(log_t n). Pour t = 512 (nœud de 4 Ko, clés de 8 octets), un arbre sur 10¹² clés a une hauteur de seulement 4.

Pourquoi les bases de données utilisent les B-trees : l'accès disque est le goulot (1-10 ms par accès). Un B-tree minimise les accès disque en maximisant les clés par nœud — chaque nœud correspond exactement a une page disque (4 ou 8 Ko). PostgreSQL, MySQL InnoDB, SQLite utilisent des B+trees (toutes les clés et valeurs dans les feuilles, les nœuds internes ne stockent que les clés de navigation).

B+tree sur 3 niveaux, t=3 :

              [30 | 60]
            /     |      \
     [10|20]  [40|50]  [70|80]
     /  |  \  /  |  \  /  |  \
   [5][15][25][35][45][55][65][75][85]  <- feuilles avec valeurs

Trie (arbre préfixe)¶

Un trie stocke des chaînes de caractères en partageant les préfixes communs. Chaque nœud correspond à un caractère, et le chemin de la racine a un nœud marque "fin" représenté un mot.

Complexité : insertion et recherche en O(L) ou L est la longueur de la chaîne — independamment du nombre de mots stockes. Pour n mots de longueur L, un dictionnaire haché donne aussi O(L) mais avec collisions possibles ; le trie donne O(L) garanti et permet la recherche par préfixe en O(L).

Cas d'usage :

• Autocompletion (Google, IDEs, moteurs de recherche)
• Correcteur orthographique
• Routage IP (longest prefix matching dans les routers)
• Validation de vocabulaire (dictionnaires)

Tables de hachage¶

La table de hachage est la structure la plus fréquemment utilisée en programmation quotidienne : Python dict, Java HashMap, Redis, etc. Elle vise le O(1) amorti pour lookup, insertion et suppression.

Fonctions de hachage¶

Une fonction de hachage transforme une clé arbitraire en un indice dans un tableau de buckets. Propriétés souhaitees :

• Determinisme : la même clé donne toujours le même hash
• Uniformite : les hashes sont distribués uniformement dans [0, m[
• Rapidité : calcul en O(L) pour une clé de longueur L
• Effet avalanche : un bit change dans la clé change ~50% des bits du hash

Exemples : MurmurHash3 (usage général, rapide), FNV-1a (simple, correct), SHA-256 (cryptographique, lent pour hachage général), SipHash (Python depuis 3.6, résistant aux attaques HashDoS).

Gestion des collisions¶

Chaining (enchainage) : chaque bucket contient une liste des éléments avec le même hash. Insertion toujours en O(1), lookup en O(1 + longueur de la chaîne). Si le facteur de charge α = n/m (n éléments, m buckets) est maintenu bas (< 1), les chaînes sont courtes en esperance.

# Chaining simplifie
class TableHachage:
    def __init__(self, m=16):
        self.m = m
        self.buckets = [[] for _ in range(m)]

    def lookup(self, cle):
        h = hash(cle) % self.m
        for k, v in self.buckets[h]:
            if k == cle:
                return v
        return None

Open addressing (adressage ouvert) : tous les éléments sont stockes dans le tableau lui-même. En cas de collision, on cherche un autre slot selon une sequence de sondage :

• Linear probing : slot suivant (mauvaise distribution des clusters)
• Quadratic probing : slot + i² (meilleure distribution)
• Double hashing : hash secondaire (distribution optimale)

Facteur de charge et rehashing : quand α dépassé un seuil (0.7-0.75 pour open addressing, 1.0-2.0 pour chaining), la table est rehachee : doublement de la taille, reinsertion de tous les éléments. Le rehashing est O(n) mais amorti O(1) par insertion.

Tas (Heap)¶

Un tas est un arbre binaire presque complet maintenant un invariant d'ordre. Le max-heap garantit que chaque nœud est supérieur ou egal a ses enfants. Le min-heap garantit l'inverse. La racine contient toujours l'élément extremal.

Implémentation par tableau : un tas binaire peut être stocke efficacement dans un tableau sans pointeurs. Pour le nœud à l'indice i :

• Parent : (i - 1) // 2
• Enfant gauche : 2*i + 1
• Enfant droit : 2*i + 2

Opérations¶

Heapify de Floyd : construire un tas par insertions successives prend O(n log n). L'algorithme de Floyd reconstruit en partant des nœuds internes depuis le bas : pour chaque nœud, sift down. Complexité : O(n) — la sommation des hauteurs d'un arbre complet converge.

File de priorité et applications¶

Le tas est l'implémentation de référence des files de priorité. En Python, le module heapq fournit un min-heap. Pour un max-heap, inverser le signe des éléments ou utiliser une classe wrapper.

import heapq

# File de priorite avec min-heap
file = []
heapq.heappush(file, (3, "tache C"))
heapq.heappush(file, (1, "tache A"))
heapq.heappush(file, (2, "tache B"))

priorite, tache = heapq.heappop(file)  # (1, "tache A")

Cas d'usage :

• Algorithme de Dijkstra (plus court chemin) : extraire le nœud de distance minimale
• Algorithme de Prim (arbre couvrant minimal)
• Huffman (construction de l'arbre de codes optimaux)
• Top-k éléments dans un stream (heap de taille k)
• Ordonnancement de tâches par priorité

Table de synthèse¶

Applications en systèmes réels¶

PostgreSQL : B+tree pour les index¶

Chaque index PostgreSQL est par défaut un B+tree. Les nœuds correspondent aux pages de 8 Ko du stockage. Un index sur une colonne entière de 10⁹ lignes a une hauteur de 3-4. Une recherche par egalite ne nécessité que 3-4 accès disque, puis 1 accès à la page de données. Sans index, un SELECT ... WHERE id = x fait un full scan : O(n) accès. Avec index B+tree : O(log n) garantis.

L'index GiST (Generalized Search Tree) de PostgreSQL generalise le B-tree a des types de données géométriques, full-text, et intervalles temporels — même principe, invariants différents.

Redis : dictionnaire en mémoire¶

Redis stocke toutes ses données dans des structures en mémoire. La structure de base est une table de hachage (dict) pour les clés. Les types de valeurs utilisent des structures adaptées : les listes Redis utilisent des quicklists (listes de ziplist, tableaux compacts de petits segments), les sorted sets utilisent un skip list (liste chaînée multi-niveaux, O(log n) mais sans rotations), les HyperLogLog pour les comptages approximatifs utilisent des registres de hachage probabiliste.

Kafka : log append-only¶

Kafka n'est pas une table de hachage ni un arbre — c'est un tableau append-only sur disque, indexe par offset. L'insertion est toujours en fin de log : O(1), très rapide (accès disque séquentiel vs aléatoire). La lecture a un offset spécifique est O(1) via un index auxiliaire (offset -> position physique). La rétention est par segment de fichier — les segments anciens sont supprimes quand la rétention expire. Cette structure extremement simple permet des débits de plusieurs Go/s sur un seul broker.