Reusing deleted entries ?

[Liviu Carausu]

Hi,
My "create" method from the DB interface looks like this :

   /**
     * Creates a new record in the database ([B]possibly reusing a deleted entry).[/B]
     * Inserts the given data, and returns the record number of the new record.
     *
     * @param data
     *            String array containing record fields.
     * @return new allocated record number.
     * @throws DuplicateKeyException
     */
    public int create(String[] data) throws DuplicateKeyException; 

How are you guys keeping track of deleted records ? I have a collection where I hold the indexes of the deleted indexes. I update the collection
at server start and when one element is deleted. Reading the collection is useful also in the "read" method, it can save reading from the disk the "delete flag"
Any other approaches, ideas ?
Thanks,
Liviu

[Jim Petersson]

I'm just reading the database file directly, checking for a deleted record.
The drawback of this is of course that it's pretty slow, but on the other hand there is no need to maintain a separate list of deleted records.

[Liviu Carausu]

Originally posted by Jim Petersson:
I'm just reading the database file directly, checking for a deleted record.
The drawback of this is of course that it's pretty slow, but on the other hand there is no need to maintain a separate list of deleted records.

OK,Jim, but then how do you find the next free index when you are trying to create a new record ? I think that going through all db file to search for the first deleted index is pretty slow.

Thanks,
Liviu

[rinke hoekstra]

I'm just not reusing deleted records. All records are appended.

[Liviu Carausu]

Originally posted by rinke hoekstra:
I'm just not reusing deleted records. All records are appended.

Hi Rinke,

That means that you are either ignoring the requirement "possibly reusing a deleted entry" (You are right, it is not a "must" ), or you are compacting somehow the database at startup . Am I right ?

Thanks,
Liviu

[Jim Petersson]

Originally posted by Liviu Carausu:


OK,Jim, but then how do you find the next free index when you are trying to create a new record ? I think that going through all db file to search for the first deleted index is pretty slow.

Thanks,
Liviu

I'm going through the whole db-file, searching for the first deleted record.
And yes, it's slow

[rinke hoekstra]

Originally posted by Liviu Carausu:

That means that you are either ignoring the requirement "possibly reusing a deleted entry" (You are right, it is not a "must" ), or you are compacting somehow the database at startup . Am I right ?

Yes, I am ignoring this.

I found that it makes the code quite a bit more complicated, and file size is normally not a problem on modern computers, especially not with this database type.

There is also a requirement to keep the code as simple and understandable as reasonably possible, and I chose to give more importance to this requirement then to the "possibly reusing deleted records" requirements.

[Jo�o Batista]

I second what rinke said.
Though my code favors a bit of complexity regarding a more flexible solution at some points, I did not have enough arguments to go to the trouble of reusing deleted records, and kept my create method clean. It might be useful in other application that uses the file with deleted records (odd reason, but a possibility).

[Joshua Fix]

I rebuild my index with each add or delete opertaion. Whenever a delete operation is performed, I add the Long byte position value to a LinkedList.

When I add a new reocrd, I check to see if my queue is empty. If it is, I append my new record. If it isn't, I poll() it and seek to that long value and write my new record there.

Then I re-index.