Structure d'un index B-Tree, taille, nombre de lignes et autres choses

Version imprimable

18/12/2015, 10h05
Ikebukuro

Structure d'un index B-Tree, taille, nombre de lignes et autres choses

Bonjour,

Je me pose plusieurs questions sur les index B-Tree et j'aurai besoin de vos lumières; vous verrez avec ces questions que j'ai une vision floue de comment est organisé un index B-Tree mais je veux en savoir plus :

1) quelle est la taille d'un bloc racine/branche/feuille dans un index B-Tree? Si mon DB_BLOCK_SIZE est de 4Ko, est-ce que chaque bloc fait 4Ko ou bien les blocs d'un index sont différents des blocs d'un fichier de données (ce qui m'étonnerait beaucoup)?
2) quel est le nombre d'enregistrements dans un bloc d'un index B-Tree? Si le bloc feuille fait 4Ko, que mon index est sur le champ Nom (Varchar2(30) de la table TB_EMP), chaque enregistrement du bloc feuille fait 30 octets (le nom) + 10 octets (taille du rowid) soit 40 octets? Donc je pourrai mettre 4000/40 = 100 enregistrements par bloc feuille dans mon B-Tree?
3) comment est alimenté le bloc racine?
3.1) Cas d'un index sur un champ unique réparti de façon homogène : si j'ai 100 enregs dans le bloc racine, pour une table de 1 million d'enregs, avec l'index sur un champ ID number(10) allant de 1 à 1 000 000, est-ce qu'on fait 1 000 000/100 = 10 000 soit dans ma racine j'aurais 100 ID allant de 10 000 à 1 000 000 par tranche de 10 000 soit 10 000, 20 000, 30 000 ... 1 000 000?
Quid du cas où
3.2) Cas d'un index sur un champ unique réparti de façon non homogène : si j'ai 100 enregs dans le bloc racine, pour une table de 1 million d'enregs, avec l'index sur un champ ID number(10) allant de 1 à 1 000 000 000 (un milliard) MAIS avec 99,9999% des données allant de 1 à 999 999 ET une seule donnée au delà du million, valant 1 000 000 000 (un milliard), est-ce qu'on fait 1 000 000 000/100 = 10 000 000 soit dans ma racine j'aurais 100 ID allant de 10 000 000 à 1 000 000 000 par tranche de 10 000 000 soit 10 000 000, 20 000 000, 30 000 000 ... 1 000 000 000 sachant que cela ne reflète ABSOLUMENT pas la réalité?
3.3) cas d'un index sur un champ non unique : table avec un million d'enregs, je crée un index sur le champ Nom. Est-ce que Oracle va d'abord récupérer les bornes min et max de ce champ et les utiliser pour construire sa racine? Si le premier nom est "Abra" et le dernier "Zyblo", et qu'il y a 10 000 noms différents MAIS avec une répartition non homogène, comment Oracle va t-il choisir les N enregs qui vont composer la racine?
4) Est-ce que pour une valeur indexée, cette valeur peut se trouver dans N feuilles? Dans le cas où on indexe un champ non unique (le Nom par exemple), qu'il y a 2 000 fois la même valeur pour ce champ (2 000 salariés de nom "DUPONT"), est-ce que cette valeur va se retrouver dans 20 blocs feuilles contigües (un bloc pourrait contenir 100 enregs max) avec les rowids?
5) Est-ce que dans les blocs Racine et Branches le Rowid est présent? Si oui, est-ce qu'il est utilisé pour accéder à la table? D'après ce que j'ai compris on utilise les blocs Racine et Branches pour accéder aux blocs Feuilles et c'est là qu'on récupère les Rowid pour lire dans la table.
6) Est-ce que les rowid d'un bloc feuille sont lus un par un ou bien, pour une même valeur recherchée, on les lit en bloc pour diminuer le nombre d'aller/retours entre l'index et la table? Exemple : je recherche le mais des employés de nom "DURAND"; il y a 50 "DURAND" dans la société et j'accède au bloc racine de l'index sur le nom contenant le nom "DURAND" : il y a 50 rowid; Oracle les lit comment : un par un, en bloc?

