[Imap-protocol] Efficiently handling sequence numbers

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).

You can store the uids for a folder on disk in sorted order, but because
every connection has its own "view" of that data, and the view itself is
only allowed to change for a connection at specific points, it seems like
the connection needs a copy of that uidlist.

Now, its possible you can maintain an in-memory "diff" between the view and
the actual state.  Or maybe you're using a data store where you can
maintain access to the view based on timestamp.  And then you also keep a
log of changes so you know what to send to the client at a sync checkpoint.
 Even then, there aren't many efficient ways to answer the question of
"give me the 500th entry in that table".  If you store the table as fixed
size records, sure, but then you have to rewrite the whole table, or use
some sort of fixed blocks so you can update only from change to end, but I
don't see what data storage you're using to do that and keep multiple
versions.  Plus, this is starting to sound like using some serious data
storage beyond what I usually see in software like this.

So, what do people use?  IMAP allows 4B messages per folder, right?  Even
in a fairly compact format, that's a lot of data to be either re-writing
constantly or loading completely and caching in memory.

I guess an on-disk b+ tree could be modified to keep counts of each
sub-tree in a node, and then you'd just need to re-write all the nodes up
the list,  is that a widely supported feature of such data structures?

Or am I missing something else obvious?

Brandon

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