On 16/03/2009, at 10:30 AM, Antony Blakey wrote:
I've user that technique in the past. The problem is that after a
while you end up rounding off due to limited precision, and the user
is left wondering why they can't change the order of their items.
And you can't just renumber because that's begging the question.
An alternative is to use ascii strings and rely on the fact that a <
am < b, which allows infinite subdivision, although the problem then
is that string length is unbounded, and then you need to consider
the lifetime of the data and the insertion statistics, so it's not
suitable for all ordering problems.
BTW, we did this to reduce the number of item needing to be touched
when re-ordering pages in a CMS.
IIRC the general solution is to treat (in abstract) the ordering of
items as the in-order traversal of a binary tree. The brief form of
the algorithm is to record in each item the path from the top e.g. 01
or 10 = termination, 00 = left, 11 = right. You then map that bit
sequence, padded with 0, to an ascii form that preserves the ordering.
Avoid unbounded lengths requires a balanced tree, which requires
transactional support. It has the benefit of a low number of documents
touched per update (in an amortized sense).
Antony Blakey
--------------------------
CTO, Linkuistics Pty Ltd
Ph: 0438 840 787
It is as useless to argue with those who have renounced the use of
reason as to administer medication to the dead.
-- Thomas Jefferson
