Introduction aux structures d'indexation

La B-Tree, souvent désignée simplement comme arbre B, constitue une structure de données fondamentale pour les systèmes de stockage persistant. Bien que son nom ait été popularisé par Rudolf Bayer et Edward M. McCreight, la signification exacte du préfixe "B" reste intentionnellement vague dans l'histoire informatique moderne.

L'objectif principal de cet article est d'explorer la conception théorique des arbres B et de fournir une implémentation fonctionnelle en langage C#. Nous nous concentrerons ici spécifiquement sur le mécanisme d'insertion des données, étape critique pour maintenir l'équilibre de la structure.

Principes fondamentaux de l'indexation

Le concept de localité

Les systèmes matériels et logiciels subissent systématiquement des coûts liés au changement de contexte ou à l'accès mémoire. Pour optimiser les performances, les architectures sont conçues afin de regrouper les opérations similaires et d'accéder à des zones mémoires contiguës. Cette caractéristique, connue sous le nom de localité, permet de mutualiser les informations de contexte et d'améliorer radicalement l'efficacité du traitement.

Spécificités de la localité des données

On mesure la qualité de la localité par la continuité des données stockées. Plus les éléments nécessaires à une opération sont groupés physiquement, plus la localité est optimale.

Mémoire vive contre stockage magnétique

Lors de l'évaluasion des performances d'E/S, deux métriques sont primordiales :

1. IOPS : Le nombre d'opérations d'entrée/sortie réalisables par seconde.
2. Bande passante E/S : Le volume de données transféré par unité de temps.

Le stockage sur disque présente des latences significativement plus élevées que la RAM, particulièrement concernant les IOPS. Les lectures sur disque s'effectuent par blocs fixes appelés pages.

• Une bonne localité permet de charger une seule page contenant une série de données ordonnées, minimisant les accès physiques.
• Une mauviase localité entraîne une multiplication des chargements de pages, saturant rapidement les capacités IOPS et dégradant les performances globales.

Adéquation avec les structures d'index

Pour un stockage sur disque, l'optimisation de la localité est cruciale. Un tableau trié offre une excellente localité et une recherche logarithmique (O(log n)), mais l'insertion devient coûteuse (O(n)) en raison des décalages massifs.

À l'inverse, les arbres binaires équilibrés (comme les arbres Rouge-Noir) offrent des performances de lecture et d'écriture similaires en mémoire, mais souffrent d'une très faible localité spatiale sur disque. Chaque nœud étant potentiellement dispersé, cela génère un overhead important dû aux défauts de page multiples.

L'arbre B résout ce compromis en regroupant plusieurs clés dans un même nœud (augmentant la densité locale) tout en conservant la capacité d'insertion efficace grâce à des opérations de division contrôlées.

Définition de la B-Tree

Caractéristiques structurelles

Un arbre B se compose de trois types de nœuds :

• Nœud racine : Point d'entrée unique.
• Nœuds internes : Contiennent des paires clé-valeur et des références vers les enfants.
• Nœuds feuilles : Stockent les données finales sans références descendantes.

Il est important de noter que si l'arbre ne contient qu'un seul élément, la racine agit simultanément comme nœud feuille.

Chaque élément dans un nœud est défini selon un paramètre appelé degré ($t$), où $t \ge 2$. Les propriétés invariantes incluent :

1. Chaque nœud (sauf la racine) possède entre $t-1$ et $2t-1$ clés.
2. Chaque nœud peut avoir jusqu'à $2t$ enfants.
3. Tous les nœuds feuilles se situent au même niveau hiérarchique.

Ordre des données

L'intégrité de l'arbre repose sur l'ordre séquentiel des clés au sein de chaque nœud. Pour une configuration croissante :

• Les clés du sous-arbre gauche d'une donnée sont inférieures à celle-ci.
• Les clés du sous-arbre droit d'une donnée sont supérieures à celle-ci.

Conception des structures de données en C#

