Base de données interne

Chapitre 2. Notions de base sur les arbres B

Cet ouvrage a été traduit à l'aide de l'IA. Tes réactions et tes commentaires sont les bienvenus : [e-mail]

Dans le chapitre précédent, nous avons séparé les structures de stockage en deux groupes : les structures mutables et les structures immuables, et nous avons identifié l'immuabilité comme l'un des concepts fondamentaux qui influencent leur conception et leur mise en œuvre. La plupart des structures de stockage mutables utilisent un mécanisme de mise à jour sur place. Pendant les opérations d'insertion, de suppression ou de mise à jour, les enregistrements de données sont mis à jour directement à leur emplacement dans le fichier cible.

Les moteurs de stockage permettent souvent la présence de plusieurs versions d'un même enregistrement de données dans la base de données ; par exemple, lors de l'utilisation du contrôle de simultanéité multiversion (voir "Contrôle de simultanéité multiversion") ou de l'organisation des pages à créneaux (voir "Pages à créneaux"). Par souci de simplicité, nous supposons pour l'instant que chaque clé n'est associée qu'à un seul enregistrement de données, qui a un emplacement unique.

L'une des structures de stockage les plus populaires est le B-Tree. De nombreux systèmes de bases de données open source sont basés sur des B-Tree et, au fil des ans, ils ont prouvé qu'ils couvraient la majorité des cas d'utilisation.

Les arbres B ne sont pas une invention récente : ils ont été introduits ...