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