Which language are you using? Andres ideas could give some nice solutions using blob, even without a specific arbitrary precision library. eg: Splitting data with an encoding like (In-order id) (Out-of-order id)
In-order insert are encoded with an encoding that guarantees lexicografical ordering (eg just writing a 64bit big endian or using sqlite 4 varint encoding http://sqlite.org/src4/doc/trunk/www/varint.wiki) with an empty out of order id. Out of order inserts are calculated with an algorithm like this (python encoding): def newId(prev, next): ret=[] for i in range(max(len(prev),len(next))+1): p=prev[i] if i<len(prev) else 0 n=next[i] if i<len(next) else 0x100 c=(p+n)/2 ret.append(c) if c!=p: return ret Achilles's test: def printArray(a): print " ".join(map(lambda x:"%02x"%(x,),a)) p=[0,] n=[1,] for i in range(0,40): p=newId(p,n) printArray(p) Test result: 00 80 00 c0 00 e0 00 f0 00 f8 00 fc 00 fe 00 ff 00 ff 80 00 ff c0 00 ff e0 00 ff f0 00 ff f8 00 ff fc 00 ff fe 00 ff ff 00 ff ff 80 00 ff ff c0 00 ff ff e0 00 ff ff f0 00 ff ff f8 00 ff ff fc 00 ff ff fe 00 ff ff ff 00 ff ff ff 80 00 ff ff ff c0 00 ff ff ff e0 00 ff ff ff f0 00 ff ff ff f8 00 ff ff ff fc 00 ff ff ff fe 00 ff ff ff ff 00 ff ff ff ff 80 00 ff ff ff ff c0 00 ff ff ff ff e0 00 ff ff ff ff f0 00 ff ff ff ff f8 00 ff ff ff ff fc 00 ff ff ff ff fe 00 ff ff ff ff ff 2014-09-24 20:51 GMT+02:00 RSmith <rsm...@rsweb.co.za>: > Thanks all for the responses. > > Thanks Scott for the calcs, I had somehow imagined using a set of values > might yield more iterations, but of course that is just wishful thinking, > the bits are the bits. > > The idea from Alessandro is great if I could control or guess where the > next inserts will be, but of course I don't know and if they happen to be > consecutively at the same position, then I will run out of Integer > intervals at the the same speed as when using a float, save a few bits. > > Clemens I'm liking the link list but did not go with it due to an > expensive insert function - of course if I knew at the start the division > thing would bite me this decision may have been different. > > But, say I'm changing things to work with the link list... how would I get > a normal SQL query ORDER BY clause to use that? > > I was thinking in stead of maybe having a prev and next column, to just > have a next column which points to an ID. Inserting a value between rows 1 > and 2 in the next example will mean 2 operations only, inserting a new > value with it's "next" value pointing to row 2 and then changing row 1 to > have the new ID as it's "Next", repeating that idea twice will work like > this: > > ID | Next | Data > 1 | 2 | 'First Row' > 2 | 3 | 'Eventual Fourth Row' > 3 | 1 | 'Last Row' > > After Insert we have: > > ID | Next | Data > 1 | 4 | 'First Row' > 2 | 3 | 'Eventual Fourth Row' > 3 | 1 | 'Last Row' > 4 | 5 | 'New Second Row' > 5 | 2 | 'New Third Row' > > Possibly "Last Row" should really have Max_Int as it's Next maybe... or > just NULL. Needs more thinking. > I'm still confused as to how to get the ORDER BY to follow the trend.... > > I'd have to have an Index on "Next" (which is fine) and then join the > table to itself linking where "Next"="ID" kind of thing and use that as the > ordering - not hard but will have to see how expensive it is. > > Either way, thanks for the help! > > > > > > On 2014/09/24 20:15, Clemens Ladisch wrote: > >> RSmith wrote: >> >>> I have one program that inserts values to a table and determine sort >>> order using one standard trick that has a REAL column named >>> "SortOrder" [...] >>> reassign SortOrders simply in Integer steps: 1, 2, 3 etc. >>> >>> ID | SortOrder | Data >>> 1 | 1 | 'First Row' >>> 2 | 4 | 'Eventual Fourth Row' >>> 3 | 5 | 'Last Row' >>> 4 | 2 | 'New Second Row' >>> 5 | 3 | 'New Third Row' >>> >> When we think of this not as a relational table but as a data structure >> in memory, this is the equivalent of an array, where SortOrder is the >> array index. Inserting or deleting of an entry requires moving all >> following entries. >> >> However, an array would not be the most efficient data structure for >> this application, because random access to the n-th entry is not needed, >> and the order of one entry is only relative to the adjacent entries. >> A better data structure would be a linked list. >> >> As a table, a linked list would be modelled as follows: >> >> ID | Prev | Next | Data >> 1 | | 4 | 'First Row' >> 2 | 5 | 3 | 'Eventual Fourth Row' >> 3 | 2 | | 'Last Row' >> 4 | 1 | 5 | 'New Second Row' >> 5 | 4 | 2 | 'New Third Row' >> >> This makes insertion easier, and should not need more space than >> a floating-point SortOrder (because the prev/next pointers are >> integers), but now reading the list in order requires a recursive CTE. >> >> Well, I'm not sure if this is more clever than useful ... >> >> >> Regards, >> Clemens >> _______________________________________________ >> sqlite-users mailing list >> sqlite-users@sqlite.org >> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users >> > > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
