---
title: "Les B-arbres"
date: "2025-04-11"
---

# Les B-arbres

\Huge

Les B-arbres


# Les B-arbres

## Problématique

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

## Exemple

* 100 nœuds par page et l'arbre comporte $10^6$ nœuds:
    * 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 ne 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 nœuds

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

. . .

## Utilisation

* Bases de données (souvent très grandes donc sur le disque);
* Systèmes de fichiers.

# Les B-arbres

## Avantages

* Arbres moins profonds;
* Diminution des opérations 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 nœud les clés sont **triées**.
* Chaque page contient au plus $n$ nœuds: check;
* Chaque nœud 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 `C` plus petit que la 1ère clé ou plus grand que la dernière descendre.
* Sinon parcourir (par bissection ou séquentiellement) jusqu'à trouver où descendre entre 2 éléments.

# Les B-arbres

## Algorithme de recherche de la clé `C` 

0. En partant de la racine.
1. Si on est dans une feuille:
    * Si `C` est dans la page, retourner la page;
    * Sinon c'est perdu.
2. Sinon:
    * Tant que `C < clé(page)` passer à la clé suivante
    * Si `C` est dans la page, retourner la page;
    * Sinon 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 n'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 1.](figs/barbres_5.svg)
 
. . .

* On descend à droite (on ne 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 nœud à 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 1.](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 1.](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 n'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

\footnotesize

## Structure de données

* Chaque page a une contrainte de remplissage, par rapport à l'ordre de l'arbre;
* Un nœud (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)?

. . .

![Structure 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 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

## 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";
* Si la page n'est pas pleine, on a terminé.

# Les B-arbres

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

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

## L'insertion cas nœud 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 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

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

. . .

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

```C
struct element
    entier 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 && 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

\footnotesize

## Les fonctions utilitaires (5min matrix)

```C
page nouvelle_page(ordre)  // créer une page
rien liberer_memoire(page) // libérer 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) - 1], valeur)
```

