Most efficient way of getting the next unused id

Question

(related to Finding the lowest unused unique id in a list and Getting unused unique values on a SQL table)

Suppose I have a table containing on id column and some others (they don't make any difference here):

+-----+-----+
| id  |other|
+-----+-----+

The id has numerical increasing value. My goal is to get the lowest unused id and creating that row. So of course for the first time I run it will return 0 and the the row of this row would have been created. After a few executions it will look like this:

+-----+-----+
| id  |other|
+-----+-----+
|  0  | ... |
|  1  | ... |
|  2  | ... |
|  3  | ... |
|  4  | ... |
+-----+-----+

Fairly often some of these rows might get deleted. Let's assume the rows with the id's of 1 and 3 are removed. No the table will look like this:

+-----+-----+
| id  |other|
+-----+-----+
|  0  | ... |
|  2  | ... |
|  4  | ... |
+-----+-----+

If I now run again the query it would like to get back the id 1 and this row should be created:

| id  |other|
+-----+-----+
|  0  | ... |
|  1  | ... |
|  2  | ... |
|  4  | ... |
+-----+-----+

The next times the query runs it should return the id's 3, 5, 6, etc.

What's the most effective way to run those kinds of query as I need to execute them fairly often in a second (it is fair to assume that the the id's are the only purpose of the table)? Is it possible to get the next unused row with one query? Or is it easier and faster by introducing another table which keeps track of the unused id's?

If it is significantly faster it is also possible to get a way to reuse any hole in the table provided that all numbers get reused at some time.

Bonus question: I plan to use SQLite for this kind of storing information as I don't need a database except for storing these id's. Is there any other free (as in speech) server which can do this job significantly faster?

Answer 1

I think I'd create a trigger on delete, and insert the old.id in a separate table. Then you can select min(id) from that table to get the lowest id.

disclaimer: i don't know what database engine you use, so i don't know if triggers are available to you.

Answer 2

Like Dennis Haarbrink said; a trigger on delete and another on insert :

The trigger on delete would take the deleted id and insert it in a id pool table (only one column id)

The trigger on before insert would check if an id value is provided, otherwise it just query the id pool table (ex: SELECT MIN(id) FROM id_pool_table) and assign it (i.g. deletes it from the id_pool_table)