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

# 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, 45, 50` dans l'arbre d'ordre 2 (3min matrix)

![](figs/barbres_ex1.png)

. . .

![](figs/barbres_ex2.png)


# Les B-arbres

## Exercice: insérer `5` 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

## Exercice (matrix, 15min)

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

. . .

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

1. On veut un tableau de `P_i, K_i => struct`;
2. `K_0` va être en "trop";
3. Pour simplifier l'insertion dans une page, on ajoute un élément de plus.

# Les B-arbres

## L'insertion cas noeud pas plein, insertion `4`?

![](figs/barbres_insert_easy.svg){width=50%}

. . .

## Solution

![](figs/barbres_insert_easy_after.svg){width=50%}

# Les B-arbres

## L'insertion cas noeud pas plein, insertion `N`

* On décale les éléments plus grand que `N`;
* On insère `N` dans la place "vide";
* Si la page n'est pas pleine, on a terminé.

# Les B-arbres

## L'insertion cas noeud plein, insertion `2`?

![](figs/barbres_insert_hard_before.svg){width=50%}

. . .

## Solution

![](figs/barbres_insert_hard_during.svg){width=50%}

# Les B-arbres

## L'insertion cas noeud plein, promotion `3`?

![](figs/barbres_insert_hard_during.svg){width=50%}

. . .

## Solution

![](figs/barbres_insert_hard_after.svg)

# Les B-arbres

## L'insertion cas noeud plein, insertion `N`

* On décale les éléments plus grand que `N`;
* On insère `N` dans la place "vide";
* Si la page est pleine:
    * On trouve la valent médiance `M` de la page (quel indice?);
    * On crée une nouvelle page de droite;
    * On copie les valeur à droite de `M` dans la nouvelle page;
    * On promeut `M` dans la page du dessus;
    * On connecte le pointeur de gauche de `M` et de droite de `M` avec l'ancienne et la nouvelle page respectivement.

# Les B-arbres

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

. . .

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

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

# Les B-arbres

\footnotesize

## Les fonctions utilitaires (5min matrix)

```C
booléen est_feuille(page)     // la page est elle une feuille?
entier position(page, valeur) // à quelle indice on insère?
booléen est_dans_page(page, valeur) // la valeur est dans la page
```

. . .

```C
booléen est_feuille(page) 
    retourne (page.tab[0].pg == vide)

entier position(page, valeur)
    i = 0
    tant que i < page.nb && val >= page.tab[i+1].clef
        i += 1
    retourne i

booléen est_dans_page(page, valeur)
    i = position(page, valeur)
    retourne (page.nb > 0 && page.tab[i].val == valeur)
```

# Les B-arbres

\footnotesize

## Les fonctions utilitaires (5min matrix)

```C
page nouvelle_page(ordre)  // creer une page
rien liberer_memoire(page) // liberer tout un arbre!
```
. . .

```C
page nouvelle_page(ordre)
    page = allouer(page)
    page.ordre = ordre
    page.nb = 0
    page.tab = allouer(2*ordre+2)
    retourner page

rien liberer_memoire(page)
    si est_feuille(page)
        liberer(page.tab)
        liberer(page)
    sinon
        pour fille dans page.tab
            liberer_memoire(fille)
        liberer(page.tab)
        liberer(page)
```

# Les B-arbres

## Les fonctions (5min matrix)

```C
page recherche(page, valeur) // retourner la page contenant
                             // la valeur ou vide 
```

. . .

```C
page recherche(page, valeur)
    si est_dans_page(page, valeur)
        retourne page
    sinon si est_feuille(page) 
        retourne vide
    sinon
        recherche(page.tab[position(page, valeur)], valeur)
```

# Les B-arbres

## Les fonctions

```C
page inserer_valeur(page, valeur) // inserer une valeur
```

. . .

```C
page inserer_valeur(page, valeur)
    element = nouvel_element(valeur)
    // on change element pour savoir s'il faut le remonter
    inserer_element(page, element) 
    si element.page != vide && page.nb > 2*page.ordre
        // si on atteint le sommet!
        page = ajouter_niveau(page, element) 
    retourne page
```

# Les B-arbres

## Les fonctions

```C
rien inserer_element(page, element) // inserer un element et voir s'il remonte
```

. . .

```C
rien inserer_element(page, element)
    si est_feuille(page)
        placer(page, element)
    sinon
        sous_page = page.tab[position(page, element)].page
        inserer_element(sous_page, element)
        // un element a été promu
        si element.page != vide
            placer(page, element)
```

# Les B-arbres

## Les fonctions (5min matrix)

```C
rien placer(page, element) // inserer un élément
```

. . .

```C
rien placer(page, element)
    pos = position(page, element.clé)
    pour i de 2*page.ordre à pos+1
        page.tab[i+1] = page.tab[i]
    page.tab[pos+1] = element
    page.nb += 1
    si page.nb > 2*page.ordre
        scinder(page, element)
```

# Les B-arbres

## Les fonctions (5min matrix)

```C
rien scinder(page, element) // casser une page et remonter
```

. . .

```C
rien scinder(page, element)
    new_page = new_page(page.ordre)
    new_page.nb = page.ordre
    pour i de 0 à ordre inclu
        new_page.tab[i] = page.tab[i+ordre+1]
    element.clé = page.tab[ordre+1].clé
    element.page = new_page
```

# Les B-arbres

## Les fonctions (5min matrix)

```C
page ajouter_niveau(page, element) // si on remonte à la racine...
                                   // on doit créer une nouvelle racine
```

. . .

```C
page ajouter_niveau(page, element) 
    tmp = nouvelle_page(page.ordre)
    tmp.tab[0].page = page
    tmp.tab[1].clé = element.clé
    tmp.tab[1].page = element.page
    retourne tmp
```


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