Search code examples
mysqltime-complexitycomparison-operators

Does MySQL maintain a time complexity of O(logn) when searching for a range of values?

Let's say I have a database schema that looks like

id | value

Where value1 is NOT unique but id is. If I want to select all values in the range 5 < value < 10 so that my query would look like

SELECT * FROM tablename WHERE value BETWEEN 5 AND 10

does the database maintain a selection time complexity of O(logn)?

Solution

  • According to @Paul Spiegel and this answer on SO that I missed during my search, the time complexity of O(logn) is maintained.