How interesting. I would have thought such a common database operation (querying by ranges) would have been a better solved problem by now.
Also, how come the author of the blog post writes O(k) instead of O(1) for constant time? Is it because 1 is as arbitrary a constant as any or is there some difference that I am not aware of?
Link to the original paper [1]