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
