On Mon, 2003-03-10 at 20:14, Joseph S Barrera III wrote: > Cyrus Daboo wrote: > > | Am I making this too complicated? Surely every imap implementor > > | has faced this issue. Do people live with O(n) deletes, or > > | am I missing something?
Most do. > > Either use a Hashtable with UID as the key and sequence number as the > > value, or do a binary search on the seq->UID vector to lookup sequence > > number given a UID (you can do that given that UIDs will always appear > > in ascending order in the vector). You'll have to figure out which is > > more efficient. Hashtable for UID lookups is a bad choice. Eg. with UID FETCH 100:200 you may have only a few of the UIDs in that range. > Sorry I didn't make it clear before that I meant set-flag-delete + > expunge. Expunges occur frequently in our environment. Maybe that's > why no one runs into this issue, namely that they assume that > expunges are infrequent. I don't think it's that slow to renumber them after expunges if you can do it in memory. My server keeps indexes in disk, so I use the kind of b-tree you described. It's C and LGPL, so go ahead and see if it helps. http://dovecot.procontrol.fi/, src/lib-index/mail-tree*. That could probably still be done faster, at least building the tree first time feels too slow.
