4 ms·
Here's as simple as an explanation as I could come up with in 30 seconds: An index is a supplemental data structure that provides O(searchable) access time to
by joshka 9y ago
Here's as simple as an explanation as I could come up with in 30 seconds:
An index is a supplemental data structure that provides O(searchable) access time to another data structure that would has O(scannable) access time given particular search or filter parameters.
Everything beyond that is implementation detail.
- kapauldo 9y agoNot O(log(searchable))?
- joshka 9y agoThis depends on your index function, and what operation you're optimizing for. My notation here was a shortcut for <insert explanation of differences to searching / filtering / sorting / etc. algorithm time complexity> where O(search) < O(scan), but by how much is implementation specific.