Avant d'aborder l'algorithme, il est nécessaire de définir les primitives logicielles. L'implémination proposée utilise des tableaux à taille fixe pré-allouée pour éviter les allocations dynamiques lors des insertions, optimisant ainsi les performances temporelles.

internal sealed class Element<TKey, TValue>
{
    public TKey Key { get; }
    public TValue Value { get; set; }

    public Element(TKey key, TValue value)
    {
        Key = key;
        Value = value;
    }
}

internal sealed class KeyPool<TKey, TValue>
{
    private readonly Element<TKey, TValue>[] _buffer;
    private readonly int _limit;
    private int _currentCount;
    private readonly IComparer<TKey> _comparator;

    public KeyPool(int maxElements, IComparer<TKey> comparer)
    {
        _limit = maxElements;
        _comparator = comparer;
        _buffer = new Element<TKey, TValue>[_limit];
    }

    public int Count => _currentCount;

    public bool TrySearch(TKey targetKey, out int foundIndex)
    {
        if (_currentCount == 0)
        {
            foundIndex = 0;
            return false;
        }

        int left = 0, right = _currentCount - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            var cmp = _comparator.Compare(targetKey, _buffer[mid].Key);

            if (cmp == 0)
            {
                foundIndex = mid;
                return true;
            }

            if (cmp < 0) right = mid - 1;
            else left = mid + 1;
        }

        foundIndex = left;
        return false;
    }

    public void ShiftIn(int position, Element<TKey, TValue> item)
    {
        if (_currentCount >= _limit) throw new InvalidOperationException("Capacity exceeded.");
        
        if (position < _currentCount)
            Array.Copy(_buffer, position, _buffer, position + 1, _currentCount - position);
            
        _buffer[position] = item;
        _currentCount++;
    }

    public void Append(Element<TKey, TValue> item) => ShiftIn(_currentCount, item);
    
    public Element<TKey, TValue> RemoveAt(int idx)
    {
        var removed = _buffer[idx];
        if (idx < _currentCount - 1)
            Array.Copy(_buffer, idx + 1, _buffer, idx, _currentCount - idx - 1);
        _buffer[--_currentCount] = null!;
        return removed;
    }
}

De manière siimlaire, nous définissons un gestionnaire pour les liens vers les nœuds enfants :

internal sealed class ChildLink<TKey, TValue>
{
    private readonly TreeNode<TKey, TValue>[] _refs;
    private readonly int _maxRefs;
    private int _refCount;

    public ChildLink(int capacity)
    {
        _maxRefs = capacity;
        _refs = new TreeNode<TKey, TValue>[capacity];
    }

    public int Count => _refCount;

    public void LinkChild(int index, TreeNode<TKey, TValue> child)
    {
        if (_refCount >= _maxRefs) throw new InvalidOperationException("Max children reached.");
        
        if (index < _refCount)
            Array.Copy(_refs, index, _refs, index + 1, _refCount - index);
            
        _refs[index] = child;
        _refCount++;
    }
    
    public TreeNode<TKey, TValue> GetChild(int index) => _refs[index];
    
    public void RemoveChild(int index)
    {
        if (index < _refCount - 1)
            Array.Copy(_refs, index + 1, _refs, index, _refCount - index - 1);
        _refs[--_refCount] = null!;
    }
}

Le nœud central encapsule ces collections :

internal sealed class TreeNode<TKey, TValue>
{
    private readonly int _degree;
    private readonly KeyPool<TKey, TValue> _store;
    private readonly ChildLink<TKey, TValue> _links;
    private readonly IComparer<TKey> _comp;

    public TreeNode(int degree, IComparer<TKey> comp)
    {
        _degree = degree;
        _comp = comp;
        // Max items = 2*t - 1
        int maxItems = 2 * degree - 1;
        int maxChildren = 2 * degree;
        
        _store = new KeyPool<TKey, TValue>(maxItems, comp);
        _links = new ChildLink<TKey, TValue>(maxChildren);
    }

