电子邮件程序/服务器如何存储和检索邮件？

Question

Eudora和GMail的速度，例如查看数千封电子邮件和找到正确的邮件令我惊叹不已。我使用Eudora，搜索在几秒钟内通过十年的电子邮件运行得非常快。

所以我的问题是，他们如何存储和检索消息？什么数据结构来存储数据，索引，什么算法？消息如何存储在磁盘/数据库上？

Answer 1

如果搜索速度很慢，我会感到惊讶。假设您有n = 10000封电子邮件，每封邮件m = 1000个字符。任何体面的子串检测算法都会给你O（n * m）的速度。对于提供的n和m值，它在现代PC上不到一秒钟。

谈到存储，我知道的客户端将所有电子邮件放在一个大文件中，每个客户端使用自己的格式。这使您可以快速读取磁盘中的所有消息。

如果你有兴趣，这是一个经典的子串搜索算法（也就是更多）：
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

编辑
我不是说任何电子邮件应用程序使用简单的字符串搜索，只是使用它已经足够快了。

Answer 2

尽管采用了完全不同的技术，但它们都使用相同的秘密酱油：索引。

Eudora对每个邮箱和文件夹使用mbox格式，这个邮箱和文件夹基本上是一个大文件，包含所有邮件。如果您检查这些文件，您会看到一个具有相同名称和扩展名的小文件.IDX或somthing。这是一个索引，可以快速查看单个电子邮件的起始位置。 Eudora的另一个明智之举是从邮件中删除附件，通过大小的命令减少邮箱的大小，加快了处理过程中的管理。这导致Eudora能够管理比大多数其他客户端更多邮件的邮箱。

Google是索引的主人，他们几十年来一直在索引完整的网页，所以他们将他们的交易应用到您的邮箱，因为所有相关的事实都是单独索引的，所以他们可以快速访问邮件。他们也有特殊的技术来快速检索电子邮件等文件。