Continuing some themes in this question, I would like to know if I could get a performance of O(log n) on the size of the table from somes sqlite queries.
The first would get the mth element of a table ordered by weight:
select id, weight from items order by weight limit 1 offset m
The second would do the opposite, get mth position of an elment of a given weight:
select count(id) from items where weight > x
'items' would be indexed by weight and id if necessary. Weight and id are unique but not necessarily distributed uniformly. m and x are arbitrary. O(log ) might seem extreme but it is what one could get from a correctly hacked b-tree and I would like to avoid rolling my own.
If this wouldn't work, are there any in-memory databases or key-value databases that could do this?
Actually, I think that this is answered here and here - of course SQLite will perform faster than standard databases and if they do O(log n) here, so should it.