B-Tree Index

B-Tree Index est la structure d'index la plus courante en bases de données relationnelles (Postgres, MySQL, Oracle, SQL Server par défaut). Arbre équilibré (balanced) permettant lookup, insertion, et range queries en O(log n) — temps logarithmique.

Fonctionnement : nodes contiennent multiple keys et pointers vers child nodes ; arbre maintenu équilibré via splits/merges. Variantes : B+ tree (data only in leaves, leaves chaînées pour range queries efficient — used par la plupart des SGBD).

Use cases optimal :
(1) **Equality lookups** — `WHERE id = 42` ;
(2) **Range queries** — `WHERE created_at BETWEEN ... AND ...`, `WHERE price > 100` ;
(3) **Sorting** — index ordering can satisfy `ORDER BY`;
(4) **Pattern matching prefix** — `WHERE name LIKE 'John%'` (mais pas `%John`) ;
(5) **Multi-column indexes** — composite (a,b,c) supports queries on a, (a,b), (a,b,c), partial matches.

Use cases sub-optimal — utiliser autres index types :
(1) **Full-text search** → GIN, GiST (Postgres), FULLTEXT (MySQL).
(2) **Hash equality only** → Hash index (memory-only Postgres).
(3) **Geographic data** → R-Tree, GiST.
(4) **JSON queries** → GIN.
(5) **Bit-vector workloads** → Bitmap (Oracle, ClickHouse).

Best practices :
(1) **Index foreign keys** ;
(2) **Composite index column order** — most selective first, ou ordered to match common query patterns ;
(3) **Covering index** (include other columns in index for index-only scan, evite table lookup — Postgres `INCLUDE`, MySQL secondary index include) ;
(4) **Partial index** — only index subset rows (`WHERE status='active'`) — smaller index ;
(5) **Expression index** — index on function result (`LOWER(email)`) ;
(6) **Monitor unused indexes** — drop them (overhead writes) ; pg_stat_user_indexes pour Postgres.

Coûts : indexes accélèrent reads mais ralentissent writes (chaque insert/update/delete maintient les indexes). Trade-off à monitor selon workload. Compétences DP-300, DEA-C01.