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
