Il s'agit d'un index B-tree, comme dans presque toutes les bases de données, il a donc un temps de recherche O (log n).
Une recherche d'expression régulière semble devoir effectuer une analyse complète de la table ou une analyse complète de l'index, les deux étant O(n). Si l'expression est ancrée dans un préfixe, elle n'aurait besoin d'analyser qu'une plage, mais je suppose que cela compte toujours comme O(n).
