couchdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Brian Candler <B.Cand...@pobox.com>
Subject Re: CouchDB book: Ordering Lists
Date Fri, 18 Dec 2009 13:37:48 GMT
On Tue, Dec 15, 2009 at 11:11:52AM +0100, Kosta Welke wrote: To insert in a
> list, insert in the middle of the existing 'boundaries'. For inserting
> items at the beginning or end, the boundaries are "a".charCodeAt(0)-1
> (which is "`") and "z".CharCodeAt(0)+1 (which is "{"). If you want, you
> can extend that to more printable characters or even unprintable ones.

Be aware that CouchDB doesn't collate in ASCII order, but uses the Unicode
Collation Algorithm, unless told otherwise.
http://wiki.apache.org/couchdb/View_collation

> What do you think? It's a little more complicated than calculating the
> average of two floats, but the complicatedness stems from fixing the issue
> of limited precision.
...
> Of course, other ways of achieving something similar is to use an array of
> integers (best would be int32 so that JavaScript can handle).

That's what I was going to suggest. JavaScript uses double-precision floats,
so you'll get 47 or 48 bits of integer precision (I'm not sure exactly).

Of course, you could just make a binary tree (represented as a hex string
perhaps). In the worst case, after N insertions, your key will be N bits
long.

But I think the worst case is the same for the others too: e.g. using an
array of 32-bit integers, after N insertions your key could be N/32 integers
long.

Mime
View raw message