    public bool IsFull => _store.Count == (2 * _degree - 1);
    public bool IsLeaf => _links.Count == 0;

    public void AddKey(KeyPool<TKey, TValue> keysToMerge, ChildLink<TKey, TValue> linksToMerge)
    {
        foreach (var kv in keysToMerge._buffer)
            _store.Append(kv);
            
        foreach (var child in linksToMerge._refs)
            _links.LinkChild(_links.Count, child);
    }

    public (Element<TKey, TValue>, TreeNode<TKey, TValue>) Divide()
    {
        int midIdx = _store.Count / 2;
        var pivot = _store.RemoveAt(midIdx);
        var sibling = new TreeNode<TKey, TValue>(_degree, _comp);

        // Transférer les éléments restants
        var itemsToRemove = _store._buffer.Skip(midIdx).ToArray();
        foreach(var itm in itemsToRemove)
             sibling._store.Append(itm);
             
        // Réinitialiser notre pool
        _store.Truncate(midIdx);

        if (!IsLeaf)
        {
            // Gérer les enfants associés
            var refsToRemove = _links._refs.Skip(midIdx + 1).ToArray();
            foreach(var r in refsToRemove)
                sibling._links.LinkChild(sibling._links.Count, r);
                
            _links._refs.AsSpan().Slice(midIdx + 1, _links.Count - (midIdx + 1)).Clear();
            _links._refCount = midIdx + 1;
        }

        return (pivot, sibling);
    }

    public InsertStatus AttemptAdd(TKey k, TValue v, InsertMode mode)
    {
        if (_store.TrySearch(k, out int idx))
        {
            return mode switch
            {
                InsertMode.Update => { _store[idx].Value = v; return InsertStatus.Updated; },
                InsertMode.Error => throw new ArgumentException("Duplicate key."),
                _ => InsertStatus.None
            };
        }

        if (IsLeaf)
        {
            _store.ShiftIn(idx, new Element<TKey, TValue>(k, v));
            return InsertStatus.Added;
        }

        if (_links.GetChild(idx).IsFull)
        {
            var (middleVal, rightNode) = _links.GetChild(idx).Divide();
            _store.ShiftIn(idx, middleVal);
            _links.LinkChild(idx + 1, rightNode);
            
            if (_comp.Compare(k, middleVal.Key) > 0) idx++;
            else if (_comp.Compare(k, middleVal.Key) == 0 && mode == InsertMode.Update)
                 return InsertStatus.Updated; 
        }

        return _links.GetChild(idx).AttemptAdd(k, v, mode);
    }
}

Mécanisme d'insertion et équilibrage

L'ajout d'une nouvelle clé nécessite de parcourir l'arbre depuis la racine jusqu'à trouver la feuille appropriée. Pour éviter une remontée coûteuse (backtracking) qui serait pénalisante sur disque, l'approche adoptée est une division préventive.

Gestion des nœuds pleins

Si un nœud atteint sa capacité maximale (2t-1 clés), il doit être scindé avant l'insertion de nouvelles données. Cela implique :

1. Création d'un nouveau nœud frère.
2. Migration de la moitié supérieure des données vers le frère.
3. Promotion de la clé médiane vers le nœud parent.

Cas de la racine

Lorsque la racine elle-même est pleine, sa division entraîne l'augmentation de la hauteur de l'arbre. Une nouvelle racine vide est créée, la vieille racine devient son premier enfant, et la deuxième moitié forme le second enfant.

Algorithme global

L'interface principale gère l'état racine et délègue la logique complexe aux instances de nœuds. La méthode principale vérifie d'abord si l'arbre est initialisé. Si la racine est saturée, elle procède immédiatement à la division pour créer une nouvelle arborescence avant de lancer l'insertion récursive.

La complexité temporelle globale de cette opération reste logarithmique O(log n), garantissant une performance stable même avec des volumes de données importants, car la profondeur de l'arbre augmente très lentement grâce à la grande quantité de clés stockées par nœud.