Les bases de données
Partie 3 sur 4
7Les index et la rapiditéApprofondir
Pour trouver un client par son nom dans une table de dix millions de lignes, la méthode naïve consiste à lire toutes les lignes, une par une. Un index fait comme l’index d’un livre : une structure annexe, triée, qui indique directement où se trouvent les lignes recherchées. La structure la plus utilisée est l’arbre B (en anglais B-tree), inventé au début des années 1970 : un arbre très large et très peu profond, où chaque nœud oriente la recherche vers la bonne branche. Trois ou quatre lectures de pages suffisent pour retrouver une ligne parmi des millions (exercice 5).
Les index ont un coût : ils occupent de la place, et chaque insertion ou modification doit les mettre à jour. On les crée donc sur les colonnes souvent utilisées dans les recherches et les liens entre tables, pas partout. L’optimiseur décide, pour chaque requête, s’il vaut mieux utiliser un index ou lire toute la table.
8Les modèles de bases de données
8.1Les cinq modèles classiques
Les bases de données sont apparues à une époque où se faisait sentir le besoin d’un système de gestion de l’information souple. On les date parfois de la fin des années 1960 ; elles sont un peu plus anciennes : IDS (Integrated Data Store), conçu par Charles Bachman chez General Electric, fonctionne dès 1964, et IMS (Information Management System), d’IBM, est développé à partir de 1966 pour le programme spatial Apollo. On distingue classiquement cinq modèles de SGBD, selon la manière dont ils représentent les données (figure 3) :
- le modèle hiérarchique : les données sont classées selon une arborescence descendante, où chaque enregistrement a un seul parent. Ce modèle, celui d’IMS, utilise des pointeurs entre les enregistrements. C’est le premier modèle de SGBD ;
- le modèle réseau : comme le modèle hiérarchique, il utilise des pointeurs vers des enregistrements, mais la structure n’est plus forcément arborescente : un enregistrement peut avoir plusieurs parents. Il a été normalisé à partir de 1969 par le groupe CODASYL (Conference on Data Systems Languages), qui avait déjà créé le langage Cobol ;
- le modèle relationnel (SGBDR, système de gestion de bases de données relationnelles) : les données sont enregistrées dans des tableaux à deux dimensions, des lignes et des colonnes, appelés tables ou relations. Leur manipulation s’appuie sur la théorie mathématique des relations. Proposé en 1970 par Edgar F. Codd, chercheur chez IBM, il a supplanté les précédents parce qu’il libère le programmeur de la navigation entre pointeurs : on décrit ce que l’on veut, le SGBD trouve le chemin ;
- le modèle déductif : les données sont représentées sous forme de tables, mais on les manipule par le calcul des prédicats, c’est-à-dire par des règles logiques, à la manière du langage Prolog ; un SGBD peut ainsi déduire de nouveaux faits, comme tous les ancêtres d’une personne à partir de la relation « parent de ». Resté surtout un sujet de recherche, il a influencé la gestion des requêtes récursives dans SQL ;
- le modèle objet (SGBDO, système de gestion de bases de données objet) : les données sont stockées sous forme d’objets, c’est-à-dire de structures appelées classes qui regroupent des données membres et des méthodes (voir la programmation orientée objet). On lit parfois que « les champs sont des instances de ces classes » : ce sont en réalité les objets qui sont des instances des classes, les champs étant leurs données membres. Les bases objet n’ont jamais percé à grande échelle ; les bases relationnelles ont plutôt intégré certaines de leurs idées, et des bibliothèques font le lien entre objets des programmes et tables des bases.
8.2La domination du relationnel
À la fin des années 1990, les bases relationnelles représentaient environ les trois quarts des bases de données. Elles restent aujourd’hui largement majoritaires : les classements de popularité placent toujours en tête Oracle, MySQL, Microsoft SQL Server et PostgreSQL. Leur force tient à la solidité de leur fondement mathématique, au langage SQL, normalisé et connu de tous les développeurs, et aux garanties de cohérence des transactions.
8.3Les bases NoSQL et les nouveaux modèles
Dans les années 2000, les géants du Web, confrontés à des volumes de données et à des nombres d’utilisateurs inédits, ont développé d’autres modèles, regroupés sous l’étiquette NoSQL (Not only SQL, « pas seulement SQL ») : bases clé-valeur, très rapides, qui associent une valeur à une clé, comme un dictionnaire ; bases orientées documents, qui stockent des documents souples au format JSON, un format texte structuré (voir XML et JSON) ; bases orientées colonnes, pour des volumes gigantesques répartis sur des centaines de serveurs ; bases orientées graphes, pour les données faites de relations, comme les réseaux sociaux. Plus récemment sont apparues les bases vectorielles, qui retrouvent les documents dont le sens est proche d’une question, au service de l’intelligence artificielle (voir l’IA générative), et les bases de séries temporelles, pour les mesures de capteurs. Ces modèles complètent le relationnel plus qu’ils ne le remplacent : une même application en combine souvent plusieurs (voir les bases NoSQL et le big data).
Pour s’exercer
Exercice 4 : choisir un modèle
Quel type de base conviendrait le mieux à chacun de ces besoins ? a) les comptes et les opérations d’une banque ; b) les relations d’amitié d’un réseau social, pour suggérer « les amis de vos amis » ; c) un catalogue de produits très variés, des vêtements aux téléviseurs, chacun avec ses propres caractéristiques ; d) les sessions des utilisateurs connectés à un site, consultées à chaque page.
Voir la réponse
a) Une base relationnelle : structure stable, règles d’intégrité strictes, transactions ACID indispensables. b) Une base orientée graphes, faite pour parcourir rapidement des relations sur plusieurs niveaux ; une base relationnelle peut le faire, mais de plus en plus lentement à chaque niveau de profondeur. c) Une base orientée documents, qui accepte des documents de structures différentes ; une base relationnelle moderne peut aussi stocker une partie des caractéristiques au format JSON. d) Une base clé-valeur en mémoire, très rapide, où la clé est l’identifiant de session. Dans la réalité, un site marchand combine souvent plusieurs de ces bases.
Exercice 5 : l’intérêt d’un index
Une table compte dix millions de clients. Combien de comparaisons faut-il, au pire, pour retrouver un client par son nom a) en lisant toute la table ; b) par une recherche dichotomique dans une liste triée, qui coupe l’intervalle en deux à chaque étape ? c) Pourquoi un arbre B fait-il encore mieux en nombre de lectures sur le disque ?
Voir la réponse
a) Dix millions de comparaisons, une par ligne. b) Il faut couper en deux jusqu’à n’avoir plus qu’un élément : 223 vaut environ 8,4 millions et 224 environ 16,8 millions, donc 24 comparaisons suffisent. c) Le coût réel tient surtout au nombre de pages lues sur le disque. Un nœud d’arbre B occupe une page et contient des centaines de clés : chaque lecture divise l’espace de recherche par plusieurs centaines au lieu de deux. Avec 500 clés par nœud, trois niveaux couvrent 5003, soit 125 millions d’entrées : trois ou quatre lectures de pages suffisent, et les premiers niveaux restent en général en mémoire.