CHAPITRE 5 : RECHERCHER UNE CLÉ

La recherche est l'opération la plus simple des trois, et celle qui justifie toute la structure. Elle généralise la descente dans un arbre binaire : au lieu de choisir entre deux directions, on en choisit une parmi n + 1.

Le principe

À chaque nœud, on cherche dans quel intervalle tombe la clé recherchée, puis on descend dans le fils correspondant.

1. Parcourir les clés du nœud jusqu'à trouver la première qui soit supérieure ou égale à la clé cherchée.
2. Si cette clé est exactement celle qu'on cherche, c'est fini : on renvoie le nœud et la position.
3. Sinon, si le nœud est une feuille, la clé n'existe pas dans l'arbre.
4. Sinon, descendre dans le fils correspondant et recommencer.

L'algorithme

fonction RECHERCHE-BARBRE(x, k)
    // x a deja ete charge depuis le disque

    i <- 1
    tant que i <= x.n et k > x.cle[i] faire
        i <- i + 1
    fin tant que

    si i <= x.n et k = x.cle[i] alors
        retourner (x, i)                  // trouvee

    sinon si x.feuille alors
        retourner NIL                     // absente de l'arbre

    sinon
        LIRE-DISQUE(x.c[i])               // le seul cout reel
        retourner RECHERCHE-BARBRE(x.c[i], k)
    fin si
fin fonction

Remarquer la ligne LIRE-DISQUE : c'est la seule opération coûteuse de tout l'algorithme, et elle n'apparaît qu'une fois par niveau.

En Python

def rechercher(noeud, k):
    # Renvoie (noeud, position) si k est presente, sinon None
    i = 0
    while i < len(noeud.cles) and k > noeud.cles[i]:
        i += 1

    if i < len(noeud.cles) and k == noeud.cles[i]:
        return (noeud, i)

    if noeud.feuille:
        return None

    return rechercher(noeud.fils[i], k)      # LIRE-DISQUE implicite

Dérouler un exemple

Cherchons la clé S.

Deux nœuds visités, donc un seul accès disque : la racine étant déjà en mémoire. Sept comparaisons de clés, qui ne coûtent rien.

Cherchons maintenant Q, qui n'existe pas : on descend de la même façon jusqu'à la feuille R S T U V, où la boucle s'arrête sur R sans égalité. Le nœud étant une feuille, on renvoie NIL.

Les deux complexités

Il faut distinguer soigneusement deux coûts que l'on confond souvent.

C'est le coût en accès disque qui compte. Le coût processeur est t fois plus grand, mais chaque opération y est un million de fois moins chère.

Chiffrons sur un milliard de clés avec t = 128 :

acces disque   : 5 x 10 ms        = 50 ms
comparaisons   : 5 x 255 = 1275 operations
                 1275 x 10 ns     = 0,0127 ms

Le processeur represente 0,025 % du temps total.

Une optimisation naturelle

La boucle qui cherche l'intervalle est linéaire : elle examine les clés une par une. Or elles sont triées. On peut donc la remplacer par une recherche dichotomique :

import bisect

def rechercher(noeud, k):
    i = bisect.bisect_left(noeud.cles, k)    # O(log t) au lieu de O(t)

    if i < len(noeud.cles) and noeud.cles[i] == k:
        return (noeud, i)
    if noeud.feuille:
        return None
    return rechercher(noeud.fils[i], k)

Le temps processeur tombe de O(t · log_t n) à O(log t · log_t n), c'est-à-dire O(log₂ n).

La recherche d'intervalle

Au-delà de la recherche d'une clé précise, on demande souvent « toutes les clés entre a et b ». On descend jusqu'à a, puis on parcourt l'arbre dans l'ordre croissant jusqu'à dépasser b.

def parcours_trie(noeud, sortie):
    # Parcours infixe : sort les cles dans l'ordre croissant
    for i, cle in enumerate(noeud.cles):
        if not noeud.feuille:
            parcours_trie(noeud.fils[i], sortie)
        sortie.append(cle)
    if not noeud.feuille:
        parcours_trie(noeud.fils[-1], sortie)   # le dernier fils

Ce parcours visite chaque nœud une fois, donc O(n) en accès disque pour tout l'arbre. Sur un B-arbre ordinaire, un parcours d'intervalle oblige à remonter et redescendre sans cesse : c'est maladroit. Le chapitre 8 montrera comment les B+ arbres règlent ce problème en chaînant les feuilles entre elles.