Stockage et indexation

À son niveau le plus fondamental, une base de données fait deux choses : quand vous lui confiez des données, elle les stocke ; quand vous les redemandez plus tard, elle vous les rend. Le chapitre précédent regardait cette mécanique du point de vue de l'application — les modèles de données et les langages de requête. Ce chapitre adopte le point de vue de la base : comment ranger les données qu'on lui donne, et comment les retrouver lorsqu'on les réclame.

Pourquoi, en tant que développeur d'application, devriez-vous vous soucier de la cuisine interne d'un moteur de stockage ? Probablement parce que vous n'en écrirez jamais un vous-même, mais que vous devrez en choisir un adapté à votre charge, parmi les nombreux disponibles. Pour régler correctement un moteur, il faut une idée approximative de ce qu'il fait sous le capot. Et la grande ligne de partage, sur laquelle s'ouvre ce chapitre, oppose les moteurs optimisés pour le transactionnel à ceux optimisés pour l'analytique.

La base la plus simple : un journal

Commençons par la base de données la plus simple du monde, deux fonctions Bash. La première ajoute une paire clé-valeur à la fin d'un fichier ; la seconde recherche la dernière occurrence d'une clé.

db_set () { echo "$1,$2" >> database; }
db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1; }

Le format de stockage sous-jacent est trivial : un fichier texte où chaque ligne contient une paire clé-valeur, à la manière d'un CSV. Chaque appel à db_set ajoute en fin de fichier (append-only) ; les anciennes versions d'une valeur ne sont pas écrasées, d'où le tail -n 1 pour retrouver la plus récente. De nombreuses bases utilisent en interne un tel journal (log) — un fichier de données en ajout seul — et la performance en écriture est excellente, car ajouter en fin de fichier est l'opération la plus simple qui soit.

Le problème est en lecture. Notre db_get doit parcourir tout le fichier du début à la fin à chaque recherche : son coût est en O(n). Si vous doublez le nombre d'enregistrements, la recherche prend deux fois plus de temps. Pour retrouver efficacement la valeur d'une clé, il faut une structure différente : un index. L'idée générale est de garder des métadonnées à côté, qui agissent comme un panneau indicateur pour localiser la donnée voulue.

C'est ici qu'apparaît le compromis fondamental du stockage : un index bien choisi accélère les lectures, mais tout index ralentit les écritures, car il faut le mettre à jour à chaque écriture de données. Aucune structure ne bat la performance d'un simple ajout en fin de fichier. Voilà pourquoi les bases n'indexent pas tout par défaut : elles vous laissent choisir les index manuellement, en fonction des motifs de requête typiques de l'application.

Deux grandes familles de moteurs de stockage répondent à ce compromis : les moteurs journalisés (log-structured) et les moteurs orientés pages (page-oriented), dont l'arbre B est le représentant.

Famille journalisée : index de hachage

Commençons par les index de données clé-valeur. Un magasin clé-valeur ressemble au type dictionnaire des langages de programmation, généralement implémenté par une table de hachage (hash map). Puisque nous avons déjà des tables de hachage en mémoire, pourquoi ne pas les utiliser pour indexer nos données sur disque ?

La stratégie d'indexation la plus simple : maintenir en mémoire un index de hachage (hash index) où chaque clé pointe vers un décalage en octets (byte offset) dans le fichier de données — l'emplacement exact où lire la valeur. À chaque ajout d'une paire, on met aussi à jour la table de hachage. À la lecture, on cherche le décalage dans la table, on se positionne au bon endroit et on lit la valeur.

C'est exactement ce que fait Bitcask, le moteur par défaut de Riak. Il offre des lectures et écritures très rapides, à une condition : toutes les clés doivent tenir en RAM, puisque la table de hachage reste entièrement en mémoire. Les valeurs, elles, peuvent dépasser la mémoire disponible, car un seul accès disque suffit à les charger. Ce moteur convient bien aux situations où la valeur de chaque clé est mise à jour très fréquemment — par exemple le nombre de lectures d'une vidéo : beaucoup d'écritures, mais peu de clés distinctes.

// Mini index de hachage append-only sur un fichier de données.
class HashIndexStore {
  private index = new Map<string, number>(); // clé -> décalage

  set(key: string, value: string): void {
    const offset = this.appendToLog(`${key},${value}\n`);
    this.index.set(key, offset); // insertion OU mise à jour
  }