Bon, ben pour un premier post sur les index c'est pas mal non :D

Merci par avance pour vos réponses.
18/12/2015, 10h22
mnitu

Bonjour,

Cette fois-ci je vous propose de commencer par la lecture de la doc d'Oracle Concepts: Overview of B-Tree Indexes suite à quoi vous allez probablement reformuler certaines de vos questions.

En matière des index d'Oracle une excellente référence est le blog de Richard Foote

Et encore à lire Richard Foote: Oracle B-Tree Index Internals
18/12/2015, 13h00
Ikebukuro

Houlala, le dernier est super dense, je vais en baver :aie:

Sinon le lien vers le site Oracle est effectivement sympa à lire.
23/12/2015, 17h28
Ikebukuro

Hello mnitu,

J'ai lu les liens et voici ce que je ne comprends toujours pas et ce que j'ai compris :

Citation:

Envoyé par Ikebukuro

1) quelle est la taille d'un bloc racine/branche/feuille dans un index B-Tree?
Il est de la taille du DB_BLOCK_SIZE.

2) quel est le nombre d'enregistrements dans un bloc d'un index B-Tree?
Cela dépend de la valeur indexée et de sa longueur (number, varchar...).

3) comment est alimenté le bloc racine?
Alors là je n'ai pas trouvé de réponse à mes questions donc je me permets de les reposer.
3.1) Cas d'un index sur un champ unique réparti de façon homogène : si j'ai 100 enregs dans le bloc racine, pour une table de 1 million d'enregs, avec l'index sur un champ ID number(10) allant de 1 à 1 000 000, est-ce qu'on fait 1 000 000/100 = 10 000 soit dans ma racine j'aurais 100 ID allant de 10 000 à 1 000 000 par tranche de 10 000 soit 10 000, 20 000, 30 000 ... 1 000 000?
Quid du cas où
3.2) Cas d'un index sur un champ unique réparti de façon non homogène : si j'ai 100 enregs dans le bloc racine, pour une table de 1 million d'enregs, avec l'index sur un champ ID number(10) allant de 1 à 1 000 000 000 (un milliard) MAIS avec 99,9999% des données allant de 1 à 999 999 ET une seule donnée au delà du million, valant 1 000 000 000 (un milliard), est-ce qu'on fait 1 000 000 000/100 = 10 000 000 soit dans ma racine j'aurais 100 ID allant de 10 000 000 à 1 000 000 000 par tranche de 10 000 000 soit 10 000 000, 20 000 000, 30 000 000 ... 1 000 000 000 sachant que cela ne reflète ABSOLUMENT pas la réalité?
3.3) cas d'un index sur un champ non unique : table avec un million d'enregs, je crée un index sur le champ Nom. Est-ce que Oracle va d'abord récupérer les bornes min et max de ce champ et les utiliser pour construire sa racine? Si le premier nom est "Abra" et le dernier "Zyblo", et qu'il y a 10 000 noms différents MAIS avec une répartition non homogène, comment Oracle va t-il choisir les N enregs qui vont composer la racine?

4) Est-ce que pour une valeur indexée, cette valeur peut se trouver dans N feuilles?
Oui.

5) Est-ce que dans les blocs Racine et Branches le Rowid est présent?
Non, le ROWID n'est que dans les feuilles.

6) Est-ce que les rowid d'un bloc feuille sont lus un par un ou bien, pour une même valeur recherchée, on les lit en bloc pour diminuer le nombre d'aller/retours entre l'index et la table? Exemple : je recherche le mais des employés de nom "DURAND"; il y a 50 "DURAND" dans la société et j'accède au bloc feuille de l'index sur le nom contenant le nom "DURAND" : il y a 50 rowid; Oracle les lit comment : un par un, en bloc?
Oracle les lit un par un.

