Optimisation de la localité spatiale des données temporelles et multiversions

La gestion efficace des données temporelles et multiversions est cruciale pour nombre d'applications de base de données, des plus classiques aux plus récentes. La hiérarchie de mémoires est le goulot d'étranglement majeur pour les systèmes de gestion de base de données. Un des principaux moyens pour optimiser l'utilisation de la hiérarchie de mémoires et d'optimiser la localité spatiale des données, c'est-à-dire de placer de manière contiguë les données qui ont de grandes chances d'être lues au même moment. Le problème posé dans cette thèse est d'optimiser la localité spatiale des données temporelles et multiversions à tous les niveaux de la hiérarchie de mémoires, via les structures d'indexation et les stratégies de stockage. Cette thèse définit un modèle de coût, l'analyse en régime permanent, permettant d'estimer avec précision les performances des différentes structures d'indexation et de comprendre leur comportement. Ainsi, l'analyse fournit aux concepteurs de bases de données temporelles ou multiversions les outils leur permettant de choisir la structure d'indexation qui sied le mieux à leurs applications. Cette thèse étudie également l'impact de la redondance due au versionnement sur l'utilisation du cache de second niveau. La thèse propose à cet effet deux modèles de stockage qui, contrairement aux modèles de stockage standards, évitent la redondance due au versionnement et optimisent l'utilisation du cache de second niveau et de la bande passante de la mémoire viveThe efficient management of temporal and multiversion data is crucial for many traditional and emerging database applications. A major performance bottleneck for database systems is the memory hierarchy. One of the main means for optimizing the utilization of the memory hierarchy is to optimize data spatial locality, i.e. to put contiguously data that are likely to be read simultaneously. The problem studied in this thesis is to optimize temporal and multiversion data spatial locality at all levels of the memory hierarchy, using index structures and storage policies. In particular, this thesis proposes a cost model, the steady state analysis, allowing an accurate estimation of the performance of different index structures. The analysis provides database designers tools allowing them to determine the most suitable index structure, for given data and application characteristics. This thesis also studies the impact of version redundancy on L2 cache utilization. It proposes two storage models which, in contrast with the standard storage models, avoid version redundancy and optimize L2 cache and main memory bandwidth utilizationPARIS-DAUPHINE-BU (751162101) / SudocSudocFranceF