  get(key: string): string | undefined {
    const offset = this.index.get(key);
    if (offset === undefined) return undefined;
    return this.readValueAt(offset);
  }
}

Comme on ne fait qu'ajouter, le fichier grossit indéfiniment. La solution : découper le journal en segments de taille fixée et appliquer une compaction sur chacun. Compacter, c'est jeter les clés en double et ne garder que la mise à jour la plus récente de chaque clé. Comme la compaction réduit souvent fortement la taille des segments, on en profite pour fusionner (merge) plusieurs segments à la fois. Les segments étant immuables une fois écrits, la fusion se fait dans un thread d'arrière-plan, sur de nouveaux fichiers, sans interrompre les requêtes ; on bascule ensuite les lectures vers le segment fusionné et on supprime les anciens.

Le choix de l'ajout seul peut sembler gaspilleur — pourquoi ne pas écraser sur place ? Mais il a plusieurs vertus :

• L'ajout et la fusion sont des écritures séquentielles, bien plus rapides que des écritures aléatoires, tant sur disques magnétiques que sur SSD.
• La reprise après panne est plus simple : pas de risque de se retrouver avec une valeur à moitié ancienne, à moitié neuve, soudées ensemble.
• La fusion évite la fragmentation des fichiers au fil du temps.

L'index de hachage a toutefois deux limites majeures, qui motivent la structure suivante. D'abord, la table doit tenir en mémoire : avec un très grand nombre de clés, un index de hachage sur disque est difficile à rendre performant (accès aléatoires nombreux, coûts d'expansion, collisions). Ensuite, les requêtes par intervalle (range queries) sont inefficaces : impossible de balayer commodément toutes les clés entre kitty00000 et kitty99999 sans les chercher une à une.

SSTables et LSM-trees

Apportons un changement simple au format des segments : exiger que la suite des paires soit triée par clé. On appelle ce format une table de chaînes triées (Sorted String Table, SSTable). On exige aussi que chaque clé n'apparaisse qu'une fois par segment fusionné — ce que la fusion garantit déjà. Le tri apporte trois avantages décisifs.

1. La fusion devient simple et efficace, même si les fichiers dépassent la mémoire : c'est l'algorithme du tri par fusion (mergesort). On lit les fichiers d'entrée côte à côte, on copie la plus petite clé dans la sortie, et on recommence. Si une même clé figure dans plusieurs segments, on garde la valeur du segment le plus récent.
2. Plus besoin d'un index complet en mémoire. Pour trouver handiwork, il suffit de connaître les décalages de handbag et handsome : le tri garantit que handiwork se situe entre les deux. On saute au décalage de handbag et on balaie à partir de là. L'index en mémoire peut donc être clairsemé (sparse) : une clé tous les quelques kilo-octets suffit.
3. Comme une lecture balaie de toute façon un intervalle de paires, on peut grouper ces enregistrements en bloc et le compresser avant écriture. Chaque entrée de l'index clairsemé pointe alors vers le début d'un bloc compressé, économisant la bande passante disque.

Reste à obtenir des données triées, alors que les écritures arrivent dans n'importe quel ordre. Maintenir une structure triée est bien plus facile en mémoire que sur disque, grâce aux arbres équilibrés (arbres rouge-noir, AVL) qui acceptent les insertions dans n'importe quel ordre et restituent les clés triées. Le moteur fonctionne alors ainsi :

// Écriture LSM : tout passe d'abord par la mémoire.
function write(key: string, value: string): void {
  appendToWAL(key, value);      // journal de reprise sur disque
  memtable.insert(key, value);  // arbre équilibré trié, en mémoire
  if (memtable.sizeInBytes() > THRESHOLD) {
    flushToSSTable(memtable);   // écrit un nouveau segment trié
    memtable = new RedBlackTree();
  }
}

// Lecture LSM : du plus récent au plus ancien.
function read(key: string): string | undefined {
  const hit = memtable.get(key);
  if (hit !== undefined) return hit;
  for (const segment of segmentsNewestFirst) {
    if (segment.bloomFilter.mightContain(key)) {
      const v = segment.lookup(key); // index clairsemé + balayage
      if (v !== undefined) return v;
    }
  }
  return undefined; // absente
}

L'arbre équilibré en mémoire est la table mémoire (memtable). Quand elle dépasse un seuil — typiquement quelques mégaoctets — on la vide sur disque (flush) sous forme de SSTable, qui devient le segment le plus récent. Une lecture consulte d'abord la memtable, puis le segment le plus récent, puis le suivant, etc. En arrière-plan, un processus de fusion et de compaction combine les segments et élimine les valeurs écrasées ou supprimées. Un journal séparé sur disque, auquel chaque écriture est immédiatement ajoutée, permet de restaurer la memtable après une panne ; il est jeté dès que la memtable est écrite en SSTable.

Cet algorithme, décrit à l'origine sous le nom d'arbre de fusion journalisé (Log-Structured Merge-Tree, LSM-Tree), est au cœur de LevelDB, RocksDB, Cassandra et HBase (ces deux derniers inspirés de l'article Bigtable de Google, qui introduisit les termes SSTable et memtable). Lucene, le moteur d'indexation d'Elasticsearch et Solr, emploie une méthode voisine pour son dictionnaire de termes.

L'idée d'une cascade de SSTables fusionnées en arrière-plan reste simple et efficace, même lorsque le jeu de données dépasse largement la mémoire. Les données étant triées, les requêtes par intervalle sont efficaces ; et comme les écritures disque sont séquentielles, le LSM-tree soutient un débit d'écriture remarquablement élevé.

Famille orientée pages : les arbres B

Les index journalisés gagnent du terrain, mais la structure d'indexation la plus répandue reste très différente : l'arbre B (B-tree). Introduit en 1970 et qualifié d'« omniprésent » moins de dix ans plus tard, il demeure l'implémentation standard dans presque toutes les bases relationnelles. Comme les SSTables, les arbres B gardent les paires triées par clé, ce qui autorise lectures et requêtes par intervalle efficaces. Mais leur philosophie de conception est tout autre.

Là où les index journalisés découpent la base en segments de taille variable écrits séquentiellement, les arbres B la découpent en pages ou blocs de taille fixe, traditionnellement 4 ko, lus et écrits une page à la fois. Cela colle au matériel, le disque étant lui-même organisé en blocs de taille fixe. Chaque page possède une adresse, ce qui permet à une page d'en référencer une autre — comme un pointeur, mais sur disque. On construit ainsi un arbre de pages.

Une page est désignée comme racine ; toute recherche y commence. Une page contient k clés et k + 1 références vers des pages enfants, chaque enfant étant responsable d'un intervalle continu de clés (en pratique, k se compte en centaines). On descend de page en page jusqu'à une page feuille (leaf page) contenant les valeurs ou des références vers elles. Le facteur de branchement (branching factor) élevé garantit un arbre peu profond : un arbre B de n clés a une hauteur en O(log n).

Pour mettre à jour une valeur, on cherche la page feuille concernée, on la modifie et on la réécrit sur place. Pour insérer une clé dans une page pleine, on la scinde en deux pages à moitié pleines et on met à jour la page parente. Cet algorithme maintient l'arbre équilibré.

Un arbre B écrit donc chaque donnée au moins deux fois : une fois dans le WAL, une fois dans la page (et encore lors des scissions). De plus, comme plusieurs threads accèdent à l'arbre en place, il faut protéger ses structures par des verrous légers (latches) — une complication que les approches journalisées évitent, faisant toute la fusion en arrière-plan. Diverses optimisations existent : copie sur écriture (copy-on-write) de LMDB en remplacement du WAL, abréviation des clés pour augmenter le facteur de branchement, pointeurs entre pages feuilles voisines pour le balayage ordonné.

LSM-tree contre arbre B : le compromis

Les implémentations d'arbres B sont en général plus matures, mais les LSM-trees séduisent par leurs caractéristiques de performance. Il n'existe aucune règle simple pour trancher : il faut tester empiriquement, sur votre charge réelle.

Critère	LSM-tree (journalisé)	Arbre B (orienté pages)
Écriture de base	Ajout en fin de fichier (séquentiel)	Écrasement de page sur place
Débit d'écriture	Élevé : écritures aléatoires transformées en séquentielles	Plus faible : écriture aléatoire + WAL
Vitesse de lecture	Bonne, mais peut consulter plusieurs segments	Souvent plus rapide : une seule place par clé
Amplification d'écriture	Due aux fusions répétées en arrière-plan	Due au WAL + réécritures de pages
Latence de queue (tail latency)	Moins prévisible : la compaction peut bloquer une requête	Plus prévisible et régulière
Copies d'une clé	Plusieurs (dans des segments distincts)	Une seule, exacte
Verrous transactionnels	Plus délicats	Faciles à attacher aux intervalles de l'arbre

Le LSM soutient un débit d'écritures aléatoires bien plus élevé, car il convertit toutes les écritures aléatoires en écritures séquentielles. Règle empirique : le LSM est plus rapide en écriture, l'arbre B plutôt en lecture — mais les benchmarks réels sont souvent peu concluants et très sensibles aux détails de la charge.

Le terme amplification d'écriture (write amplification) désigne ce phénomène : une écriture logique entraîne plusieurs écritures physiques. C'est une préoccupation particulière sur SSD, dont les blocs ne supportent qu'un nombre limité de réécritures. Enfin, l'arbre B a un atout pour les garanties transactionnelles fortes : chaque clé existe en un seul endroit, et les verrous sur intervalles de clés peuvent être attachés directement à l'arbre.

Autres structures d'index

Tout ce qui précède concernait l'index sur clé primaire (primary key), qui identifie de manière unique une ligne, un document ou un sommet. Mais il est courant d'avoir des index secondaires (secondary indexes), créés via CREATE INDEX, souvent cruciaux pour réaliser les jointures efficacement. La différence : les clés ne sont pas uniques. On résout cela soit en faisant de chaque valeur d'index une liste d'identifiants de lignes (comme une liste d'occurrences), soit en rendant chaque clé unique par un suffixe d'identifiant. Arbres B comme index journalisés conviennent.

La valeur stockée dans un index peut être de deux natures : la ligne elle-même, ou une référence vers une ligne rangée ailleurs. Dans ce dernier cas, le lieu de stockage est un fichier-tas (heap file), sans ordre particulier. Cette approche évite de dupliquer les données quand plusieurs index secondaires existent : chacun pointe vers le tas, où la donnée vit en un seul exemplaire.

Type d'index	Ce qu'il stocke	Intérêt et coût
Index sur fichier-tas	Référence vers la ligne dans le tas	Pas de duplication ; un saut d'index vers le tas à la lecture
Index agrégé (clustered)	La ligne complète dans l'index	Lecture plus rapide (pas de saut) ; plus de stockage, écritures plus lourdes
Index couvrant (covering)	Certaines colonnes incluses dans l'index	Compromis : répond à la requête « par l'index seul » sans toucher le tas

L'index agrégé (clustered index) stocke la ligne directement dans l'index pour éviter le saut vers le tas — InnoDB de MySQL en fait toujours sa clé primaire. L'index couvrant (covering index) est un compromis : il inclut quelques colonnes, de sorte que certaines requêtes sont couvertes par l'index seul. Comme toute duplication, agrégés et couvrants accélèrent les lectures mais coûtent en stockage et en écritures.

Quand il faut interroger plusieurs colonnes à la fois, un index simple ne suffit pas. L'index multi-colonnes le plus courant est l'index concaténé (concatenated index) : il combine plusieurs champs en une seule clé par juxtaposition, comme un annuaire papier indexé par (nom, prénom). Il sert à trouver tous les (nom) ou un (nom, prénom) précis, mais reste inutile pour chercher par prénom seul. Pour les données géospatiales, un index B classique ne sait pas répondre à une requête par intervalle bidimensionnelle.

SELECT * FROM restaurants
WHERE latitude  > 51.4946 AND latitude  < 51.5079
  AND longitude > -0.1162 AND longitude < -0.1004;

On utilise alors des index multidimensionnels spécialisés, comme les arbres R (R-trees) — PostGIS implémente ainsi ses index géospatiaux. L'idée déborde la géographie : un index 2D sur (date, température) retrouve toutes les observations de 2013 entre 25 et 30 °C sans balayer toute l'année. Enfin, les index flous (fuzzy) comme ceux de Lucene cherchent des mots à une certaine distance d'édition (un automate de Levenshtein), pour tolérer les fautes d'orthographe.

Tout garder en mémoire

Les structures précédentes répondent toutes aux contraintes des disques. On tolère leur lourdeur car les disques sont durables (leur contenu survit à la coupure de courant) et moins chers au gigaoctet que la RAM. Mais à mesure que la RAM se démocratise, beaucoup de jeux de données tiennent entièrement en mémoire : d'où les bases de données en mémoire (in-memory databases).

Certaines, comme Memcached, ne visent que le cache et acceptent de perdre leurs données au redémarrage. D'autres recherchent la durabilité, obtenue en écrivant un journal de changements sur disque, des instantanés périodiques, ou par réplication vers d'autres machines. VoltDB, MemSQL et Oracle TimesTen sont relationnelles ; Redis et Couchbase offrent une durabilité faible par écriture asynchrone.

Transactionnel ou analytique : OLTP contre OLAP

Aux débuts, une écriture correspondait souvent à une transaction commerciale — une vente, une commande. Le terme transaction est resté pour désigner un groupe de lectures-écritures formant une unité logique. Le motif d'accès typique — chercher un petit nombre d'enregistrements par clé via un index, insérer ou mettre à jour selon l'entrée utilisateur — a pris le nom de traitement transactionnel en ligne (online transaction processing, OLTP).

Mais les bases ont aussi servi à l'analytique, aux motifs très différents : une requête analytique balaie un nombre énorme d'enregistrements et calcule des statistiques agrégées (comptage, somme, moyenne) plutôt que de renvoyer des données brutes. Ce motif, alimentant l'informatique décisionnelle, a pris le nom de traitement analytique en ligne (online analytic processing, OLAP).

Propriété	OLTP (transactionnel)	OLAP (analytique)
Lecture principale	Peu d'enregistrements par requête, par clé	Agrégat sur un grand nombre d'enregistrements
Écriture principale	Écritures aléatoires, faible latence, depuis l'utilisateur	Import en masse (ETL) ou flux d'événements
Utilisateur principal	Client final, via une application web	Analyste interne, pour la décision
Données représentées	État courant (instant présent)	Historique des événements survenus
Taille du jeu	Gigaoctets à téraoctets	Téraoctets à pétaoctets

À l'origine, la même base servait aux deux. Mais dès la fin des années 1980 et le début des années 1990, les entreprises ont cessé de faire tourner l'analytique sur leurs systèmes OLTP — ces requêtes coûteuses, balayant de larges pans du jeu de données, nuisent aux transactions concurrentes. On les déporte vers une base séparée, l'entrepôt de données (data warehouse) : une copie en lecture seule des données de tous les systèmes OLTP de l'entreprise, alimentée par un processus d'extraction-transformation-chargement (Extract-Transform-Load, ETL). L'avantage décisif : l'entrepôt peut être optimisé pour les motifs d'accès analytiques, là où les algorithmes d'indexation vus en première moitié de chapitre conviennent à l'OLTP mais répondent mal à l'analytique.

Le schéma en étoile

En analytique, la diversité des modèles s'efface : beaucoup d'entrepôts suivent un style très standardisé, le schéma en étoile (star schema), aussi appelé modélisation dimensionnelle. Au centre trône une table de faits (fact table) : chaque ligne représente un événement survenu à un instant donné (un produit acheté par un client, une page vue). Les faits étant capturés comme événements individuels, la table de faits devient énorme — des dizaines de pétaoctets chez les grands acteurs.

Certaines colonnes de la table de faits sont des attributs (le prix de vente, le coût d'achat) ; d'autres sont des clés étrangères vers des tables de dimensions (dimension tables), qui représentent le qui, quoi, où, quand, comment et pourquoi de l'événement.

-- Cœur d'un schéma en étoile pour un détaillant.
SELECT dim_date.weekday, dim_product.category,
       SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
  JOIN dim_date    ON fact_sales.date_key    = dim_date.date_key
  JOIN dim_product ON fact_sales.product_sk  = dim_product.product_sk
WHERE dim_date.year = 2013
  AND dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY dim_date.weekday, dim_product.category;

Le nom « étoile » vient du dessin : la table de faits au milieu, entourée de ses dimensions comme les rayons d'une étoile. Une variante, le schéma en flocon (snowflake schema), décompose encore les dimensions en sous-dimensions ; plus normalisé, il est souvent moins prisé car moins simple pour les analystes.

Stockage orienté colonne

Avec des milliers de milliards de lignes, le stockage des tables de faits devient un défi. Or une requête d'entrepôt n'accède en général qu'à 4 ou 5 colonnes sur la centaine que compte une table de faits ; les SELECT * y sont rares. Dans un moteur orienté ligne (row-oriented) — celui de la plupart des bases OLTP —, toutes les valeurs d'une ligne sont rangées côte à côte ; il faut donc charger des lignes entières de plus de cent attributs, même pour n'en lire que trois.

L'idée du stockage orienté colonne (column-oriented storage) est simple : ne pas ranger ensemble les valeurs d'une ligne, mais toutes les valeurs d'une même colonne. Chaque colonne va dans un fichier séparé ; une requête ne lit et n'analyse que les colonnes qu'elle utilise. La disposition repose sur le fait que chaque fichier-colonne range les lignes dans le même ordre : la 23ᵉ entrée de chaque colonne reconstitue la 23ᵉ ligne.

Le stockage par colonne se prête remarquablement à la compression, car les valeurs d'une colonne sont souvent répétitives. Une technique très efficace en entrepôt est l'encodage par tableau de bits (bitmap encoding) : pour une colonne à n valeurs distinctes, on crée n tableaux de bits, un par valeur, avec un bit par ligne (1 si la ligne a cette valeur). Quand n est petit, c'est très compact ; sinon, on applique en plus un encodage par plages (run-length encoding) sur les tableaux clairsemés.

product_sk :        69 69 69 69 74 31 31 31 31 29 30 30 31 31 31 68 69 69

Bitmap product_sk = 31 :  0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0
Bitmap product_sk = 69 :  1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1

Encodage par plages (RLE) :
  product_sk = 31 : 5, 4, 3, 3   (5 zéros, 4 uns, 3 zéros, 3 uns…)
  product_sk = 69 : 0, 4, 12, 2  (0 zéro, 4 uns, 12 zéros, 2 uns)

Ces tableaux de bits sont parfaits pour les requêtes d'entrepôt : WHERE product_sk IN (30, 68, 69) se résout par un OU binaire des trois tableaux ; WHERE product_sk = 31 AND store_sk = 3 par un ET binaire. Comme les colonnes rangent les lignes dans le même ordre, le k-ième bit d'un tableau correspond à la même ligne que le k-ième bit d'un autre. Ces opérateurs travaillant directement sur des morceaux compressés tenant dans le cache L1 du processeur, on parle de traitement vectorisé (vectorized processing).

L'ordre de tri est lui-même un levier d'indexation. On trie la table ligne entière par ligne entière (jamais chaque colonne indépendamment, sinon on perdrait l'appariement) selon des colonnes choisies pour les requêtes fréquentes — par exemple date_key en première clé pour ne balayer que le dernier mois. Le tri renforce la compression : la première clé de tri présente de longues séquences répétées, compressibles à quelques kilo-octets même sur des milliards de lignes. C-Store et Vertica vont plus loin en stockant les mêmes données triées de plusieurs façons, profitant de la réplication déjà nécessaire.

Enfin, comme les mêmes agrégats reviennent dans beaucoup de requêtes, on les pré-calcule. Une vue matérialisée (materialized view) est une copie réelle des résultats d'une requête, écrite sur disque (contrairement à une vue virtuelle, simple raccourci). Son cas particulier est le cube de données (data cube, ou cube OLAP) : une grille d'agrégats groupés par dimensions. Certaines requêtes deviennent très rapides car déjà calculées ; en contrepartie, le cube perd la flexibilité des données brutes (impossible d'interroger une dimension absente du cube). Les entrepôts gardent donc un maximum de données brutes et n'utilisent les cubes que comme accélérateur ciblé.

À retenir

• Compromis fondamental du stockage : un index accélère les lectures mais ralentit toutes les écritures ; aucune structure ne bat l'ajout en fin de fichier (append-only) pour écrire.
• Deux familles s'opposent en OLTP. Les moteurs journalisés (index de hachage de Bitcask, SSTables et LSM-trees de LevelDB, RocksDB, Cassandra, HBase) transforment les écritures aléatoires en écritures séquentielles, d'où un fort débit d'écriture ; les filtres de Bloom y évitent les lectures pour clés absentes.
• Les arbres B écrasent des pages de taille fixe sur place, protégées par un journal d'écriture anticipée (WAL) ; ils offrent une latence plus prévisible et une seule copie par clé, précieuse pour les verrous transactionnels.
• LSM contre arbre B : pas de règle simple. LSM = écritures plus rapides mais amplification d'écriture et latence de queue moins prévisible (compaction) ; arbre B = lectures et latence plus régulières. Mesurez sur votre charge.
• Au-delà de la clé primaire : index secondaires, agrégés (clustered), couvrants, multi-colonnes et multidimensionnels (arbres R), chacun échangeant du stockage et du coût d'écriture contre de la vitesse de lecture.
• OLTP contre OLAP : le transactionnel cherche un petit nombre d'enregistrements par clé ; l'analytique balaie des millions de lignes dans un entrepôt de données modélisé en schéma en étoile. Le stockage orienté colonne — compression par tableau de bits, ordre de tri, vues matérialisées et cubes — y minimise la donnée lue sur disque.