couchdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Antony Blakey <>
Subject Re: Bulk Docs
Date Mon, 16 Mar 2009 06:25:41 GMT

On 16/03/2009, at 11:50 AM, Antony Blakey wrote:

> 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).

As I remember more about this ... by using 01 = left, 10 =  
termination, 11 = right, the length of the bit string becomes implicit  
i.e. every pair contains a 1, and thus a function to compute an  
intermediate value given two *byte* sequences is easy. In practice you  
need two adjacent values in order to avoid collisions.

Antony Blakey
CTO, Linkuistics Pty Ltd
Ph: 0438 840 787

Every task involves constraint,
Solve the thing without complaint;
There are magic links and chains
Forged to loose our rigid brains.
Structures, structures, though they bind,
Strangely liberate the mind.
   -- James Fallen

View raw message