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.