Questo è un indice B-tree, come in quasi tutti i database, quindi ha un tempo di ricerca O(log n).
Una ricerca di espressioni regolari sembra che debba eseguire una scansione completa della tabella o una scansione completa dell'indice, entrambe O(n). Se l'espressione è ancorata al prefisso, dovrebbe scansionare solo un intervallo, ma suppongo che conti ancora come O(n).
