Matrice Judy

En informatique, une matrice Judy est une structure de données mettant en œuvre un type de tableau associatif offrant de hautes performances et une faible utilisation de la mémoire. Contrairement à la plupart des autres bases de données clé-valeur, les matrices Judy n'utilisent pas de hachage, exploitent la compression sur leurs clés (qui peuvent être des entiers ou des chaînes de caractères) et peuvent représenter efficacement des données éparses, c'est-à-dire qu'ils peuvent avoir de grandes plages d'indices non attribués sans augmenter considérablement l'utilisation de la mémoire ou le temps de traitement. Ils sont conçus pour rester efficaces même sur des structures dont la taille est de l'ordre du péta-élément, avec des performances de l'ordre de O(log n). Grossièrement, les matrices Judy sont des arbres radix 256-ary hautement optimisés. Les arbres Judy sont généralement plus rapides que les arbres AVL, les arbres B, les tables de hachage et les skip list car ils sont hautement optimisés pour maximiser l'utilisation du cache CPU. De plus, ils ne nécessitent aucun équilibrage d'arbre et aucun algorithme de hachage n'est utilisé. La matrice Judy a été inventée par Douglas Baskins et nommée d'après sa sœur. Les matrices Judy sont dynamiques et peuvent croître ou décroître à mesure que des éléments sont ajoutés ou retirés du tableau. La mémoire utilisée par les matrices Judy est presque proportionnelle au nombre d'éléments de la matrice. Les matrices Judy sont conçues pour minimiser le nombre de remplissages coûteux de lignes de cache à partir de la RAM, et l'algorithme contient donc une logique très complexe pour éviter les manques de cache aussi souvent que possible. Grâce à ces optimisations du cache, les matrices Judy sont rapides, en particulier pour les très grands ensembles de données. Sur les ensembles de données séquentielles ou presque séquentielles, les matrices Judy peuvent même surpasser les tables de hachage car, contrairement à ces dernières, la structure arborescente interne des matrices Judy maintient l'ordre des clés.