21 lines
1.8 KiB
Plaintext
21 lines
1.8 KiB
Plaintext
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.
|
|
|
|
|