Indexation et accès disque : comprendre l’économie des I/O
Les moteurs de stockage évoluent dans un monde dominé par les contraintes physiques : le CPU est rapide et prévisible, mais les accès disques, en particulier aléatoires, sont coûteux, lents et variables. L’efficacité d’une base dépend moins de ses structures de données théoriques que de la manière dont elle minimise le travail d’I/O.
Trois idées structurent cette économie : l’écart immense entre mémoire et disque, le rôle des blocs et pages comme unités fondamentales, et le principe de localité, qui conditionne l’efficacité des lectures. Cette note expose ces concepts et montre pourquoi tout moteur moderne doit être intrinsèquement conçu pour l’I/O.
Le coût d’un accès : mémoire vs disque
Les latences entre RAM, SSD et HDD diffèrent d’un facteur de plusieurs millions. Ce fossé conditionne toute l’architecture interne des moteurs.
Ordres de grandeur :
Cache L1/L2 ~ 1–10 ns
RAM ~ 100 ns
NVMe random read ~ 50–100 µs
SSD random read ~ 100–200 µs
HDD random read ~ 5–10 ms
Réseau (LAN) ~ 0.1 ms
Réseau (WAN) ~ 10–100 ms
Un accès disque mécanique peut coûter dizaines de millions de cycles CPU.
C’est pour cette raison que les moteurs évitent les accès aléatoires, utilisent des caches, et organisent les données pour réduire au minimum les lectures.
Blocs et pages : les vraies unités d’accès
Les périphériques ne lisent pas des octets isolés : ils lisent des blocs, souvent de 4 à 16 KB.
Les moteurs alignent donc leurs structures sur des pages :
| Page 1 (4 KB) |
+---------------------------+
| Page 2 |
+---------------------------+
| Page 3 |
+---------------------------+
Pour retrouver une clé dans un B-Tree, plusieurs pages doivent être chargées : racine, niveaux intermédiaires, page feuille.
Si elles sont déjà dans le buffer cache, l’accès coûte ~100 ns.
Sinon, un accès disque complet est nécessaire.
L’indexation devient alors un problème d’optimisation de pages : comment garantir que les accès les plus fréquents resteront en mémoire ?
Localité : le levier essentiel
Localité spatiale
Des clés proches doivent résider dans les mêmes pages, afin qu’une seule lecture apporte plusieurs résultats utiles.
Localité temporelle
Les clés récemment ou fréquemment consultées doivent rester en mémoire.
Les moteurs orientent leur structure autour de ces propriétés :
B-Trees stockent les clés triées ; SSTables regroupent les données par blocs triés ; les moteurs maintiennent aussi des caches spécialisés.
Lorsque la localité s’effondre, les performances s’effondrent aussi.
Pourquoi les moteurs modernes doivent être I/O-efficient
Même avec les SSD, les écarts de latence restent énormes. Les moteurs doivent donc être conçus autour de l’idée de réduire les I/O coûteuses.
Cela influence :
- la forme des index,
- l’organisation des fichiers,
- les stratégies de cache,
- la manière de gérer les écritures,
- la logique de compaction ou de rééquilibrage.
Au final, l’I/O dicte l’architecture bien plus que les abstractions logicielles.
Conclusion
Comprendre l’économie des I/O est indispensable pour évaluer un moteur. L’écart entre la mémoire et le disque structure tout : les pages déterminent l’accès, la localité détermine la latence, et la gestion des I/O façonne les performances globales.
Les moteurs modernes sont conçus autour de cette réalité : optimiser l’I/O, éviter le travail inutile, et exploiter au maximum la mémoire.
C’est cette contrainte physique—plus que tout choix algorithmique abstrait—qui explique la diversité des architectures de stockage actuelles.
Références recommandées
- Jim Gray & A. Reuter — Transaction Processing: Concepts and Techniques
- Garcia-Molina et al. — Database Systems: The Complete Book
- Documentation PostgreSQL — Buffer Manager
- RocksDB — Block-Based Table Format
- ACM Queue — The Pathologies of Big Data