Indexation et accès disque : comprendre l’économie des I/O

Les moteurs de stockage évoluent dans un monde régi par des contraintes physiques. Les cycles CPU sont abondants et prévisibles, mais les opérations disque (en particulier les lectures aléatoires) sont coûteuses, lentes et fortement variables. L’efficacité d’un moteur de base de données dépend non seulement de la manière dont il stocke les données, mais surtout de sa capacité à minimiser le nombre, le coût et l’imprévisibilité des opérations d’I/O.

Au cœur de ce défi se trouvent trois idées : l’écart immense entre la latence mémoire et disque, l’importance des blocs et pages comme unités fondamentales d’accès, et le principe de localité, qui détermine si les lectures seront rapides… ou péniblement lentes. Cette note explore ces concepts et explique pourquoi tout moteur de stockage moderne doit être explicitement conçu autour de l’efficacité I/O.

Qu’est-ce qu’une I/O ?

I/O (Input/Output) désigne toute opération au cours de laquelle le CPU doit échanger des données avec quelque chose en dehors de son espace de calcul immédiat. Cela concerne principalement le stockage persistant (SSD/HDD/NVMe), mais aussi le réseau.

En pratique, une I/O se produit chaque fois que le moteur doit :

• charger une page depuis le disque,
• flusher des pages « sales » (dirty pages),
• ajouter une entrée au WAL,
• lire des blocs lors de scans ou de compactions.

Le point essentiel est le suivant : alors que CPU et RAM sont rapides, les I/O sont lentes et imprévisibles. Elles introduisent des pics de latence, limitent le throughput, et dominent la performance dès que les données ne tiennent plus en mémoire. C’est pourquoi les moteurs de stockage ne sont pas optimisés en priorité autour des algorithmes, mais autour de la réduction, du façonnage et du masquage des I/O.

Le coût d’accès : mémoire vs disque

Même si les CPUs sont devenus exponentiellement plus rapides, la performance des disques a progressé beaucoup plus lentement. L’écart de latence entre mémoire et disque est spectaculaire, et il influence presque tous les choix de conception internes d’un moteur.

Ordres de grandeur approximatifs des latences :

Accès registre CPU            ~ 1 ns
Cache L1/L2                   ~ 1–10 ns
Accès RAM                     ~ 100 ns
Lecture aléatoire NVMe         ~ 50–100 µs
Lecture aléatoire SSD          ~ 100–200 µs
Lecture aléatoire HDD          ~ 5–10 ms
Aller-retour réseau (LAN)      ~ 0.1 ms
Aller-retour réseau (WAN)      ~ 10–100 ms

Une milliseconde correspond à un million de nanosecondes. Un accès aléatoire sur HDD représente donc des dizaines de millions de cycles CPU.

Cet écart explique pourquoi les moteurs évitent les I/O aléatoires, batchent les écritures, utilisent des buffers et des caches de pages, et pourquoi des structures comme les B-Trees et les LSM-Trees existent.

Chaque algorithme à l’intérieur d’un moteur de stockage est, consciemment ou non, une tentative de minimiser les I/O coûteuses.

Blocs et pages : les unités qui comptent

Les périphériques de stockage ne lisent pas les octets un par un. Ils lisent des blocs — typiquement des chunks de 4 KB, 8 KB ou 16 KB. Les moteurs structurent donc leurs fichiers en pages, alignées sur le matériel sous-jacent.

+---------------------------+
|  Page 1 (ex. 4 KB)        |
+---------------------------+
|  Page 2                   |
+---------------------------+
|  Page 3                   |
+---------------------------+

Lorsqu’un lookup cherche une seule clé dans un B-Tree, le moteur doit charger :

1. la page contenant le nœud racine,
2. la/les page(s) des nœuds intermédiaires,
3. la page contenant la clé (ou la valeur).

Même une requête simple peut déclencher plusieurs lectures de pages. Des moteurs comme PostgreSQL, InnoDB ou WiredTiger s’appuient fortement sur des buffer pools pour garder en mémoire les pages les plus consultées. Si une page est déjà dans le buffer pool, l’accès coûte environ ~100 ns. Sinon, le moteur paie la latence complète du disque.

Une indexation efficace est donc l’art de prédire quelles pages sont les plus importantes et de façonner les layouts de données pour minimiser les lectures aléatoires.

Localité : le levier secret des performances

La localité — à la fois spatiale et temporelle — est le concept le plus important pour construire des systèmes efficaces en I/O.

Localité spatiale

Si des clés liées sont stockées proches les unes des autres, une seule lecture de page ramène plusieurs valeurs utiles. C’est pourquoi les SSTables et les B-Trees stockent les données dans un ordre trié.

Localité temporelle

Les workloads accèdent souvent aux mêmes clés de manière répétée. Les moteurs exploitent cela en mettant en cache les pages « chaudes » (hot pages) en mémoire.

Lorsque la localité est mauvaise — clés dispersées dans des pages non liées — l’amplification de lecture augmente fortement, les requêtes ralentissent, et le sous-système I/O est saturé.

Les meilleurs moteurs sont conçus pour que la localité devienne le comportement par défaut.

Pourquoi les moteurs modernes doivent être efficaces en I/O

Même avec des SSD et des NVMe, l’accès aléatoire reste plusieurs ordres de grandeur plus lent que la mémoire. Et à mesure que les datasets grossissent et que les workloads se diversifient, les moteurs doivent être explicitement construits autour de l’économie des I/O.

Cela impacte chaque sous-système majeur :

• L’indexation doit réduire la profondeur du chemin d’accès à la donnée.
• Les layouts doivent maximiser l’I/O séquentielle et la localité.
• Le caching doit minimiser les page faults inutiles.
• Le write path doit exploiter les écritures séquentielles pour éviter la fragmentation.
• La compaction / rééquilibrage doit maintenir la structure sans submerger le système.

Qu’un moteur utilise des B-Trees ou des LSM-Trees, qu’il soit transactionnel ou analytique, qu’il tourne sur un laptop ou sur un cluster distribué : l’économie des I/O façonne la performance plus que tout autre facteur.

Au final, concevoir des moteurs de stockage revient à gérer un déséquilibre permanent : CPU rapides vs disques lents. Les I/O sont le goulot d’étranglement qui ne disparaît jamais complètement.

Conclusion

Comprendre l’économie des I/O est essentiel pour évaluer ou concevoir un moteur de base de données. Les écarts de latence entre mémoire et disque créent des ruptures de performance ; les blocs et pages imposent des contraintes d’alignement ; la localité détermine si les requêtes restent prévisibles ou se dégradent brutalement.

Chaque décision majeure dans un moteur — indexation, layout fichier, stratégie de cache, chemin d’écriture — vise à minimiser les I/O coûteuses. Une fois cette réalité comprise, l’architecture des moteurs modernes devient plus lisible : ce sont des systèmes sophistiqués conçus pour naviguer dans les contraintes physiques du stockage.

Références recommandées

1. Jim Gray & A. Reuter — Transaction Processing: Concepts and Techniques
2. Garcia-Molina et al. — Database Systems: The Complete Book
3. PostgreSQL Internals — Buffer Manager and Page Layout
4. LevelDB / RocksDB — Block-Based Table Format
5. ACM Queue — The Pathologies of Big Data