---
title: "Les B-arbres"
date: "2025-05-09"
---

# Les B-arbres (rappel)

## 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 (rappel)

## Est-ce un B-arbre?

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

. . .

### Bien sûr!

# Les B-arbres (rappel)

## 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 (rappel)

## L'insertion cas nœud pas plein, insertion `4`?

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

. . .

## Solution

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

# Les B-arbres (rappel)

## L'insertion cas nœud pas plein, insertion `N`

* On décale les éléments plus grand que `N`;
* On insère `N` dans la place "vide";
* Comme la page ne déborde pas, on a terminé.

# Les B-arbres (rappel)

## L'insertion cas nœud plein, insertion `2`?

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

. . .

## Solution

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

# Les B-arbres (rappel)

## L'insertion cas nœud plein, promotion `3`?

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

. . .

## Solution

![](figs/barbres_insert_hard_after.svg)

# Les B-arbres (rappel)

## L'insertion cas nœud plein, insertion `N`

* On décale les éléments plus grands que `N`;
* On insère `N` dans la place "vide";
* Si la page est pleine:
    * On trouve la valeur médiane `M` de la page (quel indice?);
    * On crée une nouvelle page de droite;
    * On copie les valeurs à 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 (rappel)

## Pseudo-code structure de données

. . .

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

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

# Les B-arbres (rappel)

\footnotesize

## Les fonctions utilitaires (5min matrix)

```C
booléen est_feuille(page)     // la page est-elle une feuille?
entier position(page, valeur) // à quelle indice insère-t-on?
booléen est_dans_page(page, valeur) // la valeur est-elle 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 && valeur >= 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 (rappel)

\footnotesize

## Les fonctions utilitaires 

```C
page nouvelle_page(ordre)  // créer une page
```
. . .

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

# Les B-arbres (rappel)

## Recherche de page

```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) - 1], 
            valeur)
```

# Les B-arbres (nouveautés)

## Les fonctions

```C
page inserer_valeur(page, valeur) // insérer une valeur
```

. . .

```C
page inserer_valeur(page, valeur)
    element = nouvel_element(valeur)
    // ici élément est modifié 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) // insérer 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.clé) - 1].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 element
```

. . .

```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)
    nouvelle_page = nouvelle_page(page.ordre)
    nouvelle_page.nb = page.ordre
    pour i de 0 à ordre inclu
        nouvelle_page.tab[i] = page.tab[i+ordre+1]
    element.clé = page.tab[ordre+1].clé
    element.page = nouvelle_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; -->
<!-- ``` -->


# Les B-arbres: suppression

## Cas simplissime

![Suppression de 25.](figs/barbres_ordre2_supp1.svg){width=80%}

. . .

![25 supprimé, on décale juste 27.](figs/barbres_ordre2_supp2.svg){width=80%}

# Les B-arbres: suppression

\footnotesize

## Cas simple


![Suppression de 27.](figs/barbres_ordre2_supp2.svg){width=50%}

. . .

* On retire 27, mais....
    * Chaque page doit avoir au moins 2 éléments.
    * On doit déplacer des éléments dans une autre feuille! Mais comment?

. . .

![La médiane de la racine descend, fusion de 20 à gauche, et suppression à droite.](figs/barbres_ordre2_supp3.svg){width=60%}

# Les B-arbres: suppression

## Cas moins simple

![Suppression de 5.](figs/barbres_ordre2_supp4.svg){width=50%}

. . .

* Un élément à droite, comment on fait?
    * Remonter `7`, serait ok si racine, mais... ce n'est pas forcément le cas.
    * On redistribue les feuilles.

. . .

![Descente de `3`, remontée médiane des feuilles `2`.](figs/barbres_ordre2_supp5.svg){width=50%}

# Les B-arbres: suppression

\footnotesize

## Cas ultra moins simple

![Suppression de 3.](figs/barbres_ordre2_supp6.svg){width=60%}

. . .

* `7` seul:
    * Fusionner les feuilles et redistribuer, comment?

. . .

![Descendre `-1`, déplacer `7` à gauche, et décaler les éléments de droite au milieu.](figs/barbres_ordre2_supp7.svg){width=60%}

# Les B-arbres: suppression

## Cas ultra moins simple

![On a pas fini...](figs/barbres_ordre2_supp7.svg){width=60%}

. . .

* `8` est seul, ce n'est plus un B-arbre :
    * Fusionner le niveau 2 et redistribuer, comment?

. . .

![Fusionner `8`, `17`, `22` et descendre `12`.](figs/barbres_ordre2_supp8.svg){width=40%}

. . .

* La profondeur a diminué de 1.

# Les B-arbres: suppression

## Algorithme pour les feuilles!

* Si la clé est supprimée d'une feuille:
    * Si on a toujours `n` (ordre de l'arbre) clés dans la feuille, on décale simplement les clés.
    * Sinon on combine (récursivement) avec le nœud voisin et on descend la clé médiane.

# Les B-arbres: suppression

## Cas non-feuille!

![Suppression de 8.](figs/barbres_ordre2_supp9.svg){width=60%}

. . .

* On sait comment effacer une valeur d'une feuille, donc?

. . .

![Échanger le `8` avec le plus grand du sous-arbre de gauche.](figs/barbres_ordre2_supp10.svg){width=60%}

* Ensuite?

# Les B-arbres: suppression

## Cas non-feuille!

![Suppression de 8.](figs/barbres_ordre2_supp10.svg){width=60%}

. . .

* On sait comment effacer une valeur d'une feuille!

. . .

![Yaka enlever le 8 de la feuille comme avant!](figs/barbres_ordre2_supp11.svg){width=60%}

# Les B-arbres: suppression

## Algorithme pour les non-feuilles!

* Si la clé est supprimée d'une page qui n'est pas une feuille:
    * On échange la valeur avec la valeur de droite de la page de gauche.
    * On supprime comme pour une feuille!

## Et maintenant des exercices par millions!

