search

priitj / whitedb

WhiteDB memory database
http://whitedb.org/
GNU General Public License v3.0
608 stars 78 forks source link

Question: find first missing entry #44

Closed Hi-Angel closed 5 years ago

Hi-Angel commented 5 years ago

I've read docs, sources, but couldn't quite figure out how to do it.

For example, given a database has 6 one-field records with numbers: {10, 0, 1, 2, 27, 5}.

What can I use to find the smallest number that is not in database? E.g. in above that would be 3.

I imagine, some kind of iteration is needed, and I found that wg_query even has *_offset fields. But I didn't find any functional for that, and from inspecting in gdb I couldn't make sense from offsets either (I've seen end_offset being much smaller than curr_offset).

priitj commented 5 years ago

Hi,

if that number is in the same "column", as is the case with your one-field records, you can exploit the property that if there is an index on a column AND you make a query on that column then the results will come out sorted by that column (side effect of traversing the index).

This will be O(n) where n is the number of records so not terribly fast, but it helps that the values are sorted, so you can run a simple loop checking the values.

If you experiment with the index and the query you should see how the records are fetched.

Oh and offsets are actual memory offsets, they are not related to data values.

Hi-Angel commented 5 years ago

Thanks! Will try tomorrow.