Dette er et B-træindeks, som i næsten alle databaser, så det har O(log n) opslagstid.
En søgning i regulære udtryk lyder som om den skal udføre en fuld tabelscanning eller en fuld indeksscanning, som begge er O(n). Hvis udtrykket er præfiksforankret, skal det kun scanne et område, men det tæller vel stadig som O(n).