B-TREE INDEX and key redundancy

Hier c'étaient des replays de starcraft 2, une autre fois c'était Jack Bauer, ... Aujourd'hui au réveil, une soudaine envie de jouer avec des index.

Un index, c'est une structure arborescente qui, à une clef, potentiellement composite, associe une adresse (rowid) dans une table.

Le nombre d'étages de cet arbre, ou niveau de l'arbre, ou encore "b-tree level", dépend du nombre de blocs feuilles à référencer (le bloc de départ peut contenir n références vers des blocs au niveau inférieur, qui eux même peuvent contenir m références, ...), mais pas seulement !

1) Un petit exemple rigolo :

On va illustrer avec une table à deux colonnes : l'une constante, l'autre identifiant unique.  

CREATE TABLE t AS SELECT lpad('x', 255, 'X') c, level l FROM DUAL CONNECT BY level <= 1000;

On construit deux index composites sur ces deux colonnes en intervertissant l'ordre

CREATE INDEX idxt1 ON t(c, l) COMPUTE STATISTICS;

CREATE INDEX idxt2 ON t(l, c) COMPUTE STATISTICS;

Et là, on vérifie le niveau du b-tree index :

SELECT index_name, blevel
FROM dba_indexes
WHERE table_name = 'T';

INDEX_NAME                         BLEVEL
------------------------------ ----------
IDXT1                                   2
IDXT2                                   1

Quand on met la colonne la plus sélective en premier, ça baisse le niveau de l'index !

2) Ca marche aussi pour les index concaténés au lieu de composites

CREATE INDEX IDXT3 ON t(c||l) COMPUTE STATISTICS;

CREATE INDEX IDXT4 ON t(l||c) COMPUTE STATISTICS;

SELECT index_name, blevel
FROM dba_indexes
WHERE table_name = 'T';

INDEX_NAME                         BLEVEL
------------------------------ ----------
IDXT1                                   2
IDXT2                                   1
IDXT3                                   2
IDXT4                                   1

Même sentence.

L'idée en fait, c'est que pour référencer un niveau inférieur de l'arbre, vous n'avez pas besoin de toute la clef.

Supposez que dans le premier niveau d'indirection, vous référenciez un bloc feuille de la manière suivante :
Pour les valeurs entre '1;xxx...x' à '500;xxx...x', rendez-vous bloc 4233 !
... se reformule aisément en :
Pour les valeurs entre '1*' à '500*', rendez-vous bloc 4233 !
=> Les références sont beaucoup plus courtes, on peut en coincer beaucoup plus dans un bloc, et on a donc besoin de moins de niveaux d'indirection !

3) La même bien sûr sans concaténation de l'index

Cette fois, le pattern est présent naturellement dans la colonne.

CREATE TABLE u AS SELECT level || lpad('x', 255, 'X') c FROM DUAL CONNECT BY level <= 1000;

CREATE INDEX idxu1 ON u(c) COMPUTE STATISTICS;

CREATE TABLE W AS SELECT lpad('x', 255, 'X') ||level c FROM DUAL CONNECT BY level <= 1000;

CREATE INDEX idxw1 ON w(c) COMPUTE STATISTICS;

SELECT index_name, blevel
FROM dba_indexes
WHERE table_name IN ('U', 'W');

INDEX_NAME                         BLEVEL
------------------------------ ----------
IDXU1                                   1
IDXW1                                   2

Exactement la même... comme on pouvait s'y attendre.
C'est dans le mécanisme même de construction de l'index.

4) Juste pour déconner

Sur un index à forte redondance sur les premières positions de la clef composite, on peut (depuis 9i si je ne me trompe pas), compresser :

ALTER INDEX idxt1 REBUILD COMPRESS 1 COMPUTE STATISTICS;

SELECT index_name, blevel
FROM dba_indexes
WHERE table_name = 'T';

INDEX_NAME                         BLEVEL LEAF_BLOCKS
------------------------------ ---------- -----------
IDXT1                                   1           3
IDXT2                                   1          39
IDXT3                                   2          39
IDXT4                                   1          39

IDXT1 est devenu tout petit non seulement quant à son niveau, mais aussi pour les blocs feuilles qui sont elles aussi compressés.... c'est Imbattable :)