I'm working on making an in-house imap server perform better for large folders with many thousands of messages. The first thing I want to address is the poor choice of data structure to represent the sequence-id to uid (or message primary key) mapping. Right now it is kept as an array which has O(n) performance for deletes. I assume I need to move to a tree-like structure, with some efficient O(log n) way of mapping indices to nodes.
I hope I'm mistaken, but I don't see anything in java.util (yes, the server is written in Java) that handles the index requirement. In particular, TreeMap doesn't contain a method for get-Nth-node. I know I can write my own Tree data structure to do this, where each node keeps track of the number of nodes beneath it, thereby allowing a log(n) search for the nth node, but I don't see anything off the shelf, for Java, with a friendly license (e.g. GNU or public domain). If there's something out there with a friendly license for C or C++, I can rewrite it in Java as necessary.
Am I making this too complicated? Surely every imap implementor has faced this issue. Do people live with O(n) deletes, or am I missing something?
Thanks all,
- Joe
--
-----------------------------------------------------------------
For information about this mailing list, and its archives, see: http://www.washington.edu/imap/imap-list.html
-----------------------------------------------------------------
