> On Oct 15, 2016, at 7:42 AM, Luca Olivetti <l...@wetron.es> wrote:
> Instead of an autoincrement you could increment it manually in, say, 1000 
> increments.
> Then, when you have to insert something between 1000 and 2000 you just use 
> 1500.

Unfortunately this breaks down after log2(1000) ≈ 10 insertions, when you may 
have to insert in between two consecutive IDs like 1324 and 1325. “Fine, then 
I’ll go to floating point.” Unfortunately that only gives you a finite number 
more bits … a dozen or two more insertions before you run out of room in more 
insidious ways due to floating-point roundoff error.

A much better way to create an ordered sequence you can always insert into, is 
to use strings. As a simplified example, initially assign the IDs “A”, “B”, 
“C”, “D”… Then when you need to insert between “C” and “D”, use “CM”. Between 
“C” and “CM” is “CF”. Eventually you may have to insert between “CD” and “CE” … 
use “CDM”. It’s pretty clear that this can go on ‘forever’.

(This works best when you have a finite space you need to subdivide, which 
isn’t true here. So “What comes after “Z”? Well, “ZM”. Obviously this example 
scheme is not optimized for frequent appending to the end! It’s really the same 
problem that comes up with search trees, since this is equivalent to a 26-way 
tree where the nodes are expressed as paths from the root.)

sqlite-users mailing list

Reply via email to