Re: [Imap-protocol] Efficiently handling sequence numbers

On Fri, Nov 9, 2012 at 1:37 PM, Timo Sirainen <[email protected]> wrote:

> On 9.11.2012, at 23.15, Brandon Long wrote:
>
> > I'm drawing a blank on how to efficiently handle sequence numbers
> without O(n) operations (where n is the number of messages in a folder).
>
> I don't think it's a real concern. A long time ago I wrote some kind of a
> binary tree based algorithm to do expunges in O(log n), but eventually I
> just realized it's way too much trouble (and I'm pretty sure it had some
> O(n) operations hidden in there at some intervals). Small fixed size
> records (especially a simple uids[] array) works just fine for probably up
> to tens of millions of mails, and just about no one has that many mails in
> one mailbox.
>
> Dovecot nowadays doesn't rewrite the whole index to disk every time you
> delete a mail. It appends "uid 123 expunged" to a log file and updates the
> index in memory (memmove()ing data around). Then once in a while it
> recreates the index. Works nicely. I've wondered about making this two
> arrays though, so that you'd have the uids[] array and other_fixed_data[]
> array and expunge would only need to move data in the uids[] array, but I
> don't know if that really is a good idea. Probably not.
>
> Also large mailboxes could be split to "old mails" and "new mails"
> indexes. If you have a huge mailbox, it's very unlikely that any old
> messages get expunged. Then you only need to append to the old index and
> rewrite the small new index.
>
> So, do you load the full sequence into memory on SELECT?

Brandon

_______________________________________________
Imap-protocol mailing list
[email protected]
http://mailman2.u.washington.edu/mailman/listinfo/imap-protocol