यह लगभग सभी डेटाबेस की तरह एक बी-ट्री इंडेक्स है, इसलिए इसमें ओ (लॉग एन) लुकअप टाइम है।
एक नियमित अभिव्यक्ति खोज ऐसा लगता है जैसे इसे एक पूर्ण तालिका स्कैन या एक पूर्ण अनुक्रमणिका स्कैन करने की आवश्यकता है, जिनमें से दोनों ओ (एन) हैं। यदि एक्सप्रेशन प्रीफ़िक्स-एंकर है, तो उसे केवल एक रेंज स्कैन करने की आवश्यकता होगी, लेकिन मुझे लगता है कि यह अभी भी O(n) के रूप में गिना जाता है।