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é.