Merci par avance pour vos réponses.

Je viens de faire le test ci-dessous

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
Connected to Oracle Database 11g Enterprise Edition Release 11.2.0.3.0 
 
SQL> 
SQL> create table test_idx (a number(12))
  2  /
Table created
SQL> insert into test_idx
  2  select level
  3   from dual
  4  connect by level <= 10000
  5  /
10000 rows inserted
SQL> insert into test_idx(a) values(1000000)
  2  /
1 row inserted
SQL> Commit
  2  /
Commit complete
SQL> create unique index ix_test_idx on test_idx(a)
  2  /
Index created
SQL> exec dbms_stats.gather_table_stats(null, 'TEST_IDX', cascade=>true)
PL/SQL procedure successfully completed
 
SQL> 
SQL> Select object_id
  2    from all_objects
  3   Where object_name = 'IX_TEST_IDX'
  4  /
 OBJECT_ID
----------
    168522
 
SQL> 
SQL> Select header_file, header_block, blocks
  2    from dba_segments
  3   where segment_name = 'IX_TEST_IDX'
  4  /
HEADER_FILE HEADER_BLOCK     BLOCKS
----------- ------------ ----------
          4       946186         32
 
SQL> 
SQL> ALTER SESSION SET EVENTS 'immediate trace name treedump level 168522'
  2  /

Dans le fichier de dump vous avez (regarder la présentation du Richard Foote pour les détails)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
----- begin tree dump
branch: 0x10e700b 17723403 (0: nrow: 20, level: 1)
   leaf: 0x10e700c 17723404 (-1: nrow: 520 rrow: 520)
   leaf: 0x10e700d 17723405 (0: nrow: 513 rrow: 513)
   leaf: 0x10e700e 17723406 (1: nrow: 513 rrow: 513)
   leaf: 0x10e700f 17723407 (2: nrow: 513 rrow: 513)
   leaf: 0x10e7010 17723408 (3: nrow: 513 rrow: 513)
   leaf: 0x10e7011 17723409 (4: nrow: 513 rrow: 513)
   leaf: 0x10e7012 17723410 (5: nrow: 513 rrow: 513)
   leaf: 0x10e7013 17723411 (6: nrow: 513 rrow: 513)
   leaf: 0x10e7014 17723412 (7: nrow: 513 rrow: 513)
   leaf: 0x10e7015 17723413 (8: nrow: 513 rrow: 513)
   leaf: 0x10e7016 17723414 (9: nrow: 513 rrow: 513)
   leaf: 0x10e7017 17723415 (10: nrow: 513 rrow: 513)
   leaf: 0x10e7019 17723417 (11: nrow: 513 rrow: 513)
   leaf: 0x10e701a 17723418 (12: nrow: 513 rrow: 513)
   leaf: 0x10e701b 17723419 (13: nrow: 513 rrow: 513)
   leaf: 0x10e701c 17723420 (14: nrow: 513 rrow: 513)
   leaf: 0x10e701d 17723421 (15: nrow: 513 rrow: 513)
   leaf: 0x10e701e 17723422 (16: nrow: 513 rrow: 513)
   leaf: 0x10e701f 17723423 (17: nrow: 513 rrow: 513)
   leaf: 0x10e7020 17723424 (18: nrow: 247 rrow: 247)
----- end tree dump

L’adresse du block branche est dans mon cas 17723403 ce qui donne l’adresse du block

Code:

1
2
3
4
5
6
7
 
SQL> SELECT DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(17723403),
  2  DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(17723403)
  3  FROM dual;
DBMS_UTILITY.DATA_BLOCK_ADDRES DBMS_UTILITY.DATA_BLOCK_ADDRES
------------------------------ ------------------------------
                             4                         946187

Et je vais faire un dump du ce block

Code:

1
2
 
alter system dump datafile 4 block 946187

