---
title: "Barnes-Hut et B-arbres"
date: "2023-05-12"
---
# Le cours précédent
## A quoi sert l'algorithme de Barnes-Hut?
. . .
* A accélérer la résolution du problème à $n$-corps avec la gravitation,
* si on peut vivre avec une réduction de précision.
## Sur quelle structure de données se base l'algorithme?
* L'arbre quaternaire.
. . .
## Quelle est l'idée générale?
. . .
* Si un groupe d'étoiles est suffisamment loin, on le modélise comme un corps unique situé en son centre de masse.
* Exemple: Si on simule plusieurs galaxies, on considère chaque galaxie comme un corps unique!
* Un arbre quaternaire est une structure parfaite pour regrouper les étoiles.
# Le cas à 10 corps
::: columns
:::: {.column width=50%}
## Illustration: le cas à 10 corps
{width=60%}
::::
:::: {.column width=50%}
## Problématique
* On veut calculer la force sur $1$.
::::
:::
. . .
::: columns
:::: {.column width=50%}
## Illustration: le cas à 10 corps
{width=60%}
::::
:::: {.column width=50%}
## Résultat
* Calcul et somme des forces venant des $9$ autre corps.
::::
:::
# Le cas à 10 corps
::: columns
:::: {.column width=50%}
## Réduction d'un groupe à un seul corps
{width=100%}
::::
:::: {.column width=50%}
## Idée
* On accélère le calcul en traitant un groupe comme un seul corps.
* Fonctionne uniquement si le groupe est assez loin.
* Autrement l'approximation est trop grossière.
::::
:::
# Solution: l'arbre quaternaire
## Corps célestes - arbre
* On omet les nœuds vides pour éviter la surcharge.
* La numérotation est:
* 0: ID
* 1: SD
* 2: IG
* 3: SG
# Exemple d'insertion
::: columns
:::: {.column width=50%}
## Insertion corps 1
{width=100%}
::::
:::: {.column width=50%}
## Arbre, niveau 1
{width=100%}
* Quadrant ID.
* La feuille est vide, on insère.
::::
:::
# Exemple d'insertion
::: columns
:::: {.column width=50%}
## Insertion corps 2
{width=100%}
::::
:::: {.column width=50%}
## Arbre, niveau 1
{width=100%}
* Quadrant SD.
* La feuille est vide, on insère.
::::
:::
# Exemple d'insertion
::: columns
:::: {.column width=50%}
## Insertion corps 3 (1/N)
{width=100%}
::::
:::: {.column width=50%}
## Arbre, niveau 1
{width=100%}
* Quadrant SD.
* La feuille est prise par 2.
::::
:::
# Exemple d'insertion
::: columns
:::: {.column width=50%}
## Insertion corps 3 (2/N)
{width=100%}
::::
:::: {.column width=50%}
## Arbre, niveau 2
{width=100%}
* On crée un nouveau nœud.
* Deux corps dans le nœud ID.
* On crée un nouveau nœud.
::::
:::
# Exemple d'insertion
::: columns
:::: {.column width=50%}
## Insertion corps 3 (3/N)
{width=100%}
::::
:::: {.column width=50%}
## Arbre, niveau 3
{width=100%}
* 2 va dans ID.
* 3 va dans SG.
* C'est des feuilles vides, tout va bien.
::::
:::
# Exemple d'insertion
::: columns
:::: {.column width=50%}
## Que fait-on avec les nœuds intérieurs?
* On les utilise pour:
* stocker la masse totale;
* stocker le centre de masse.
\begin{align}
m&=m_2+m_3,\\
\vec x &= \frac{m_2\vec x_2+m_3\vec x_3}{m}.
\end{align}
## Chaque feuille contient **une étoile**
::::
:::: {.column width=50%}
## Arbre
{width=100%}
::::
:::
# Résumé
* Insertion du corps `c` dans le nœud `n` en partant de la racine.
* Si le nœud `n`
* ne contient pas de corps, on y dépose `c`,
* est interne, on met à jour masse et centre de masse. `c` est inséré récursivement dans le bon quadrant.
* est externe, on subdivise `n`, on met à jour la masse et centre de masse, on insère récursivement les deux nœuds dans les quadrants appropriés.
## Remarque
* Il faut stocker les coordonnées des quadrants.
* Un nœud a un comportement différent s'il est interne ou externe.
# Algorithme d'insertion
## Structure de données
```C
struct node
etoile e // externe: pour stocker
etoile sup_etoile // interne: pour stocker m, x
quadrant q // coordonnées du quadrant
node enfants[4]
```
## Remarque:
* On fait une simplification "moche": `sup_etoile` pourrait juste avoir une masse et une position.
# Algorithme d'insertion
\footnotesize
## Algorithme d'insertion, pseudo-code (15min, matrix)
. . .
```C
rien insertion_etoile(arbre, e)
si (!est_vide(arbre) && dans_le_quadrant(arbre.q, e.x)) {
si (est_feuille(arbre))
si (!contient_etoile(arbre))
arbre.e = e
sinon
// on crée enfants et arbre.sup_etoile est initialisée
subdivision_arbre(arbre, e)
pour enfant dans arbre.enfants
insertion_etoile(enfant, arbre.e)
pour enfant dans arbre.enfants
insertion_etoile(enfant, e)
destruction(arbre.e)
sinon
maj_masse_cdm(arbre.sup_etoile, e)
pour enfant dans arbre.enfants
insertion_etoile(enfant, e)
```
# Utilisation de l'arbre
* L'arbre est rempli: comment on calcule la force sur le corps 1?
* Parcours de l'arbre:
* si la distance entre 1 et le centre de masse est suffisante, on utilise la masse totale et centre de masse pour calculer la force.
* sinon, on continue le parcours
# Calcul de la force
## Calcul de la force sur `1`
* Le cadrant ID ne contient que `1`, rien à faire.
# Calcul de la force
## Calcul de la force sur `1`
* Le cadrant SG ne contient `5` corps.
# Calcul de la force
## Calcul de la force sur `1`
* La distance entre `1` et le centre de masse de SG est `d`.
# Calcul de la force
## Calcul de la force sur `1`
* La distance entre `1` et le centre de masse de SG est `d`.
* Est-ce que `d` est assez grand?
* On va comparer avec la distance `d` avec la taille du quadrant `s`.
# Critère $\theta$
* On compare $d=||\vec x_1-\vec x_{cm}||$ avec $s$ la taille du quadrant.
* Le domain est assez éloigné si
$$
\frac{s}{d}<\theta,
$$
* $\theta$ est la valeur de seuil.
* Une valeur typique est $\theta=0.5$, donc la condition devient
$$
d>2s.
$$
# Calcul de la force
## Calcul de la force sur `1`
* Ici $d<2s$, domaine rejeté.
* ON descend dans l'arbre.
# Calcul de la force
## Calcul de la force sur `1`
* `s` est plus petit, mais....
* Cela ne suffit pas $d<2s$, domaine rejeté.
# Calcul de la force
## Calcul de la force sur `1`
* Les nœuds sont des feuilles, on calcule la force.
* On ajoute la force qu'ils exercent sur `1`.
# Algorithme pour le calcul de la force
Pour calculer la force sur un corps `c`, on parcourt l'arbre en commençant par la racine:
* Si le nœud `n` est une feuille et n'est pas `c`, on ajoute la force dûe à `n` sur `c`;
* Sinon si $s/d<\theta$, on traite `n` comme une feuille et on ajoute la force dûe à `n` sur `c`;
* Sinon on continue sur les enfants récursivement.
## Continuons notre exemple précédent!
# Calcul de la force
## Calcul de la force sur `1`
* Il y a deux corps dans le quadrant vert.
* Quel est le critère pour remplacer les étoiles par leur centre de masse?
. . .
* Et oui! $d>2s$ on peut remplacer les étoiles par leur centre de masse!
# Algorithme du calcul de force
## Écrire le pseudo-code-code du calcul de la force
\footnotesize
```C
rien maj_force_sur_etoile(arbre, e, theta)
si est_vide(arbre)
retourne
si est_feuille(arbre) && contient_etoile(arbre) && dans_le_quadrant(arbre.q, e.x)
maj_force(e, arbre.e)
sinon si noeud_assez_loin(arbre, e, theta)
maj_force(e, arbre.sup_etoile)
sinon
pour enfant dans enfants
maj_force_sur_etoile(enfant, e, theta)
```
# 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 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 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
. . .
## 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?
. . .
## 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`
. . .
* 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`
. . .
* L'arbre est vide, on insère juste dans la première page.
# Les B-arbres
## Exemples d'insertion: `2`
. . .
* La première page est pas pleine, on insère dans l'ordre (après 1).
# Les B-arbres
## Exemples d'insertion: `3`
{width=50%}
* Comment on insère (1min de réflexion avant de donner une réponse!)?
# Les B-arbres
## Exemples d'insertion: `3`
{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`
{width=50%}
* Comment on insère (1min de réflexion avant de donner une réponse!)?
# Les B-arbres
## Exemples d'insertion: `4`
{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`
{width=50%}
* Comment on insère (1min de réflexion avant de donner une réponse!)?
# Les B-arbres
## Exemples d'insertion: `5`
. . .
* 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 nœud à droite de `4`;
* La règle `m => m+1` est ok.
# Les B-arbres
## Exemples d'insertion: `6`
{width=50%}
* Comment on insère (1min de réflexion avant de donner une réponse!)?
# Les B-arbres
## Exemples d'insertion: `6`
. . .
* `6 > 4` on descend à droite;
* `6 > 5` et on a à la place à droite, on insère.
# Les B-arbres
## Exemples d'insertion: `7`
{width=50%}
* Comment on insère (1min de réflexion avant de donner une réponse!)?
# Les B-arbres
## Exemples d'insertion: `7`
{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)
. . .
# Les B-arbres
## Exercice: insérer `5` dans l'arbre d'ordre 2 (3min matrix)
. . .
# Les B-arbres
## Exercice: insérer `32, 55, 60` dans l'arbre d'ordre 2 (3min matrix)
. . .
# Les B-arbres
## Exercice: insérer `41` dans l'arbre d'ordre 2 (3min matrix)
. . .
# 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.