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

![Arbre divisé en pages de 3 noeuds](figs/barbres_page3.png)

. . .

## 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?

![B-arbre d'ordre 2.](figs/barbres_exemple.png)

. . .

## 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`

![B-arbre d'ordre 2.](figs/barbres_exemple.png)
 
. . .

* 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`

![B-arbre d'ordre 1.](figs/barbres_1.svg)
 
. . .

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

# Les B-arbres

## Exemples d'insertion: `2`

![B-arbre d'ordre 1. Nombre pages max = 2.](figs/barbres_2.svg)
 
. . .

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

# Les B-arbres

## Exemples d'insertion: `3`

![B-arbre d'ordre 1.](figs/barbres_2.svg){width=50%}

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

# Les B-arbres

## Exemples d'insertion: `3`

![B-arbre d'ordre 1. Nombre pages max = 2.](figs/barbres_3.svg){width=50%}
 
. . .

* 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`

![B-arbre d'ordre 1.](figs/barbres_3.svg){width=50%}
 
* Comment on insère (1min de réflexion avant de donner une réponse!)?

# Les B-arbres

## Exemples d'insertion: `4`

![B-arbre d'ordre 1. Nombre enfants 0 ou 2.](figs/barbres_4.svg){width=50%}
 
. . .

* 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`

![B-arbre d'ordre 1.](figs/barbres_4.svg){width=50%}
 
* Comment on insère (1min de réflexion avant de donner une réponse!)?

# Les B-arbres

## Exemples d'insertion: `5`

![B-arbre d'ordre 2.](figs/barbres_5.svg)
 
. . .

* 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`

![B-arbre d'ordre 1.](figs/barbres_5.svg){width=50%}
 
* Comment on insère (1min de réflexion avant de donner une réponse!)?

# Les B-arbres

## Exemples d'insertion: `6`

![B-arbre d'ordre 2.](figs/barbres_6.svg)
 
. . .

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

# Les B-arbres

## Exemples d'insertion: `7`

![B-arbre d'ordre 1.](figs/barbres_6.svg){width=50%}
 
* Comment on insère (1min de réflexion avant de donner une réponse!)?

# Les B-arbres

## Exemples d'insertion: `7`

![B-arbre d'ordre 2.](figs/barbres_7.svg){width=50%}
 
. . .

* `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)

![](figs/barbres_ex1.png)

. . .

![](figs/barbres_ex2.png)


# Les B-arbres

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

![](figs/barbres_ex2.png)

. . .

![](figs/barbres_ex3.png)

# Les B-arbres

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

![](figs/barbres_ex3.png)

. . .

![](figs/barbres_ex4.png)

# Les B-arbres

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

![](figs/barbres_ex4.png)

. . .

![](figs/barbres_ex5.png)

# 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)?

. . .

![Strcture d'une page de B-arbre d'ordre 2.](figs/barbres_struct.png)


# Les B-arbres

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

. . .

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

```C
struct element
    int clé
    page pg
```

# Les B-arbres



# Les B-arbres

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

. . .

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

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