Les entrés suivantes vous donnée l’idée comment les plages des valeurs sont stockés dans l'index

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
row#0[8052] dba: 17723405=0x10e700d
col 0; len 3; (3):  c2 06 16
row#1[8044] dba: 17723406=0x10e700e
col 0; len 3; (3):  c2 0b 23
row#2[8036] dba: 17723407=0x10e700f
col 0; len 3; (3):  c2 10 30
row#3[8028] dba: 17723408=0x10e7010
col 0; len 3; (3):  c2 15 3d
row#4[8020] dba: 17723409=0x10e7011
col 0; len 3; (3):  c2 1a 4a
row#5[8012] dba: 17723410=0x10e7012
col 0; len 3; (3):  c2 1f 57
row#6[8004] dba: 17723411=0x10e7013
col 0; len 3; (3):  c2 24 64
row#7[7996] dba: 17723412=0x10e7014
col 0; len 3; (3):  c2 2a 0d
row#8[7988] dba: 17723413=0x10e7015
col 0; len 3; (3):  c2 2f 1a
row#9[7980] dba: 17723414=0x10e7016
col 0; len 3; (3):  c2 34 27
row#10[7972] dba: 17723415=0x10e7017
col 0; len 3; (3):  c2 39 34
row#11[7964] dba: 17723417=0x10e7019
col 0; len 3; (3):  c2 3e 41
row#12[7956] dba: 17723418=0x10e701a
col 0; len 3; (3):  c2 43 4e
row#13[7948] dba: 17723419=0x10e701b
col 0; len 3; (3):  c2 48 5b
row#14[7940] dba: 17723420=0x10e701c
col 0; len 3; (3):  c2 4e 04
row#15[7932] dba: 17723421=0x10e701d
col 0; len 3; (3):  c2 53 11
row#16[7924] dba: 17723422=0x10e701e
col 0; len 3; (3):  c2 58 1e
row#17[7916] dba: 17723423=0x10e701f
col 0; len 3; (3):  c2 5d 2b
row#18[7908] dba: 17723424=0x10e7020
col 0; len 3; (3):  c2 62 38

Ligne 1, colonne 0 (a), valeur c2 06 16 c’est à dire 521
Ligne 2, colonne 0 (a), valeur c2 0b 23 c’est-à-dire 1034, delta 513
Ligne 3, colonne 0 (a), valeur c2 10 30 c’est-à-dire 1547, delta 513
…
Ligne 18, colonne 0 (a), valeur c2 62 38 c’est-à-dire 9755

La valeur 1 000 000 se trouve juste dans ce dernier block : 17723424

Code:

1
2
 
alter system dump datafile 4 block 946208

Et dans le fichier de dump

Code:

1
2
3
4
5
6
 
...
row#245[5087] flag: ------, lock: 0, len=11, data:(6):  01 0e 70 01 00 63
col 0; len 2; (2):  c3 02
row#246[5076] flag: ------, lock: 0, len=11, data:(6):  01 0e 70 01 00 64
col 0; len 2; (2):  c4 02

C302 est 10000 et C402 est 1000000

Code:

1
2
3
4
5
6
7
8
 
SQL> select utl_raw.cast_to_number('c302'),
  2         utl_raw.cast_to_number('c402')
  3    from dual
  4  /
UTL_RAW.CAST_TO_NUMBER('C302') UTL_RAW.CAST_TO_NUMBER('C402')
------------------------------ ------------------------------
                         10000                        1000000

28/12/2015, 19h22
Ikebukuro

Houlala, c'est de plus en plus complexe :calim2:
28/12/2015, 21h47
pachot

Bonjour,

