Brevet FR3047580A1 — publié le 20170811

INDEX DE TABLE DE BASE DE DONNEES DOMAINE DE L'INVENTION De façon générale, la présente invention concerne la technologie de base de données. Plus spécifiquement, la présente invention est dirigée vers un index pour accéder à une table de base de données en réponse à une demande et pour déterminer l'enregistrement de données (rangée) le plus spécifique de la table de base de données conforme à la demande. CONTEXTE On connaît les tables de base de données d'index pour accéder aux enregistrements de données de manière directe ou accélérée. Un index est une structure de métadonnées qui améliore la vitesse des opérations d'extraction de données sur une table de données, aux dépens de l'espace de stockage pour maintenir la structure des données d'index. Les index sont utilisés pour localiser rapidement les données sans devoir chercher chaque rangée dans la table de base de données, à chaque fois que l'on accède à la table de base de données. Les index peuvent être créés en utilisant une ou plusieurs colonnes de la table de base de données et fournir à la fois la base pour les consultations aléatoires rapides et l'accès efficace aux enregistrements ordonnés. 20 Une tâche particulière dans diverses applications liées à la base de données consiste à récupérer uniquement la rangée de la table de base de données la plus spécifique répondant à une demande d'extraction. Par conséquent, en réponse à une demande, l'application de base de données détermine donc la rangée de la table de base de données qui correspond aux paramètres ou aux 25 critères d'entrée de la manière la plus spécifique. À cette fin, une hiérarchie de spécificité au sein de la rangée est généralement présente dans la table de base de données. Une approche connue pour déterminer la rangée la plus spécifique dans la table de base de données utilise l'algorithme Raite. L'algorithme Raite est un algorithme de mise en 30 correspondance de motif qui est utilisé par ex. pour implémenter des systèmes de règles de production (par ex. la planification automatisée, les systèmes experts et les systèmes de sélection d'action). Il est utilisé pour déterminer toutes les règles qui correspondent aux critères d'entrée. Une prétendue « résolution de conflit » est ensuite réalisée. Elle utilise un ordre parmi les règles déterminées pour identifier la règle qui doit être retournée. 3047580 2 RESUME DE L'INVENTION L'objet de la présente invention est de fournir un indice de table de base de données qui facilite 5 particulièrement la détermination de la rangée de tables de base de données la plus spécifique remplissant les paramètres d'entrée d'une demande d'extraction. L'objet de la présente invention est également de fournir un index de table de base de données qui a une représentation de données particulièrement compactes et minimise ainsi les besoins en mémoire. L'objet de la présente invention est également de fournir un index de table de base de données qui s'occupe 10 spécifiquement de l'architecture interne et de la mémoire de dimensionnement des systèmes informatiques ultramodernes et qui est optimisé pour être conservé dans un cache de processeur et facilite ainsi la détermination de haute performance de la rangée de table de base de données la plus spécifique. L'objet de la présente invention est également de fournir un index de table de base de données permettant le traitement de réponse déterministe. 15 Selon un aspect, ces objets sont résolus par une méthode de détermination de la rangée la plus spécifique dans la table de base de données. La table de base de données est maintenue par un système informatique. La table de base de données est constituée d'une pluralité de rangées et d'une pluralité de colonnes. Les rangées et les colonnes de la table de base de données forment des cellules. Chacune des cellules comprend soit une valeur au moins soit aucune valeur. Le système informatique maintient également un index pour la table de base de données. L'index comprend une structure d'index respective pour chaque colonne de la table de base de données. Chaque structure d'index comprend deux types de sous-structures, à savoir un 25 ensemble respectif de tuples de pointeur pour chaque valeur apparaissant dans la colonne respective et un bitmap lié à la cellule de la colonne sans valeur. Chaque tuple de pointeur comprend un premier pointeur indiquant une des valeurs qui apparaît dans la colonne et un second pointeur indiquant la rangée de la table de base de données dans laquelle apparaît la valeur. Le bitmap indique toutes les cellules dans la colonne respective sans valeur. L'index 30 indique également un ordre de spécificité des rangées de la table de base de données. La méthode de détermination de la rangée la plus spécifique comprend les activités suivantes : 3047580 3 Le système informatique reçoit une demande indiquant les colonnes de la table de base de données associées à une valeur d'entrée respective. Le système informatique traite ensuite la demande de manière incrémentielle pour chaque colonne indiquée dans la demande. Pour chaque colonne, le système informatique utilise le bitmap de la structure d'index pour que la 5 colonne maintienne toutes les rangées de la table de base de données qui ne contiennent pas de valeurs dans la cellule de la colonne considérée. De plus, pour chaque colonne, le système informatique utilise le tuple de pointeur de la structure d'index pour que la colonne filtre toutes les rangées de la table de base de données qui ne comprennent pas la valeur d'entrée respective. Une fois que toutes les colonnes avec les valeurs d'entrée respectives de la demande ont été 10 traitées, le système informatique sélectionne la rangée la plus en haut dans l'ordre de spécificité parmi les rangées restantes, c-à-d les rangées qui n'ont pas été filtrées pendant le traitement incrémentiel des colonnes. Enfin, le système informatique retourne la valeur d'au moins une cellule de la rangée déterminée. 15 Selon un autre aspect, un système informatique agencé de façon à exécuter une méthode respective de détermination de la rangée la plus spécifique dans la table de base de données est fourni. Selon encore un autre aspect, un programme informatique pour ordonner à un système 20 informatique d'exécuter la méthode de détermination de la rangée la plus spécifique dans la table de base de données est fourni. BRÈVE DESCRIPTION DES DESSINS La présente invention sera décrite en référence aux dessins annexés. Les numéros de référence similaires indiquent généralement des éléments identiques ou fonctionnellement similaires. La figure 1 illustre une base de données avec une table de base de données. La figure 2 est un exemple générique d'une table de base de données et d'une demande. La figure 3 illustre la structure d'un index comme décrit dans les présentes. 3047580 4 La figure 4 est un exemple générique d'un index pour la table de base de données de la figure 2. La figure 5 donne un exemple générique de traitement de demande utilisant l'index 5 La figure 6 est un organigramme d'un exemple de traitement de demandes. La figure 7 est un exemple d'agencement d'un ensemble de tuples de pointeur en mémoire. 10 La figure 8 illustre une recherche binaire sur un ensemble de tuples de pointeur. La figure 9 est un exemple de génération d'index. La figure 10 est un organigramme de haut niveau d'un processus général comprenant la 15 génération d'index et la détermination de la rangée la plus spécifique. La figure 11 visualise de manière schématique l'entretien d'une table de base de données et l'index dans les mémoires d'un système informatique. 20 La figure 12 montre une table de routage en guise d'exemple de table de base de données. La figure 13 est un exemple de vue schématique de l'architecture interne d'un système informatique mettant en oeuvre la base de données et/ou un client demandeur. 25 DESCRIPTION DÉTAILLÉE L'index décrit dans les présentes facilite l'accès à une table de base de données qui est maintenue par un système de base de données. Le terme base de données tel qu'utilisé dans les présentes inclut toutes sortes de référentiels de données conservant des données statiques ou 30 dynamiques sous forme de tables. Ces sortes de référentiels de données comprennent, par exemple, des systèmes de base de données relationnelles tels que les bases de données Oracle®, Microsoft® SQL Server, Microsoft Access®, le système de base de données relationnelle objet tel que PostgreSQL, des systèmes de règles de production tels que des systèmes experts et des moteurs de systèmes de sélection d'action (par ex. des systèmes experts maintenant des actions 3047580 5 d'entretien et de réparation pour des dispositifs techniques), les éléments de commande et de réseau tels que les routeurs (avec des tables de routage), les noeuds de gestion de réseau (avec journal et/ou des données de commande conservées dans des tables) ou les systèmes SCADA (qui conservent aussi le journal et/ou les données de commande sous forme de tables) ainsi que 5 les systèmes propriétaires conservant les données par ex. dans de simples tables telles que les tableaux Microsoft Excel® ou les fichiers de texte tabulateur (par ex. fichiers csv). Généralement, la base de données est mise en oeuvre sur un système informatique tel qu'un serveur de base de données ou un noeud de réseau. La base de données est agencée pour recevoir 10 des demandes d'extraction (simplement ci-après dénommées « demandes ») précisant les critères de recherches (ci-après-dénommés « valeurs d'entrée ») pour traiter la demande en vérifiant les valeurs d'entrée par rapport à une table de base de données au moins, pour déterminer un enregistrement de données de la table de base de données qui remplit les valeurs d'entrée et pour retourner une ou plusieurs valeurs de cet enregistrement de données. À cette 15 fin, la base de données utilise tout type de langage de base de données et est équipée de tout type d'interface de communication connu dans la technique. L'auteur de la demande, par ex. un client (ordinateur, station mobile, application, etc.) dans un réseau local (LAN) ou dans un réseau distant interrogeant la base de données 1. 20 Comme le montre la figure 1, une base de données 1 maintient au moins une table de base de données 2. La table de base de données 2 est constituée d'un nombre de rangées 3 et d'un nombre de colonnes 4. Chaque rangée 3 de la table de base de données comprend un enregistrement de données et chaque colonne 4 de la table de base de données constitue un attribut des enregistrements de données, généralement conformément à un modèle de données 25 (tel qu'un modèle de gestion de base de données relationnelle). L'association des rangées 3 et des colonnes 4 forme la cellule 5. Généralement, tout nombre de rangées 3 et de colonnes 4 peut être présent dans la table de base de données 2. Des enregistrements de données peuvent être ajoutés ou supprimés, le nombre de rangées 3 notamment n'est pas fixé, mais il peut changer au fil du temps. La base de données 2 peut également inclure des mécanismes pour 30 redéfinir ou modifier le modèle de données, c-à-d que le nombre de colonnes peut aussi être adapté. Les cellules 5 de la table de base de données contiennent soit au moins une valeur soit aucune valeur (figure 2). Les valeurs dans les cellules sont généralement conformes à un type de 3047580 6 données défini pour la colonne respective, comme prescrit par le modèle de données. Les types de données comprennent, par exemple, des données Booléennes (c-à-d que les valeurs sont « vraies » ou « fausses »), des nombres entiers, des nombres à virgule flottante, des caractères, des chaînes, des pointeurs ainsi que des types de données complexes, fonctionnelles telles que 5 les dates. Plus d'une valeur peut être présente dans une cellule 5, c-à-d qu'une cellule 5 peut comprendre un vecteur ou une liste de valeurs, par ex. sous forme d'un ensemble, d'un enregistrement, d'une série, d'une énumération ou d'un objet de valeurs conformément à un type de données. Dans certains modes de réalisation, le système informatique est un routeur, la table de base de données est une table de routage, chaque rangée de la table de routage constitue 10 une règle de routage pour acheminer une demande entrante vers une destination, la table de routage comprend une colonne de destination avec des valeurs de destination possibles et une colonne d'acheminement avec les valeurs correspondantes indiquant un acheminement vers la destination 15 Les cellules 5 sans valeur peuvent comprendre des caractères de remplacement tels que NUL ou *. Ces caractères de remplacement précisent l'absence de valeur, c-à-d qu'une cellule respective est considérée comme incluant toute valeur de la gamme de valeurs autorisée pour le type de données des colonnes correspondantes, comme prescrit dans le modèle de données. Un exemple d'enregistrement de données utilisant des caractères de remplacement est 20 l'itinéraire standard dans une table de routage IP qui utilise l'adresse réseau « 0.0.0.0 » dans les colonnes d'adresse de destination et le masque de sous-réseau dans les colonnes de masque de sous-réseau comme caractère de remplacement pour toute adresse IP de destination possible (cf. exemple de table de routage de la figure 12). 25 La figure 2 montre un exemple générique de table de base de données 2 avec six rangées 3 (cà-d six enregistrements de données) et sept colonnes 4 (c-à-d que les enregistrements de données ont sept attributs). Les colonnes de cette table de base de données exemplaire définissent tout type d'attributs pour les enregistrements de données conservés par les rangées. La première colonne 4A définit un attribut clé des enregistrements de données. La première 30 rangée 3A définit, par exemple, un enregistrement de données par défaut avec des caractères de remplacement « * » dans les colonnes 4B à 4F et un « oui » dans la dernière colonne 4G qui est un type de donnée Booléenne. Par conséquent, la première rangée 3A précise « oui » comme réponse par défaut. Les autres rangées définissent des enregistrements de données plus spécifiques. Par exemple, la seconde rangée 3B précise un tuple de valeurs « A, B » comme 3047580 attribut dans la seconde colonne 4B et « non » comme dernier attribut de l'enregistrement de données, tandis que toutes les autres cellules contiennent des caractères de remplacement (négligeant la colonne clé 4A), c-à-d que toute valeur pour ces attributs tombent dans l'enregistrement de données de la rangée 3B. Par exemple, le modèle de données peut définir 5 des valeurs F, G, H, I, J et K comme plage de données autorisée pour la troisième colonne 4C. Par conséquent, le caractère de remplacement dans la troisième cellule du second enregistrement de données (rangée 3B, colonne 4C) représente toutes les valeurs possibles F, G, H, I, J et K de cet attribut du second enregistrement de données. 10 La table de base de données 2 est généralement stockée dans la mémoire du système informatique, par exemple dans la mémoire principale (RAM). Comme exposé au départ, l'index de la table de base de données décrit dans les présentes est en particulier agencé pour permettre de déterminer la rangée la plus spécifique correspondant à 15 une demande. En général, les rangées contenant plus de caractères de remplacement (c-à-d plus de non valeurs, moins de cellules avec valeurs) que les autres rangées sont considérées comme étant moins spécifiques que les rangées comprenant moins de caractères de remplacement (cà-d moins de non valeurs, plus de cellules avec valeur). En d'autres termes, les rangées comprenant des enregistrements de données plus généraux sont définies pour être moins 20 spécifiques que les rangées avec un contenu plus précis ; ces dernières sont définies pour être plus spécifiques. Afin de faciliter la détermination de la rangée la plus spécifique qui correspond aux valeurs d'entrée d'une demande, un ordre de spécificité parmi les rangées de la table de base de données 2 est soit donné, soit établi. En option, l'ordre de spécificité est implicite dans le tri de la rangée. Par exemple, les rangées sont triées dans la table de non spécifique à très 25 spécifique, comme dans l'exemple de la table de base de données indiqué à la figure 2. Dans certains modes de réalisation, l'ordre de spécificité est explicitement défini, par ex. par une colonne spécifique indiquant le niveau respectif de spécificité des rangées, telle que les valeurs clés dans la colonne clé 4A de la table de base de données 2 à la figure 2. En option, l'ordre de spécificité strictement monotone, c-à-d que chaque rangée de la table de base de données a un 30 ordre de spécificité unique. Dans d'autres exemples, les catégories de spécificité sont définies, et de multiples rangées peuvent partager un niveau commun de spécificité. Dans les derniers exemples, un mécanisme est présent pour s'assurer qu'une seule rangée de rangées multiples membre du même niveau de spécificité remplit les valeurs d'entrée dans la demande, par ex. les rangées définissent mutuellement des enregistrements de données exclusifs et les valeurs 3047580 sont indiquées dans la demande pour un nombre minimum de rangées de la table de base de données. En réponse à la réception d'une demande indiquant au moins des colonnes et des valeurs 5 d'entrée respectives, la base de données 1 procède à la demande avec les valeurs d'entrée comprises dans la demande et compare les valeurs d'entrée avec la table de base de données 2 afin de déterminer la rangée la plus spécifique remplissant les valeurs d'entrée. En se référant à nouveau à la figure 2, un exemple générique de demande entrante 9 est reçu. Dans l'exemple de la figure 2, l'ordre de spécificité est explicitement défini par la colonne 4A qui trie les 10 rangées conformément aux valeurs clés, tandis que la rangée 3A est la rangée la moins spécifique (étant donné qu'elle contient cinq caractères de remplacement et seulement une valeur dans la colonne 4G) et la rangée 3F est la valeur la plus spécifique (étant donné qu'elle ne contient aucun caractère de remplacement mais seulement des cellules avec valeurs). Dans l'exemple de la figure 2, la demande entrante 9 indique les cinq colonnes 4B, 4C, 4D, 4E et 4F 15 ainsi que les valeurs d'entrée respectives. La base de données 1 détermine que la dernière rangée 3F est la rangée la plus spécifique correspondant à la demande entrante 9, étant donné que la valeur « A » dans la cellule 4B/3F correspond à la valeur d'entrée A pour la colonne 4B, la valeur « F » dans la cellule 4C/3F correspond à la valeur d'entrée F pour la colonne 4C, les valeurs « P, R » dans la cellule 4D/3F correspondent à la valeur d'entrée P pour la colonne 4D, 20 la valeur « W » dans la cellule 4E/3F correspond à la valeur d'entrée W pour la colonne 4E et la valeur « Z » dans la cellule 4F/3F correspond à la valeur d'entrée Z pour la colonne 4F. Les deux autres rangées 3A et 3B qui correspondent également aux valeurs d'entrée 6 de la demande entrante 9 sont moins spécifiques que la rangée 3F, étant donné qu'elles sont classées plus bas dans la spécificité de l'ordre défini implicitement de la table de base de données 2. 25 Une fois que la rangée 3 la plus spécifique est déterminée, au moins une valeur (attribut) de la rangée la plus spécifique est retournée. Dans l'exemple de la figure 2, la valeur de la colonne 4G de la rangée 3F est retournée, c-à-d la valeur Booléenne « non ». 30 La détermination de la rangée la plus spécifique correspondant à une demande utilise l'index 10 décrit dans le présent document (figure 3). L'index de la table de base de données 2 comprend les éléments suivants : - Il existe une structure d'index 11 pour chaque colonne 4 de la table de base de données pour laquelle les valeurs d'entrée dans une demande sont attendues. Une structure 3047580 9 d'index 11 fait par conséquent également référence à une structure d'index spécifique à la colonne ci-après. Chaque structure d'index 11 spécifique à la colonne dispose de deux éléments, à savoir o un ensemble de tuples de pointeurs 12 et 5 o un bitmap 13 (comme habituellement compris par la personne qualifiée, un bitmap est une collection de bits contigus, c-à-d un tableau de bits). L'ensemble de tuples de pointeur 12 a pour fonction de se référer à toutes les valeurs dans les cellules de la colonne à laquelle la structure d'index 11 respective, spécifique à la colonne, fait référence. Chaque tuple de pointeur 14 dans l'ensemble 12 comprend 10 un premier pointeur 15 et un second pointeur 16. o Le premier pointeur 15 fait référence à l'une des valeurs comprises dans la colonne. La valeur est stockée à un emplacement particulier dans la mémoire du système informatique hébergeant la base de données 1. Le premier pointeur fait référence à cet emplacement de mémoire. 15 o Le second pointeur 16 indique la rangée de la table de base de données 2 dans laquelle la valeur apparaît. Par exemple, la rangée est identifiée par une valeur clé qui est encore stockée à un emplacement de mémoire particulier dans la mémoire du système informatique hébergeant la base de données 1. Le second pointeur fait référence à cet emplacement de mémoire. 20 Ainsi, le nombre de tuples de pointeur 14 compris dans l'ensemble 12 correspond au nombre de valeurs apparaissant dans la colonne à laquelle la structure d'index 11 respective, spécifique à la colonne, fait référence. - Le bitmap 13 précise les cellules dans la colonne à laquelle la structure d'index 11 respective, spécifique à la colonne, fait référence et qui n'a pas de valeurs, c-à-d qu'elle 25 comprend des caractères de remplacement. Le bitmap 13 est par conséquent également appelé « bitmap sans valeur ». Le nombre de bits dans le bitmap sans valeur 13 correspond au nombre de rangées 3 de la table de base de données 2. La figure 4 est un exemple d'un index 10. L'exemple d'index donné avec la figure 4 est lié à 30 l'exemple générique de table de base de données de la figure 2. L'index 10 indiqué par la figure 4 est composé de cinq structures d'index 11 correspondant aux colonnes 4B à 4F de table de base de données 2 de la figure 2 pour laquelle les valeurs d'entrée 6 sont attendues (la colonne 4G avec le type de données Booléennes ne peut pas être demandé dans l'exemple de la figure 3047580 10 2 : les valeurs de cette colonne sont des valeurs de retour). Chacune des structures d'index 11 contient un ensemble de tuples de pointeur 12 et le bitmap 13 sans valeur. L'ensemble de tuples de pointeur 12 dans chaque structure d'index 11 spécifique à la colonne 5 constitue une liste compacte de toutes les valeurs comprises dans la colonne respective de table de base de données 2. Par exemple, l'ensemble 12B dans la structure d'index 11B liste la présence de toutes les valeurs A, B et C apparaissant dans la colonne 4B. La valeur A apparaît dans les rangées avec les valeurs clés R2, R4 et R6 ; la valeur B est présente dans les rangées avec les valeurs clés R2 et R5 et la valeur C est présente dans les rangées avec les valeurs clés 10 R3 et R4 (cf. figure 2). Comme susmentionné, les premiers pointeurs dans les tuples de pointeurs font référence à l'adresse de mémoire respective des valeurs A, B et C dans la mémoire de l'ordinateur, tandis que les seconds pointeurs dans les tuples de pointeurs indiquent la rangée correspondante c-à-d font référence aux valeurs clés de la rangée dans cet exemple. La même chose est vraie pour les autres ensembles 12C à 12F dans les structures d'index 11C 15 à 11F. En option, les tuples de pointeur 14 dans les ensembles 12 sont triés par la valeur référencée par les premiers pointeurs. Dans la figure 4, par exemple, les tuples de pointeur dans l'ensemble 12B sont triés par les valeurs A, B et C apparaissant dans la colonne 4B. Par conséquent, les 20 trois premiers tuples de pointeur dans l'ensemble 12B définissent l'apparition de la valeur A dans la colonne 4B ; les deux prochains tuples de pointeurs définissent l'apparition de la valeur B dans la colonne 4B et les deux derniers tuples de pointeurs définissent l'apparition de la valeur C dans la colonne 4B. Trier les tuples de pointeur 14 dans l'ensemble facilite l'accès mémoire efficace, si on utilise l'index 10, par ex. pour réaliser une recherche linéaire sur les 25 tuples de pointeur 14 parce que les valeurs respectives nécessitent seulement d'être chargées une fois à partir de la mémoire, si on traite le premier tuple de pointeur qui définit les apparitions d'une valeur, et sont ensuite disponibles par ex. dans le cache du processeur pour les tuples de pointeur suivants toujours liés à la même valeur. Trier les tuples de pointeur 14 facilite également une recherche binaire sur les tuples de pointeur qui sont utilisés dans certains modes 30 de réalisation (plus amplement expliqués ci-dessous en référence à la figure 8). Le bitmap 13 fournit une représentation compacte de l'apparition de la cellule sans valeur dans la table de base de données 2. Chaque bitmap 13 comprend six bits qui coïncident avec le nombre de rangées 3 dans la table de base de données 2 dans l'exemple de la figure 2. Par 3047580 11 définition, la séquence des bits dans les bitmaps respectifs correspond à la séquence des rangées avec des valeurs clés R1 à R6, c-à-d que le premier bit de chaque bitmap 13 fait référence à la rangée avec la valeur clé R1, le second bit dans chacun des bitmaps fait référence à la rangée avec la valeur clé R2 et ainsi de suite et le dernier bit dans chaque bitmap 13 fait référence à la 5 dernière rangée avec la valeur clé R6. Dans l'exemple de la figure 4, les bits mis à « 1 » désignent toutes les rangées dans la colonne respective sans valeur (c-à-d avec des caractères de remplacement) tandis que les bits mis à « 0 » désignent des rangées dans la colonne respective avec valeurs (c-à-d sans caractère de remplacement). Par exemple, le bitmap 13B indique que seule la première rangée (valeur clé R1) dans la colonne 4B ne comprend pas de 10 valeur tandis que les autres rangées (valeurs clés R2 à R6) comprennent des valeurs. La même chose s'applique aux autres bitmaps 13C à 13F de manière analogue pour les cellules sans valeur dans les colonnes 4C à 4F. L'index 10 comme décrit ci-dessus représente une structure de métadonnées particulièrement 15 compacte (si comparé aux index ultramodernes actuellement connus). Dans certains modes de réalisation, l'index est stocké dans un cache de processeur du système informatique et reste stocké dans le cache de processeur après que la valeur d'au moins une cellule de la rangée déterminée ait été retournée pour être disponible pour d'autres demandes de traitement. L'emplacement des cellules sans valeur n'est pas stocké en tant que tuples de pointeur 14 mais 20 sous la forme des bitmaps 13 qui diminue le nombre de tuples de pointeurs 14. La taille d'un tuple de pointeur 14 est toujours une puissance de 2. Par exemple, un pointeur a la taille de 8 octets dans une architecture de mémoire 64 bits, ce qui augmente la taille à 16 octets pour un tuple de pointeur 14. Dans la mesure où la multiplication d'entiers pour le nombre de taille en puissance de 2 est plus efficace que pour les nombres de taille en non puissance de 2, les accès 25 aléatoires dans l'index 10 sont efficaces. Pour certaines catégories de tables de base de données (par ex. des tables avec 1 000 entrées ou moins), l'index 10 rentre dans les caches de CPU L1 et/ou L2 et peut donc être disponible en permanence dans une mémoire à accès très rapide et la performance globale du traitement de la demande et de la détermination de la rangée est améliorée. De plus, l'index 10 facilite un algorithme de recherche binaire pour déterminer la 30 rangée la plus spécifique, comme décrit plus loin ci-dessous (en référence à la figure 8). L'index 10 indique également un ordre de spécificité des rangées 3 de la table de base de données 2. Des manières différentes sont envisagées pour cette indication. Par exemple, comme susmentionné en référence à la figure 2, la table de base de données 2 elle-même est déjà triée 3047580 12 conformément à son ordre de spécificité par ex. de la spécificité la plus basse à la plus élevée (cf. également activité 38 à la figure 9 et activité 17 à la figure 10). Dans de tels modes de réalisation, l'ordre de spécificité des rangées de la table de base de données est implicitement présent dans l'index 10 dans les bitmaps 13 sans valeur. Comme expliqué ci-dessus, les bitmaps 5 13 sans valeur comprennent un bit pour chaque rangée 3 de table de base de données 2 et l'ordre des bits dans les bitmaps 13 correspond à l'ordre des rangées 3 de la table de base de données 2. Ainsi, le premier bit respectif dans les bitmaps 13 fait référence à la première rangée (par ex. rangée 3A dans la figure 2) qui est par ex. la rangée la moins spécifique et le dernier bit respectif dans les bitmaps 13 sans valeur fait référence à la dernière rangée (par ex. rangée 3F dans la 10 figure 2) qui est par ex. la rangée la plus spécifique de la table de base de données 2. Dans d'autres modes de réalisation, les rangées de la table de base de données 2 ne sont pas triées par spécificité mais l'index 10 comprend une structure de données séparée définissant l'ordre de spécificité des rangées 3. Par exemple, les valeurs de pondération 7 (voir figure 3) sont associées aux rangées 3 quand elles génèrent l'index 10 (voir également activité 44 dans la 15 figure 9) et sont explicitement maintenues en tant que métadonnées définissant l'ordre de spécificité des rangées 3 dans l'index 7. En réponse à la réception d'une demande entrante 9, le système informatique hébergeant la base de données 1 utilise l'index 10 pour déterminer la rangée la plus spécifique comme suit. En 20 général, un processus incrémentiel est réalisé. Il traite la demande colonne par colonne, pour chaque colonne (et la valeur d'entrée respective 6) indiquée dans la demande entrante 9. En commençant par la première colonne 4 indiquée dans la demande entrante 9 (colonne 4B avec la valeur d'entrée « A » dans l'exemple de la figure 2), le système informatique utilise le 25 bitmap 13 de la structure d'index 11 pour la première colonne (structure d'index 11B avec le bitmap 13B dans l'exemple de la figure 2) afin de s'assurer que toutes les rangées 3 de la table de base de données 2 qui ne contiennent aucune valeur ne sont pas rejetées parce que ces rangée[s] comprennent des caractères de remplacement qui incluent toute valeur d'entrée. Par conséquent, dans l'exemple des figures 2 et 4, la rangée R1 (indiquée par le « 1 » dans le bitmap 30 13B) est définitivement maintenue. A ce stade, aucune décision n'est prise concernant le maintien ou le rejet des autres rangées marquées d'un « 0 » dans le bitmap 13B. Ensuite, en plus de maintenir les rangées conformément à l'utilisation du bitmap sans valeur, les tuples de pointeur 14 de la structure d'index 11 pour la première colonne (structure d'index 3047580 13 11B avec un ensemble de tuples de pointeur 12B dans l'exemple de la figure 2) sont utilisés pour maintenir toutes les rangées 3 qui comprennent la valeur d'entrée respective (valeur d'entrée « A » dans l'exemple de la figure 2) et pour filtrer toutes les rangées 3 de la table de base de données 1 qui ne comprennent pas la valeur d'entrée 6. Dans l'exemple des figures 2 5 et 4, toutes les rangées qui comprennent la valeur « A » (à savoir les rangées R2, R4 et R6) sont maintenues tandis que les rangées restantes qui ne contiennent pas la valeur d'entrée « A » dans la colonne 4B (rangées R3 et R5) sont rejetées. Comptabiliser les décisions de maintien ou de rejet tout au long de ce processus incrémentiel 10 est, dans certains modes de réalisation, basé sur des bitmaps temporaires supplémentaires (appelés bitrnaps résultat, décrits plus en détail ci-dessous) indiquant les rangées qui sont encore maintenues et les rangées qui ont déjà été rejetées. Ce processus est répété pour chaque colonne 4 indiquée dans la demande entrante 9. À chaque 15 itération, aucune, une ou plusieurs rangées 3 de la table de base de données 2 est/sont rejetées. Une fois que toutes les colonnes 4 indiquées dans la demande entrante 9 ont été traitées, une ou plusieurs rangées 3 conformes aux valeurs d'entrée indiquées dans la demande restent. Le système informatique sélectionne ensuite, en utilisant l'index 10, la rangée 3 à partir de rangées restantes qui est la plus en haut dans l'ordre de spécificité. Dans l'exemple des figures 2 et 4, 20 les rangées 3A, 3B et 3F (c-à-d les rangées avec les valeurs clés R1, R2 et R6) remplissent les valeurs d'entrée 6 de la demande entrante 9 en exemple à la figure 2. La rangée la plus spécifique est la rangée 3F (valeur clé R6). Dans l'exemple des figures 2 et 4, l'ordre de spécificité est donné par le tri des rangées qui se reflète aussi dans l'index 10 (dans les bitmaps 13 ainsi que dans les bitmaps résultats décrits ci-dessous). Ainsi, dans l'exemple des figures 2 25 et 4, le système informatique choisit la rangée restante avec la valeur clé de plus élevée (qui se situe le plus à droite dans les bitmaps 13 et dans le bitmap résultat décrit ci-dessous). Puis, un exemple de mise en oeuvre du traitement de la demande incrémentielle et du processus de détermination de la rangée est décrit à la figure 5. Cet exemple réutilise l'exemple de la table 30 de base de données 2 de la figure 2 et l'index 10 correspondant comme indiqué à la figure 4, ce dernier étant représenté à gauche de la figure 5. En général, l'exemple de traitement de la demande est basé sur deux bitmaps supplémentaires pour utiliser les tuples de pointeur 14 et les bitmaps sans valeur, c-à-d un bitmap colonne 23 et un bitmap résultat 25. À la fois le bitmap colonne 23 et le bitmap résultat 25 comprennent un nombre de bits qui correspond au nombre 3047580 14 de rangées dans table de base de données 2. L'objet du bitmap colonne 23 est d'indiquer, lors de chaque itération à travers la colonne 4 et la valeur d'entrée 6 correspondante, indiquée dans la demande entrante 9, les rangées 3 de la table de base de données qui comprennent la valeur d'entrée respective. L'objet du bitmap résultat 25 est d'indiquer, à travers le traitement de la demande incrémentielle, les rangées 3 restantes de la table de base de données qui sont encore des rangées candidates remplissant éventuellement toutes les valeurs d'entrée 6 dans la demande entrante 9 et, en même temps, d'indiquer toutes les rangées 3 de la table de base de données 2 qui ont été filtrées parce qu'elles ne correspondent pas à une ou plusieurs valeurs d'entrée 6. 10 Le traitement de la demande commence avec l'initialisation du bitmap résultat 25, par ex. définir tous les bits du bitmap résultat 25 à « 1 », tandis que chaque « 1 » indique que la rangée 3 associée au bit respectif dans le bitmap résultat 25 n'a pas encore été filtrée, c-à-d qu'elle est encore une rangée candidate qui remplit éventuellement toutes les valeurs d'entrée 6 comprises 15 dans la demande entrante 9. Par conséquent, au début du traitement de la demande, toutes les rangées 3 de la table de base de données sont des candidates valides. Ensuite, la première itération concernant la première colonne et la valeur d'entrée 6 respective (dans l'exemple des figures 2 et 4 : la colonne 4B avec valeur d'entrée 6B = « A ») est traversée. 20 Elle se compose de deux activités utilisant la structure d'index respective (ici : structure d'index 11B). La première activité concerne la détermination des rangées 3 de la table de base de données 2 qui remplissent l'actuelle valeur d'entrée 6B. La seconde activité concerne la comptabilisation des rangées candidates restantes maintenues à travers toutes les itérations. 25 Concernant la première activité, le bitmap colonne 23B est initialisé avec les valeurs de bit du bitmap 13 sans valeur de la colonne 4 considérée pendant l'itération actuelle (ici : colonne 4B, bitmap sans valeur 13B). Ainsi, dans l'exemple, le bitmap colonne 23B est mis à 1-0-0-0-0-0 et indique par conséquent que la rangée 3A (valeur clé R1) doit absolument être maintenue (parce qu'elle comprend un caractère de remplissage dans la colonne 4B). Ensuite, l'ensemble 30 de tuples de pointeur 12B fait l'objet d'une recherche pour toutes les rangées comprenant la valeur d'entrée « A ». Dans certains modes de réalisation, la recherche est une recherche binaire (expliquée plus loin ci-dessous à la figure 8). Dans d'autres modes de réalisation, la recherche est une recherche linéaire. Dans l'exemple, la recherche dans un ensemble de tuples de pointeur 12B indique que les rangées avec des valeurs clés R2, R4 et R6 comprennent un « A » dans la 3047580 15 colonne 4B actuellement envisagée. Les bits dans le bitmap colonne 23B correspondant aux rangées qui ont été déterminées pour comprendre la valeur d'entrée 6B sont donc mis à « 1 », étant donné qu'ils remplissent la première valeur d'entrée 6B et qu'ils doivent donc être maintenus. Par conséquent, dans l'exemple, le second, le quatrième et le sixième bits du bitmap 5 colonne 23B sont mis à « 1 », le bitmap colonne 23B est à présent fixé à 1-1-0-1-0-1; ce qui signifie que la première, la seconde, la quatrième et la sixième rangées (valeurs clés R1, R2, R4 et R6) sont toujours des rangées candidates tandis que la troisième et la cinquième rangées (valeurs clés R3 et R5) sont filtrées. À ce stade, le bitmap colonne 23B indique, pour l'itération actuelle, que toutes les rangées qui remplissent la première valeur d'entrée 6B sont comprises 10 dans la demande entrante 9. Concernant la seconde activité, le bitmap colonne 23B établi est associé à la version actuelle du bitmap résultat 25 afin d'inclure le résultat de détermination de rangée de l'actuelle itération dans la comptabilisation globale des rangées candidates. Dans l'exemple, toutes les rangées 15 candidates restantes sont indiquées par des bits mis à « 1 », tandis que toutes les rangées filtrées sont indiquées par des bits mis à « 0 ». Par conséquent, une opération ET logique bit à bit est réalisée entre le bitmap colonne 23B et la version actuelle du bitmap résultat 25, découlant d'une version 25B du bitmap résultat mise à jour. Dans l'exemple, la version 25B du bitmap résultat mise à jour est donc mise à 1-1-0-1-0-1. 20 Voilà qui conclut la première itération concernant la première colonne indiquée dans la demande entrante 9 et la valeur d'entrée 6 correspondantes. Les itérations suivantes sont réalisées de la même manière. Une fois de plus, lors de chaque itération suivante, le bitmap colonne 23 est réinitialisé avec les valeurs de bit des bitmaps respectifs sans valeur (dans 25 l'exemple, les bitmaps sans valeur 13C à 13F, les versions d'initialisation 23C à 23F des bitmaps colonnes). Ensuite, on recherche des occurrences des valeurs d'entrée respectives comprises dans la demande entrante 9 (dans l'exemple, valeurs d'entrée 6C à 6F) dans l'ensemble respectif de tuples de pointeur (dans l'exemple, ensembles 12C à 12F). Les bits respectifs qui correspondent aux rangées incluant la valeur d'entrée 6 sont mis à « 1 » dans le 30 bitmap colonne 23. La version respective en résultant 23C-23F du bitmap colonne est associée à la version actuelle respective 25C-25F du bitmap résultat par l'opération ET bit à bit. Dans l'exemple, la version finale du bitmap résultat 25F indique que la première rangée, la seconde rangée et la sixième rangée remplissent toutes les valeurs d'entrée 6 comprises dans la 3047580 16 demande entrante 9. La dernière activité du traitement de la demande concerne la sélection de la rangée la plus spécifique parmi les rangées restantes après la fin des itérations. À cette fin, l'indication de l'ordre de spécificité dans l'index 10 est utilisée. Dans l'exemple, l'ordre de spécificité est donné par le tri des rangées 3 de table de base de données 2 qui se reflète dans la 5 séquence de bits (correspondant aux rangées) dans les bitmaps 13 sans valeur, dans le bitmap colonne 23 et dans le bitmap résultat 25. Ainsi, dans l'exemple, la rangée la plus spécifique parmi les rangées candidates restantes est donnée par le « 1 » le plus à droite (numéro de référence 27) dans la version finale 25F du bitmap résultat. 10 Bien que le traitement de la demande implique un nombre d'opérations de complexité 0(n), il comporte de nombreuses caractéristiques techniques avantageuses. Un espace mémoire limité suffit pour exécuter les opérations. Les deux bitmaps supplémentaires, le bitmap colonne 23 et le bitmap résultat 25 comprennent un nombre de bits qui correspond au nombre de rangées dans table de base de données 2. Par conséquent, pour une table de base de données avec par ex. 15 1024 rangées, le bitmap colonne 23 et le bitmap résultat 25 ont une taille de 128 octets chacun. De plus, le traitement de la demande est déterministe parce que le nombre d'itérations de colonne de la base de données est prédéterminé respectivement par le nombre de colonnes de la table de base de données et de colonnes indiquées dans la demande. Par conséquent, pour les tables de base de données avec un certain nombre de rangées, le temps de réponse pour chaque 20 traitement de demande est déterministe. De plus, le nombre d'opérations de recherche et d'opérations de comparaison de valeur (comparant les valeurs d'entrée aux valeurs référencées par les premiers pointeurs 15 respectifs) pour chercher les ensembles de tuples de pointeur 12 en présence des valeurs d'entrée 6 est 25 réduit en faveur des opérations de bitmap (telles que les opérations ET logiques bit à bit). Bien que les opérations de bitmap impliquent des opérations 0(n), n est relativement petit (correspond au nombre de rangées 3) et l'opération de bitmap exploite en général pleinement les capacités du matériel informatique moderne. Par exemple, les instructions d'assemblages individuelles des architectures 64 bits traitent 64 bits à la fois. De plus, le traitement de la 30 présente demande est spécifiquement adapté aux CPU équipés d'unités informatiques 000 (out-of-order, en désordre) qui ont la capacité d'effectuer plusieurs calculs par cycle d'horloge sur un seul noyau, à condition qu'il n'y ait aucune dépendance entre ces calculs. La dernière condition applique les opérations de bitmap parce chaque opération individuelle ET par bit dans une opération ET générale entre le bitmap colonne 23 et le bitmap résultat 25 est indépendante. 3047580 17 Réduire la part de recherche et d'opérations de recherche au bénéfice d'une part accrue d'opérations de bitmap concerne spécifiquement un agencement d'extension de vecteur des CPU. Les CPU équipés d'un ensemble d'instructions SSE2 (extensions SIMD en continu, 5 SIMD = une seule instruction, données multiples) offrent notamment la possibilité de traiter 128 bits en une instruction d'assemblage, un ensemble d'instructions AVX2 (Advanced Vector Extensions, extension de vecteur évolué) pour traiter 256 bits en une instruction d'assemblage ou AVX-512 (par ex. la génération « Knights Landing » d'Intel®) permettant le traitement de 512 bits en une instruction d'assemblage. Par exemple, avec le dernier ensemble d'instructions, 10 une opération ET bit à bit entre le bitmap colonne 23 et le bitmap résultat 25 pour une table de base de données 2 avec 1 000 rangées peut être réalisée en deux cycles CPU. Le fonctionnement de ce traitement de demande est illustré dans le graphique de la figure 6. Premièrement, à 20, le système informatique hébergeant la base de données 1 reçoit une 15 demande entrante 9. En réponse à la réception de la demande, le bitmap résultat 25 est initialisé à 22. Ainsi, le processus incrémentiel 24 est réalisé. Dans l'itération colonne par colonne pour chaque colonne et valeur d'entrée respective 6 indiquée dans la demande entrante 9, le bitmap colonne 23 est initialisé à 24A, sur la base du bitmap respectif 13 sans valeur. Puis, à 24B, on recherche dans l'ensemble de tuples de pointeur 12 toutes les rangées 3 de la colonne actuelle 20 4 qui comprennent la valeur d'entrée 6 respective et le bitmap colonne 23 est mis à jour en conséquence. Puis, à 24C, le bitmap colonne 23 et la version actuelle du bitmap résultat 25 sont associées, par ex. par l'opération ET logique bit à bit afin d'obtenir un bitmap résultat mis à jour. Une fois que toutes les colonnes 4 et les valeurs d'entrée respectives 6 indiquées dans la demande entrante 9 ont été traitées de cette manière incrémentielle, la rangée la plus spécifique 25 parmi les rangées restantes indiquée dans la version finale du bitmap de résultat 25 est sélectionnée à 26. Finalement, à 35, au moins une valeur de la rangée la plus spécifique déterminée est retournée. Il est également possible que le bitmap résultat ne contienne que « 0 » bit après la dernière itération du traitement de la demande. Dans ce cas, aucune des rangées dans la table de base de données ne remplit la demande et la valeur de retour est donc une valeur 30 « de non-correspondance ». Dans certains modes de réalisation, l'attribution de bits dans les bitmaps 13 sans valeur est inverse (en comparaison à l'exemple de la figure 4), c-à-d que les bits mis à « 0 » désignent toutes les rangées dans la colonne respective sans valeur (c-à-d avec des caractères de 3047580 18 remplacement) tandis que les bits mis à « 1 » désignent des rangées dans la colonne respective avec valeurs (c-à-d sans caractère de remplacement). Dans ces modes de réalisation, l'affectation de bits dans le bitmap colonne 23 et dans le bitmap résultat 25 est inversé, c-à-d que tous les bits mis à « 0 » dans le bitmap colonne 23 indiquent les rangées 3 de la colonne 5 considérée qui comprennent la valeur d'entrée respective 6 et chaque « 0 » dans le bitmap résultat 25 indique que la rangée 3 associée au bit respectif n'a pas encore été filtrée, c-à-d qu'elle est encore une rangée candidate qui remplit potentiellement toutes les valeurs d'entrée 6 comprises dans la demande entrante 9. Par conséquent, dans ces modes de réalisation, le bitmap colonne 23 et le bitmap résultat 25 sont associés par une opération logique OU bit à bit. 10 Dans certains modes de réalisation, le traitement de la demande incrémentielle (activité 24 dans la figure 6) et en particulier, la recherche des ensembles de tuples de pointeur 12 pour vérifier la présence d'une valeur d'entrée (activité 24B dans la figure 6) comprend une recherche binaire au sein des tuples de pointeur 14 stockés de façon adjacente dans une mémoire du système 15 informatique hébergeant la base de données 1 (figures 7 et 8). La figure 7 donne un exemple générique de tuples de pointeur 14 qui sont stockés de façon adjacente à un endroit dans la mémoire 28 du système informatique hébergeant la base de données 1. Comme le montre la représentation schématique de la figure 7, chaque tuple de pointeur 14 unique est disposé consécutivement dans la mémoire 28 dans un ensemble de tuples de pointeur 14 sans trous 20 entre. Cette disposition des tuples de pointeur 14 dans la mémoire 28 facilite l'accès direct au nième tuple de pointeur (c-à-d tout tuple de pointeur arbitraire avec l'ensemble 12) et facilite donc une recherche binaire pour chaque itération colonne par colonne de la demande entrante 9. 25 La figure 8 est un exemple générique de recherche binaire pour l'activité 24B de la figure 6. Par exemple, comme susmentionné à la figure 4, les tuples de pointeur 14 dans l'ensemble 12 sont triés par les valeurs référencées par les premiers pointeurs 15 (qui trient pour les types de données respectifs de la colonne 4, par ex. l'ordre alphabétique pour les caractères et les chaînes). Cela permet l'exécution d'une recherche binaire sur les tuples de pointeur 14. 30 Conformément au principe « diviser pour mieux régner », l'algorithme de recherche binaire entre le milieu de l'ensemble 12 et examine si la valeur référencée par le premier pointeur 15D du tuple de pointeur 14D situé au milieu de l'ensemble 12 correspond ou non à la valeur d'entrée 6. Dans l'exemple de la figure 8, la valeur d'entrée « A » est donc comparée à la valeur « D » référencée par le premier pointeur 15D. Si la valeur d'entrée 6 est plus faible que la valeur 3047580 19 référencée par le premier pointeur 15 considéré, la même procédure est répétée dans la moitié supérieure (moitié gauche d'un ensemble 12 dans la figure 8, c-à-d avec le premier pointeur 15B). Si la valeur d'entrée 6 est plus élevée que la valeur référencée par le premier pointeur 15 considéré, la même procédure est répétée dans la moitié inférieure (moitié droite d'un ensemble 5 12 dans la figure 8, c-à-d avec le premier pointeur 15B). Comme montré dans les exemples des figures 4 et 5, il est possible que les premiers pointeurs multiples 15 se réfèrent à la même valeur. Dans l'exemple des figures 7 et 8, les premiers pointeurs 15A et 15B se référent tous deux à la valeur « A ». Si la comparaison entre la valeur 10 d'entrée 6 et la valeur référencée par le premier pointeur 15 actuellement considéré à un stade particulier de la recherche binaire montre que les deux valeurs sont égales, la recherche binaire n'est pas encore terminée à ce stade. La recherche binaire continue de déterminer d'autres tuples de pointeur 14 éventuels et les premiers pointeurs 15 qui font aussi référence à la valeur d'entrée 6. Par conséquent, après avoir trouvé une correspondance entre la valeur d'entrée 6 et la valeur 15 référencée par un premier pointeur 15, les tuples de pointeur 14 voisins situés à gauche et à droite du tuple de pointeur actuellement considéré (dans la mesure où ils sont présents) sont examinés jusqu'à ce qu'il y ait une non-correspondance entre la valeur d'entrée 6 et la valeur référencée par le premier pointeur respectif soit déterminée ou jusqu'à ce que l'algorithme arrive à un tuple de pointeur 14 déjà considéré auparavant. Dans l'exemple de la figure 8, 20 l'examen du premier pointeur 15B (qui est réalisé après l'examen du premier pointeur 15D) génère une correspondance entre la valeur d'entrée « A » et la valeur « A » référencée par le premier pointeur 15B. Dans cette situation, on détermine ensuite si les premiers pointeurs 15A et 15C font aussi référence ou non à la valeur « A ». La réponse est affirmative pour le premier pointeur 15A et négative pour le premier pointeur 15C. Par conséquent, la recherche binaire 25 dans l'exemple de la figure 8 se termine après que la valeur « A » a été trouvée comme présente dans les rangées R1 et R4 de la colonne 4 considérée. Les premiers pointeurs 15D, 15B, 15A et 15C ont été vérifiés pendant l'exécution de la recherche binaire. La recherche binaire utilisée par certains modes de réalisation a la complexité computationnelle 30 de 0(log n) et est par conséquent en général plus efficace que par ex. une recherche linéaire de complexité de 0(n). Dans certains modes de réalisation, la recherche binaire est mise en oeuvre de manière récursive. Dans certains modes de réalisation, la recherche binaire est mise en oeuvre de manière itérative. 3047580 20 Dans certains modes de réalisation, le système informatique hébergeant la base de données 1 est agencé pour générer l'index 10 à partir de la table de base de données 2. L'index 10 généré après la table de base de données 2 a été établi pour la première fois puis ensuite, en réponse à un changement de la table de base de données 2 tel qu'un changement d'une ou de plusieurs 5 valeurs dans les cellules 5, le remplacement d'une ou de plusieurs valeurs par un caractère de remplacement et vice versa, ajoute ou supprime une rangée 3 ou une colonne 4, etc. En général, la génération d'index comprend l'établissement d'une structure d'index 11 pour chaque colonne 4 de la table de base de données 2 pour laquelle les demandes entrantes 9 10 peuvent comprendre des valeurs d'entrée 6. Correspondant à la structure d'index 10, ce processus comprend principalement deux activités, à savoir l'initialisation et l'établissement de bitmaps 13 sans valeur de chaque structure d'index 11 et l'établissement d'un ensemble de tuples de pointeur 12 avec le premier pointeur respectif 15 et le second pointeur 16 dans les tuples de pointeur 14. 15 La figure 9 est un exemple de génération d'index. En option, pour les modes de réalisation avec un ordre de spécificité explicite ou implicite donné en triant les rangées 3 de la table de base de données 2 conformément à l'ordre de spécificité, les rangées de la table de base de données 2 sont triées à 38 (si cela n'a pas été fait au préalable). En général, trier les rangées de la table de 20 base de données dépend du nombre de cellules dans chaque rangée 3 sans valeur (par ex. avec des caractères de remplacement) et/ou de la spécificité des valeurs dans les cellules 5 de la rangée 3. Plus spécifiquement, dans certains modes de réalisation, les rangées 3 de la table de base de données 2 sont pondérées. Chaque cellule contribue au poids d'une rangée dans laquelle une rangée sans valeur ajoute moins de poids que chaque cellule avec au moins une valeur et, 25 dans certains modes de réalisation plus spécifiques, les cellules avec un nombre plus élevé de valeurs/des valeurs plus spécifiques ajoutent moins de poids à la rangée que les cellules avec un plus petit nombre de valeurs/des valeurs moins spécifiques. La séquence de rangées avec des valeurs de pondération identiques est choisie de manière arbitraire. Dans certains modes de réalisation, l'indication de l'ordre de spécificité est donnée par une rangée unique indiquant les 30 rangées triées, telles que dans l'exemple de la figure 2 (colonne 4A). Cet ordre de rangée peut fonctionner comme une clé primaire de la table de base de données 2. La génération d'index réelle commence ensuite avec l'initialisation du premier bitmap 13 sans valeur auquel peut renvoyer une demande entrante 9 (par ex. bitmap 13 lié à la colonne 4B, 3047580 21 renvoyant à l'exemple de la figure 4). L'initialisation du bitmap est par ex. liée à l'allocation de la quantité de mémoire requise par ex. dans la mémoire principale du système informatique hébergeant la base de données 1 et par ex. au fait de mettre tous les bits dans le bitmap 13 à « 0 » en n'indiquant initialement aucune cellule dans la colonne 4 sans valeur. Ensuite, à 40, 5 l'ensemble des tuples de pointeur 12 (par ex. ensemble 12B de la figure 4) est rempli avec les tuples de pointeur. Un tuple de pointeur 14 est ajouté à l'ensemble 12 pour chaque valeur apparaissant dans les rangées 3 de la colonne 4 considérée. À 41, le bitmap 13 sans valeur est mis à jour afin de refléter toutes les cellules dans la colonne sans valeur. Par exemple, tous les bits correspondant aux cellules sans valeur sont mis à « 1 ». En option, à 42, les tuples de 10 pointeur 14 dans l'ensemble 12 sont triés par les valeurs référencées par les premiers pointeurs 15 respectifs. A ce stade, la structure d'index 11 pour la première colonne (c-à-d par ex. la structure d'index 11B dans l'exemple de la figure 4) est intégralement générée. À 43, on vérifie si la table de base de données 2 a ou non une autre colonne pour laquelle une structure d'index 11 doit être établie. Si la réponse est affirmative, les activités 39 à 42 sont répétées pour cette 15 autre colonne 4 (par ex. la colonne 4C dans l'exemple de la figure 4) de la même manière, jusqu'à ce que les structures d'index 11 aient été générées pour toutes les colonnes 4 de la table de base de données qui peut être indiquée dans une demande entrante 9. En option, dans des modes de réalisation sans rangées 3 triées (par ex. l'activité 38 n'était pas 20 exécutée), un ensemble de valeurs de pondération 7 indiquant explicitement l'ordre de spécificité des rangées 3 est établi à 44. Dans des modes de réalisation qui permettent à plusieurs rangées de partager la même valeur de pondération et où plusieurs rangées d'un poids identique correspondent à la demande entrante 9, soit une rangée arbitraire parmi les rangées avec le même poids est sélectionnée comme étant la rangée la plus spécifique soit un mécanisme est 25 présent pour permettre uniquement des associations de valeurs disjointes pour les rangées avec le même poids, ce qui pour effet que seule une rangée à un certain niveau de pondération correspond à une demande entrante 9. La figure 10 est un exemple du flux de haut niveau d'un processus général réalisé par le système 30 informatique hébergeant la base de données 1 avec au moins une table de base de données 2. À 17, les rangées de la table de base de données trient pour constituer l'ordre de spécificité des rangées qui se reflète dans l'index 10. À 18, l'index 10 est généré (cf. exemple de la figure 9). Plus tard, une demande entrante 9 est reçue par le système informatique, la demande indique au moins une valeur d'entrée 6 pour une colonne 4 de la table de base de données 2. À 19, la 3047580 22 demande est traitée sur la base de l'index 10 afin de déterminer toutes les rangées de la table de base de données 2 qui correspondent à la/aux valeur(s) d'entrée de la demande entrante 9, par ex. par l'activité 22 et l'activité incrémentielle 24 présentée à la figure 6. À 34, la rangée la plus spécifique est sélectionnée à partir des rangées restantes qui sont la sortie d'activité 19 en 5 utilisant l'ordre de spécificité reflété dans l'index 10, par ex à la manière de l'activité 26 présentée à la figure 6. À 21, une ou plusieurs valeurs de la rangée la plus spécifique sélectionnée est/sont retournée(s). La disposition des diverses données de la table de base de données 1 dans la mémoire du 10 système informatique 100 hébergeant la base de données 1 est représentée par la figure 11. Le système informatique 100 a une mémoire adressable 30 qui comprend par ex. la mémoire principale ou la mémoire d'exploitation (RAM) du système informatique 100. Le système informatique 100 conserve la table de base de données 2 dans la mémoire adressable 30, dans certains modes de réalisation dans la RAM. Le traitement de la demande et la détermination de 15 la rangée la plus spécifique sont réalisés par l'unité centrale de traitement (CPU) 31. La CPU 31 comprend au moins un niveau de cache de processeur 32, dans certains modes de réalisation au moins trois niveaux (L1 cache, L2, cache, L3) de différentes tailles et de vitesses d'accès. L'index 10 avec les structures d'index 11 pour les colonnes 4 de la table de base de données 2 se situe également dans la mémoire adressable 30 du système informatique 100, dans certains 20 modes de réalisation dans au moins un des niveaux de cache de processeur. La mise en oeuvre de l'index présentée dans ce document est supérieure aux autres mécanismes d'index en termes de besoins en mémoire/compacité, comme ce sera le cas à partir de la comparaison suivante avec les mises en oeuvre d'index ultramodernes. La comparaison se base 25 sur une table de base de données 2 avec 1024 rangées et cinq colonnes qui peuvent être soumises à une demande entrante 9 avec des valeurs arbitraires. La table de base de données utilisée pour la comparaison comprend les rapports types du nombre de cellules sans valeur de 66 %, du nombre de cellules avec plus d'une valeur de 10 % et une taille moyenne des valeurs. La même table de base de données 2 est utilisée pour les mises en oeuvre comparées. La mise en oeuvre 30 d'index présentée dans ce document est comparée à deux autres manières connues d'indexer les rangées de la table de base de données. 3047580 23 - Les arbres rouges noirs sont une structure de données associative connue pour l'indexation. La mise en oeuvre se base sur le C++ std:map, fourni avec GCC 4.3.2 STL. - Les arbres B sont une autre structure de données associative pour l'indexation. Ils 5 sont utilisés pour améliorer la localité des données dans une mémoire ou sur un disque. La mise en oeuvre se base sur « klib » par chaos attractif qui est connu pour ses bonnes performances (voir https://github.com/attractivechaos/klibiblob/master/kbtree.h). Un facteur d'agrégation des 256 éléments qui est un bon compromis entre l'efficacité et la 10 compacité a été choisi. Les trois approches ont montré l'empreinte de mémoire suivante (1 octet de précision) pour les différents index (toutes les valeurs sont exprimées en octets). Structure d'index de la Index 10 Arbres rouges Arbres B noirs colonne 1 13824 94720 51040 Structure d'index de la colonne 2 13984 93504 50240 Structure d'index de la colonne 3 11936 88320 48400 Structure d'index de la colonne 4 13040 91776 50400 Structure d'index de la colonne 5 13104 91968 50080 Total 65888 460288 250160 La taille du cache Ll de l'actuelle CPU Intel ultramoderne est de 32 KO. Ainsi chaque structure d'index de l'index 10 comme présentée dans le présent document pour une table de base de données 2 avec 1024 rangées et plus rentre dans le cache Li de cette taille alors que ça n'est pas le cas pour les mises en oeuvre des Arbres rouges noirs et des arbres B. 15 3047580 24 La taille d'un cache L2 actuellement disponible est de 256 KO. Ainsi chaque structure d'index de l'index 10 comme présentée dans le présent document pour une table de base de données 2 avec 1024 rangées et plus rentre dans le cache L2 de cette taille alors que ça n'est pas le cas 5 pour les mises en oeuvre des Arbres rouges noirs et des Arbres B. Bien que l'index basé sur les Arbres B pour une table de base de données 2 avec 1024 rangées rentre dans le cache L2 de cette taille, il ne reste virtuellement plus d'espace dans le cache L2 pour les valeurs de la table de base de données 2 et les structures de données de comptabilisation telles que le bitmap colonne 23 et le bitmap résultat 25. 10 Tandis que les métadonnées d'index complètes et la table de base de données 2 complète rentre dans le cache L3 (plusieurs MO, en fonction du modèle de CPU) pour les trois mises en oeuvre d'index comparées ci-dessus, il faut noter que le cache L3 est partagé entre les noyaux CPU et est soumis à une synchronisation en surdébit. L'accès au cache L3 est par conséquent 15 considérablement plus lent en général que l'accès au cache L1 (en général 10 à 20 fois plus lent) et plus lent que l'accès au cache L2 (en général 4 à 8 fois plus lent). Ainsi, la compacité de mémoire inhérente à l'index 10 présenté dans ce document permet de maintenir l'index complet ou au moins une partie significativement plus élevée de l'index (en comparaison aux deux autres mises en oeuvre d'index connues susmentionnées) dans le cache Ll et/ou dans le 20 cache L2 qui constitue une performance très accrue du mécanisme de traitement de la demande pour déterminer la rangée la plus spécifique de la table de base de données 2 correspondant à la demande entrante 9. L'index 10 et les mécanismes de traitement de la demande basés sur l'index 10 présenté dans 25 ce document peuvent s'appliquer à toutes sortes de base de données différentes et de systèmes de type base de données, par exemple un routeur avec une table de routage. La figure 12 montre une table de routage 33 d'un routeur IP (c-à-d un routeur au niveau de la couche réseau du modèle de référence OSI) mais le présent index 10 est également applicable à tout autre type de routeur ou à tout type de routeur plus spécifique tels que les routeurs logiques et les routeurs 30 de logiciels (par ex. Enterprise Service Busses, ESB), les routeurs de matériels et backbone, les commutateurs haut de gamme, les routeurs DSL, les routeurs Wifi, etc. La table de routage 33 de la figure 12 est un exemple simple de table de base de données 2 qui a cinq rangées et cinq colonnes. Les colonnes, de gauche à droite, définissent l'adresse de 3047580 25 destination, le masque de sous-réseau, le bond suivant (par ex. le routeur suivant), l'interface de réseau de sortie du routeur ainsi qu'une indication métrique. Connue de la personne du métier, l'adresse de destination et le masque de sous-réseau forment ensemble une adresse de réseau (le masque de sous-réseau indique la gamme de bit de préfixe qui constitue l'adresse de 5 réseau tandis que les bits restant forment l'adresse hôte. Des paquets IP entrant devant être acheminés vers une destination forment les demandes entrantes 9. Le routeur examine l'adresse IP de destination d'un paquet IP entrant et le compare à la table de routage 33. À cet égard, le routeur détermine la rangée la plus spécifique de la table de routage 33 avec une adresse de réseau (c-à-d une adresse de destination dans la première colonne recouverte du masque de 10 sous-réseau dans la seconde colonne) incluant l'adresse IP de destination du paquet IP entrant. Un index 10 avec au moins une structure d'index 11 représentant les adresses du réseau de destination (formé de l'adresse de destination de la première colonne recouverte du masque de sous-réseau dans la seconde colonne de la table de routage 33) et le traitement de la demande décrit en détail ci-dessus sont utilisés pour déterminer la rangée la plus spécifique correspondant 15 à l'adresse IP de destination dans une demande entrante. Par exemple, un paquet IP avec une adresse de destination 192.168.1.23 est reconnu comme étant dirigé vers le réseau 192.168.1.0/24 (24 = masque de sous-réseau 225.225.225.0), c-à-d que la quatrième rangée est la rangée la plus spécifique de la table de routage 33 correspondant à cette demande entrante 9. D'un autre côté, pour un paquet IP avec un numéro de destination 123.123.123.123, la première 20 rangée de la table de routage 33 précisant l'itinéraire standard sera déterminée comme étant la rangée la plus spécifique de table de routage 33 correspondant à cette demande entrante 9. Par conséquent, ce paquet IP sera acheminé vers le saut suivant 192.168.1.1 via l'interface de réseau de sortie 192.168.1.2. 25 L'index 10 et les mécanismes de traitement de la demande basés sur l'index 10 présenté dans ce document sont également applicables à d'autres bases de données ou systèmes de type base de données, tels que les pare-feu avec des tables de filtrage (par ex. les filtres de paquet avec ou sans inspection à états, le filtre mandataire, le filtre de contenu), les moteurs de production, les moteurs de règles, (par ex. les référentiels de réparation précisant les procédures de 30 réparation pour tout type de symptômes d'erreur des dispositifs techniques), les moteurs en continu, les moteurs de vérification de transaction, etc. Par conséquent, le système informatique 100 est, par exemple, un noeud de réseau hébergeant un pare-feu, auquel cas la table de base de données 2 est une table de filtrage, la demande 3047580 26 entrante 9 est un paquet de données entrant et chaque rangée de la table de filtrage constitue une règle de filtrage pour permettre ou empêcher le paquet de données entrant d'être acheminé vers une destination. Les valeurs du paquet de données entrant (par ex. un paquet IP transportant un segment TCP ou UPC qui transporte un paquet de couches d'application tels qu'une 5 demande HTTP) telles qu'une adresse IP de destination, des adresses de port source et destination et les caractéristiques du paquet de données, comme le fait de savoir si le paquet de données appartient ou non à une connexion existante, sont vérifiées par rapport aux règles de filtrage définies par les rangées de la table de filtrage. La table de filtrage comprend par ex. au moins une colonne de destination avec des adresses de destination possibles (telles que des 10 adresses IP et/ou des adresses de port), par ex. une ou plusieurs colonnes sources avec des adresses sources possibles (telles que des adresses IP et/ou des adresses de port), par ex. une ou plusieurs colonnes avec des valeurs précisant les caractéristiques du paquet de données entrant (telles que « établies » faisant référence aux paquets appartenant à une connexion établie) et une colonne avec des valeurs Booléenne indiquant si le paquet de données entrant doit être 15 transmis ou rejeté. La règle de filtrage (c-à-d rangée) la plus applicable (c-à-d la plus spécifique) est déterminée sur la base des valeurs d'entrée 6 dans le paquet de données et la valeur correspondante de la dernière colonne mentionnée (c-à-d oui ou non = accepter ou rejeter) est retournée. 20 Au cas où le système informatique 100 est, par exemple, un moteur de règles, la table de base de données 2 est une table de règles et chaque rangée de la table de règles constitue une règle pour répondre à la demande. Les colonnes de la table de règles définissent les critères des règles. Les valeurs d'entrée 6 de la demande qui définissent des critères de règles particuliers sont vérifiées par rapport à la table de règles, la règle la plus spécifique conforme aux valeurs 25 d'entrée 6 est déterminée et les valeurs de retour demandées de la rangée la plus spécifique déterminée de la table de règle sont retournées. Enfin, la figure 13 est une représentation schématique d'un système informatique 100 qui fournit la fonctionnalité de la base de données 1 avec au moins une table de base de données 2. 30 La base de données 1 peut comprendre un ensemble d'instructions pour amener le système informatique à exécuter toute méthode ou activité réalisée par la table de base de données 1 comme élaboré ci-dessus. Le système informatique 100 comprend un processeur 101, une mémoire principale 102 et un dispositif d'interface réseau 103 qui communiquent entre eux via un bus 104. Le processeur 101 comprend au moins un cache de CPU contenant au moins une 3047580 27 partie de l'index 10, comme indiqué à la figure 11 et à la figure 13. La mémoire principale 102 comprend la base de données 1 (c-à-d le logiciel exécuté mettant en oeuvre le système de base de données ainsi qu'une table de base de données 2 au moins) et, en option des parties de la table de base de données 2 sont aussi maintenues dans le cache de CPU du processeur 101. En 5 option, le système informatique 100 peut encore comprendre une mémoire statique 105 et une unité d'entraînement de disque 106. Un écran vidéo 107, un dispositif d'entrée alphanumérique 108 et un dispositif de commande de curseur 109 forment une interface homme-machine pour faire fonctionner le système informatique 100. Le dispositif d'interface réseau 103 est une interface avec et/ou sans fils qui connecte la base de données 1 à tout nombre et type de 10 dispositifs et applications client envoyant des demandes entrantes 9 à la base de données 1. Le client peut résider sur Internet et/ou tout autre réseau. Le dispositif d'interface réseau 103 utilise soit des protocoles de communication standards tels qu'une pile de protocoles I-ITTP/TCP/IP, IEEE 802.11 et/ou des protocoles de communication propriétaires. Un ensemble d'instruction (c-à-d logiciel) 100 incarnant tout ou toutes les méthodologies décrites ci-dessus, réside 15 entièrement ou au moins partiellement dans ou sur un support lisible par machine, par ex. la mémoire principale 102 et/ou le processeur 101 avec au moins un cache de CPU. Parmi d'autres, les instructions peuvent mettre en oeuvre les fonctions de la base de données 1 pour traiter les demandes entrantes 9, pour déterminer la rangée 3 la plus spécifique de la table de base de données 2 correspondant à une demande entrante 9, comme indiqué à la figure 6, ainsi 20 que la génération d'index de la figure 9. Un support lisible par machine sur lequel réside le logiciel 110 peut également être un support de données non volatile 111 (par ex. un disque dur magnétique non amovible ou un disque amovible optique ou magnétique) qui fait partie de l'unité d'entraînement de disque 106. Le logiciel 110 peut de plus être transmis ou reçu comme un signal 112 propagé via Internet à travers le dispositif d'interface réseau 103. 25 Bien que certains produits et méthodes construits conformément aux enseignements de l'invention ont été décrits dans ce document, la portée de couverture de ce brevet ne s'y limite pas. Au contraire, ce brevet couvre tous les modes de réalisation des enseignements de l'invention qui entrent dans la portée des revendications annexées soit littéralement, soit sous 30 la doctrine d'équivalents. REVENDICATIONS1. Un procédé de détermination de la rangée la plus spécifique dans une table de base de données maintenue par un système informatique, la table de base de données se compose d'une pluralité de rangées et d'une pluralité de colonnes, les rangées et les colonnes de la table de base de données forment des cellules, chaque cellule comprend au moins une valeur ou aucune valeur ; le système informatique maintient également un index pour la table de base de données ; chaque index comprend une structure d'index respective pour chaque colonne de la table de base de données ; chaque structure d'index comprend un ensemble respectif de tuples de pointeurs pour chaque valeur apparaissant dans la colonne respective et un bitmap dans lequel chaque tuple de pointeur comprend un premier pointeur indiquant une des valeurs qui apparaît dans la colonne et un second pointeur indiquant la rangée de la table de base de données dans laquelle la valeur apparaît, et où le bitmap indique des cellules dans la colonne respective sans valeur ; l'index indique un ordre de spécificité des rangées de la table de base de données ; le procédé comprend : - la réception par le système informatique d'une demande indiquant au moins une colonne de la table de base de données associée à une valeur d'entrée respective ; - incrémentiellement, pour chaque colonne, le système informatique : utilise le bitmap de la structure d'index pour que la colonne maintienne toutes les rangées de la table de base de données qui ne contiennent aucune valeur dans la cellule de la colonne considérée, et - utilise le tuple de pointeur de la structure d'index pour que la colonne filtre toutes les rangées de la table de base de données qui ne comprennent pas la valeur d'entrée respective, la sélection, par le système informatique, à partir des rangées restantes, de la rangée la plus en haut dans l'ordre de spécificité ; 3047580 29 - le fait de retourner, par le système informatique, la valeur d'au moins une cellule de la rangée déterminée. 2. Le procédé selon la revendication 1 comprend par ailleurs : 5 - en réponse à la réception de la requête, l'initialisation d'un bitmap résultat indiquant les rangées restantes ; dans laquelle l'utilisation des tuples de pointeur et du bitmap de la structure d'index pour chaque colonne indiquée dans la demande comprend : l'établissement d'un bitmap colonne indiquant toutes les rangées qui remplissent la valeur d'entrée respective pour la colonne respective, et la mise à jour du bitmap résultat en associant le bitmap résultat et le bitmap colonne. Le procédé selon la revendication 1 dans lequel l'ensemble respectif des tuples de pointeur est stocké de manière contiguë dans une mémoire du système informatique. Lea procédé selon l'une quelconque des revendications 1 à 3, dans leaquel l'utilisation des tuples de pointeur et du bitmap de la structure d'index pour chaque colonne indiquée dans la demande comprend par ailleurs la réalisation d'une recherche binaire sur l'ensemble respectif de tuples de pointeur. Le procédé selon l'une quelconque des revendications 2 à 4 dans lequel toutes les rangées qui remplissent la valeur d'entrée respective sont indiquées par un « 1 » dans le bitmap colonne, toutes les rangées restantes sont indiquées par « 1 » dans le bitmap résultat et l'association du bitmap résultat et du bitmap colonne comprend une opération ET bit à bit; Le procédé selon l'une quelconque des revendications 1 à 5 comprenant par ailleurs : - la génération de l'index par : - l'initialisation du bitmap indiquant toutes les cellules dans la colonne respective sans valeur, - l'ajout d'un tuple de pointeur à l'ensemble de tuples de pointeur de la structure d'index respective pour chaque valeur dans la colonne, 10 3. 15 4. 20 5. 25 6. 30 3047580 30 - la mise à jour du bitmap de la structure d'index respective pour refléter toutes les cellules sans valeur. 7. 5 8. 10 159. 10. 20 11. 25 30 12. Le procédé selon la revendication 6 dans lequel la génération d'index comprend par ailleurs : le tri des tuples de pointeur de chaque structure d'index par la valeur désignée par le premier pointeur. Le procédé selon l'une quelconque des revendications 1 à 7 dans lequel l'indication de l'ordre de spécificité des rangées de la table de base de données est réalisée en triant les rangées de la table de base de données en fonction du nombre de cellules dans chaque rangée sans valeur et/ou une spécificité des valeurs dans les cellules de la rangée. Le procédé selon la revendication 8 dans lequel l'indication de l'ordre de spécificité est donnée par un ordre de rangée unique indiquant les rangées triées. Le procédé selon l'une quelconque des revendications 1 à 7 dans lequel l'indication de la spécificité est donnée par des valeurs de pondération comprises dans l'index de la table de base de données. Le procédé d'une quelconque des revendications 1 à 10 dans lequel le système informatique est un routeur, la table de base de données est une table de routage, chaque rangée de la table de routage constitue une règle de routage pour acheminer une demande entrante vers une destination, la table de routage comprend une colonne de destination avec des valeurs de destination possibles et une colonne d'acheminement avec les valeurs correspondantes indiquant un acheminement vers la destination. Le procédé d'une quelconque des revendications 1 à 10 dans lequel le système informatique est un pare-feu, la table de base de données est une table de filtrage, la demande est un paquet de données entrant et chaque rangée de la table de filtrage constitue une règle de filtrage pour permettre ou empêcher le paquet de données entrant d'être transmis vers une destination, où la table de filtrage comprend au moins 3047580 31 une colonne de destination avec les adresses de destination possibles, au moins une colonne avec des valeurs précisant les caractéristiques du paquet de données entrant et une colonne avec des valeurs Booléennes indiquant si le paquet de données entrant doit être transmis ou rejeté. 5 13. Le procédé d'une quelconque des revendications 1 à 10 dans lequel le système informatique est un moteur de règles, la table de base de données est une table de règles, chaque rangée de la table règles constitue une règle pour répondre à la demande, les colonnes de la table de règles définissent les critères de règles. 10 14. Le procédé d'une quelconque des revendications 1 à 13 dans lequel l'index est stocké dans un cache de processeur du système informatique et reste stocké dans le cache de processeur après que la valeur d'au moins une cellule de la rangée déterminée ait été retournée pour être disponible pour d'autres demandes de traitement. 15 15. Un système informatique pour déterminer la rangée la plus spécifique dans une table de base de données maintenue par le système informatique, la table de base de données se compose d'une pluralité de rangées et une pluralité de colonnes, les rangées et les colonnes de la table de base de données 20 forment une cellule, chaque cellule comprend au moins une valeur ou aucune valeur ; le système informatique maintient également un index pour la table de base de données ; chaque index comprend une structure d'index respective pour chaque colonne de la table de base de données ; 25 chaque structure d'index comprend un tuple de pointeurs respectif pour chaque valeur apparaissant dans la colonne respective et un bitmap dans lequel chaque tuple de pointeur comprend un premier pointeur indiquant une des valeurs qui apparaît dans la colonne et un second pointeur indiquant la rangée de la table de base de données dans laquelle la valeur apparaît, et où le bitmap indique des cellules dans la 30 colonne respective sans valeur ; l'index indique un ordre de spécificité des rangées de la table de base de données ; le système informatique est configuré pour : - recevoir une demande indiquant au moins une colonne de la table de base de données associée à une valeur d'entrée respective ; 3047580 32 - incrémentiellement, pour chaque colonne indiquée dans la demande : - utiliser les tuples de pointeur de la structure d'index pour que la colonne filtre toutes les rangées de la table de base de données qui ne comprennent pas la valeur d'entrée respective, et 5 - utiliser le bitmap de la structure d'index pour que la colonne maintienne toutes les rangées de la table de base de données qui ne contiennent aucune valeur dans la cellule de la colonne considérée ; - sélectionner, à partir des rangées restantes, la rangée la plus en haut dans l'ordre de spécificité ; 10 - retourner la valeur d'au moins une cellule de la rangée déterminée. 16. Le système informatique selon la revendication 15 est agencé pour exécuter le procédé d'une quelconque des revendications 2 à 14. 15 17. Un programme d'ordinateur comprenant des instructions de code de programme pour l'exécution des étapes du procédé selon les revendications 1 à 14 lorsque ledit programme est exécuté sur un ordinateur.