MBOX-Line: From tss at iki.fi  Fri Nov  9 13:37:58 2012
To: imap-protocol@u.washington.edu
From: Timo Sirainen <tss@iki.fi>
Date: Fri Jun  8 12:34:49 2018
Subject: [Imap-protocol] Efficiently handling sequence numbers
In-Reply-To: <CABa8R6v2-NW2L4itj30juL6CEFUC3v9pQG0D0zvqM04UNiB+vA@mail.gmail.com>
References: <CABa8R6v2-NW2L4itj30juL6CEFUC3v9pQG0D0zvqM04UNiB+vA@mail.gmail.com>
Message-ID: <E121DCDC-75FA-43FB-87A7-EA0EEEEA13B0@iki.fi>

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.


