couchdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Antony Blakey <antony.bla...@gmail.com>
Subject Re: Bulk Docs
Date Mon, 16 Mar 2009 01:20:19 GMT

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



Mime
View raw message