How to find the first free ID in the database?

Question

PHP

Good afternoon.
In a DB there is a table in which 2 fields
user_id (autoincrement)
full_name
In the table some millions of records. Data is periodically deleted and added.
At the moment, the task is to, when creating a new user, if possible, give him an id not by auto-increment, but first check for possibly free id.
That is, when creating a user, if there is a free id, for example 325, then give it to him.
The question is how to implement a search for such an ID with a minimum load, since there are several million records in the table.
Common sense tells me that taking and sorting through several million records is, to put it mildly, not an option.
Interested in an elegant solution, at the moment I settled on the following options

• Create a separate table in which I will store free IDs
  
• Perform SQL searches with a medium-strength query
  

Request like this

SELECT MIN( uid +1 ) 
FROM  `users `
WHERE uid +1 NOT 
IN (

SELECT uid
FROM  `users`
)

The catch is that 100 or 200 users can work with the system at the same time, and I mean from the point of view of SQL, this can also be expensive.
Bottom line, is the golden mean an additional table with free IDs?

Answer 1

> Create a separate table in which I will store free IDs
is the best option.

Answer 2

you don't need it... Well, don't pay attention to the value of the auto-increment field, forget about it...

Answer 3

They speak correctly. After the Insert request, you can get the assigned ID and operate it as you like. Do not clog the code with unnecessary operations. Most of this has already been done.
php.net/manual/ru/mysqli.insert-id.php