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$
    .

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;
• 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!

• 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.