As Mark pointed out in his reply to me, the addition of a single messageI would strongly urge server implementers to look beyond merely caching references headers, and to come up with smart caching of the actual thread tree structure itself.
to the store can completely invalidate such a cache;
Yes, addition is tricky. You could probably optimize it if you kept the base subjects and message IDs stored permanently in a hash/btree, but keeping them up to date requires more work and may not be worth it.
You should be able to optimize some expunges more easily. Message without children can just be removed. Message with parent and children requires rebuilding that one thread, assuming base subject hasn't changed. Exception to these would be if expunged message had it's message-id duplicated elsewhere, if that was the case you'd probably have to rebuild the whole tree again.
Is the above worth the trouble? I don't know, I doubt I'll try it for a while.
for many message
stores, I suspect that the process of detecting the messages that have
been added to a mailbox since the cache was created is probably an
NlogN problem as well, and that's leaving aside the logistical issues of
dealing with the situation where a non-IMAP client manipulates the
message store between sessions.
I don't think external clients are a problem. There's no difference between them adding a message or MTA adding a message. There's hardly a difference between noticing external expunges and doing the expunging ourself.
