Dies ist ein B-Baum-Index, wie in fast allen Datenbanken, also hat er O(log n) Suchzeit.
Eine Suche mit regulären Ausdrücken klingt so, als müsste sie einen vollständigen Tabellenscan oder einen vollständigen Indexscan durchführen, die beide O (n) sind. Wenn der Ausdruck mit einem Präfix verankert ist, müsste er nur einen Bereich scannen, aber ich denke, das zählt immer noch als O(n).
