cours_22.md

title: "B-Arbres"
date: "2022-04-13"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto

Le cours précédent

• Questions:

Les B-arbres

Problématique

• Grands jeux de données (en 1970).
• Stockage dans un arbre, mais l'arbre tiens pas en mémoire.
• Regrouper les sous-arbres en pages qui tiennent en mémoire.

Exemple

• 100 noeuds par page et l'arbre comporte
  10^6
  noeuds:
  • Recherche B-arbre:
    \log_{100}(10^6)=3
    ;
  • Recherche ABR:
    \log_2(10^6)=20
    .
• Si on doit lire depuis le disque:
  10\mathrm{ms}
  par recherche+lecture:
  • 30\mathrm{ms}
    (lecture beaucoup plus rapide que recherche) vs
    200\mathrm{ms}=0.2\mathrm{s}
    .

Remarques

• On sait pas ce que veut dire B: Bayer, Boeing, Balanced?
• Variante plus récente B+-arbres.

Les B-arbres

Illustration, arbre divisé en pages de 3 noeuds

. . .

Utilisation

• Bases de données (souvent très grandes donc sur le disque);
• Système de fichier.

Les B-arbres

Avantages

• Arbres moins profonds;
• Diminue les opération de rééquilibrage;
• Complexité toujours en
  \log(N)
  ;

. . .

Définition: B-arbre d'ordre

n

• Chaque page d'un arbre contient au plus
  2\cdot n
  clés;
• Chaque page (excepté la racine) contient au moins
  n
  clés;
• Chaque page qui contient
  m
  clés contient soit:
  • 0
    descendants;
  • m+1
    descendants.
• Toutes les pages terminales apparaissent au même niveau.

Les B-arbres

Est-ce un B-arbre?

. . .

Oui!

• Dans chaque noeud les clés sont triées.
• Chaque page contient au plus
  n
  noeuds: check;
• Chaque noeud avec
  m
  clés a
  m+1
  descendants;
• Toutes les feuilles apparaissent au même niveau.

Les B-arbres

Exemple de recherche: trouver 32

. . .

• Si n plus petit que la 1e clé ou plus grand que la dernière descendre.
• Sinon parcourir (par bissection ou séquentiellement) jusqu'à trouver ou descendre entre 2 éléments.

Les B-arbres

La recherche de la clé C algorithme

0. En partant de la racine.
1. Si on est dans une feuille:
   • Si la C est dans une page, retourner la page;
   • Sinon c'est perdu.
2. Sinon:
   • Tant que C > page passer à la page suivante
   • Descendre

Les B-arbres

Disclaimer

• Inspiration de https://en.wikipedia.org/wiki/B-tree

Exemples d'insertion: 1

. . .

• L'arbre est vide, on insère juste dans la première page.

Les B-arbres

Exemples d'insertion: 2

. . .

• La première page est pas pleine, on insère dans l'ordre (après 1).

Les B-arbres

Exemples d'insertion: 3

• Comment on insère (1min de réflexion avant de donner une réponse!)?

Les B-arbres

Exemples d'insertion: 3

. . .

• La page est pleine, on crée deux enfants.
• On choisit, 2, la médiane de 1, 2, 3 et il est inséré à la racine.
• 1 descend à gauche, 3 descend à droite.

Les B-arbres

Exemples d'insertion: 4

• Comment on insère (1min de réflexion avant de donner une réponse!)?

Les B-arbres

Exemples d'insertion: 4

. . .

• On pourrait insérer à droite de 2, mais... ça ferait 2 parents pour 2 enfants (mais m parents => m+1 enfants ou 0);
• On descend à droite (4 > 2);
• On insère à droite de 3.

Les B-arbres

Exemples d'insertion: 5

• Comment on insère (1min de réflexion avant de donner une réponse!)?

Les B-arbres

Exemples d'insertion: 5

. . .

• On descend à droite (on peut pas insérer à la racine comme pour 4);
• On dépasse la capacité de l'enfant droite;
• 4, médiane de 3, 4, 5, remonte à la racine;
• On crée un nouveau noeud à droite de 4;
• La règle m => m+1 est ok.

Les B-arbres

Exemples d'insertion: 6

• Comment on insère (1min de réflexion avant de donner une réponse!)?

Les B-arbres

Exemples d'insertion: 6

. . .

• 6 > 4 on descend à droite;
• 6 > 5 et on a à la place à droite, on insère.

Les B-arbres

Exemples d'insertion: 7

• Comment on insère (1min de réflexion avant de donner une réponse!)?

Les B-arbres

Exemples d'insertion: 7

. . .

• 7 > 4 on descend à droite;
• 7 > 6 mais on a dépassé la capacité;
• 6 est la médiane de 5, 6, 7, remonte à la racine;
• 5 reste à gauche, 7 à droite, mais 6 fait dépasser la capacité de la racine;
• 4 est la médiane de 2, 4, 6, 4 remonte, 2 reste à gauche, 6 à droite.

Les B-arbres

L'algorithme d'insertion

0. Rechercher la feuille (la page a aucun enfant) où insérer;
1. Si la page n'est pas pleine insérer dans l'ordre croissant.
2. Si la page est pleine, on sépare la page en son milieu :
   1. On trouve la médiane, M, de la page;
   2. On met les éléments < M dans la page de gauche de M et les > M dans la page de droite de M;
   3. M est insérée récursivement dans la page parent.

Les B-arbres

Exercice: insérer 22 dans l'arbre d'ordre 2 (3min matrix)

. . .

Les B-arbres

Exercice: insérer 5, 45, 50 dans l'arbre d'ordre 2 (3min matrix)

. . .

Les B-arbres

Exercice: insérer 32, 55, 60 dans l'arbre d'ordre 2 (3min matrix)

. . .

Les B-arbres

Exercice: insérer 41 dans l'arbre d'ordre 2 (3min matrix)

. . .

Les B-arbres

Exercice

• Insérer 20, 40, 10, 30, 15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25, 2, 14, 28, 32, 41,
• Dans un B-arbre d'ordre 2.

Les B-arbres

Structure de données

• Chaque page a une contrainte de remplissage, par rapport à l'ordre de l'arbre;
• Un noeud (page) est composé d'un tableau de clés/pointeurs vers les enfants;

P_0 | K_1 | P_1 | K_2 |  | P_i | K_{i+1} |  | P_{m-1} | K_m | P_m

• P_0, ..., P_m pointeurs vers enfants;
• K_1, ..., K_m les clés.
• Il y a m+1 pointeurs mais m clés.
• Comment faire pour gérer l'insertion?

Les B-arbres

Faire un dessin de la structure de données (3min matrix)?

. . .

Les B-arbres

Pseudo-code structure de données (3min, matrix)?

. . .

struct page
    int ordre, nb
    element tab[2*ordre + 2]

struct element
    int clé
    page pg

Les B-arbres

Les B-arbres

Structure de données en C (3min, matrix)

. . .

typedef struct _page {
    int order, nb;
    struct _element *tab;
} page;

typedef struct element {
    int key;
    struct _page *pg;
} element;