Este es un índice de árbol B, como en casi todas las bases de datos, por lo que tiene un tiempo de búsqueda O(log n).
Una búsqueda de expresión regular suena como si necesitara hacer un escaneo de tabla completo o un escaneo de índice completo, los cuales son O(n). Si la expresión está anclada a un prefijo, necesitaría escanear solo un rango, pero supongo que aún cuenta como O(n).