1) oui, les tailles de bloc sont le mêmes. Evidemment, on peut mettre l'index dans un tablespace qui a une taille de bloc different, mais il n'y a pas de raison pour faire ça.
2) oui, dans une feuille chaque entrée d'index fait la taille du rowid (c'est 6 octets seulement sauf pour un index global sur table partitionnée là c'est 10 octects car il faut l'info de la partition) plus la taille de l'entrée (taille réelle - pas taille maximum)
3) une fois qu'on a les feuilles, les blocs 'au dessus' - donc les branches - sont là pour référencer les blocs feuille. Donc pour n blocs feuille, il y a n+1 entrées à mettre. Chaque entrée a une valeur (valeur max des colonnes indexée) + l'adresse du bloc feuille. Si toutes ces entrées logent dans un seul bloc, alors c'est le bloc racine. Sinon, c'est n blocs et il faut une branche de plus pour indexer ceux-là de la même manière. Etc. jusqu'à ce que tout loge dans une seul bloc, et c'est la racine
4) en réalité, vue que chaque entrée d'index contient le rowid, il n'y a pas de doublons. donc oui une valeur indexée peut se trouver dans plusieurs feuilles, mais une entrée d'index ne se trouve que dans une seule
5) oui il y a le rowid (car il fait partie de l'entrée d'index) mais il n'est pas utilisé pour accéder à la table. Il faut aller voir la feuille.
6) il y a des mécanismes de batching pour éviter d'aller voir trop souvent les mêmes blocs de table. Ce mécanisme n'est pas toujours choisi car il ne ramène pas les lignes dans l'ordre de l'index.

Cordialement,
Franck.

Citation:

Envoyé par Ikebukuro

Houlala, c'est de plus en plus complexe :calim2:

Oui il manque certainement des explications !

Le test crée une table avec une colonne (a) pour laquelle un index unique est créé. Dans la colonne (a) on a les valeurs de 1 à 10 000 et la valeur 1 000 000 ce qui corresponde à votre cas 3.2 où l’idée est d’investiguer comment les plages des valeurs sont stockées dans la branche.
L’index a un bloc racine et 20 blocs feuilles
Code:

1 2 3 4 5 6 7 8 9 10 11 SQL> SQL> Select blevel, leaf_blocks 2 from all_indexes 3 Where index_name = 'IX_TEST_IDX' 4 / BLEVEL LEAF_BLOCKS ---------- ----------- 1 20 SQL>
Ce qui est mis en évidence dans le premier dump de l’arbre.
Le bloc racine contient 20 entrés et il se trouve à l’adresse : 17723403 (0: nrow: 20, level: 1)
Le premier bloc feuille contient 520 valeurs et se trouve à l’adresse 17723404
Le deuxième bloc feuille contient 513 valeur et se trouve à l’adresse 17723405
Et ainsi de suite jusqu’au dernier bloc feuille qui contient 247 valeurs et se trouve à l’adresse 17723424

J’ai fait un vidage (dump) du bloc racine pour regarder son contenu. Dans ce dump on peut voir les plages des valeurs et le lien avec le bloc feuille où ces valeurs se trouvent.
row#0[8052] dba: 17723405=0x10e700d
col 0; len 3; (3): c2 06 16
nous informe que toutes les valeurs inférieurs à 521 (c20616) se trouve dans le bloc feuille de l’adresse 17723405.
row#1[8044] dba: 17723406=0x10e700e
col 0; len 3; (3): c2 0b 23
nous informe que toutes les valeurs entre 522 et 1034 (c20b23) se trouve dans le bloc feuille de l’adresse 17723406
et ainsi de suite jusqu’au la dernier entrée
row#18[7908] dba: 17723424=0x10e7020
col 0; len 3; (3): c2 62 38
qui nous informe que toutes les valeurs supérieures à 9755 se trouve dans le bloc feuille de l’adresse 17723424.

Le vidage (dump) de ce bloc montre bien la présence des valeurs 10 000 et 1 000 000 ainsi que le rowid (pointer) qui permet de trouver l’enregistrement de la table qui contient cette valeur.
Code:

1 2 3 4 row#245[5087] flag: ------, lock: 0, len=11, data:(6): 01 0e 70 01 00 63 col 0; len 2; (2): c3 02 row#246[5076] flag: ------, lock: 0, len=11, data:(6): 01 0e 70 01 00 64 col 0; len 2; (2): c4 02