電子郵件程序/服務器如何存儲和檢索郵件？

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是索引的主人，他們幾十年來一直在索引完整的網頁，所以他們將他們的交易應用到您的郵箱，因爲所有相關的事實都是單獨索引的，所以他們可以快速訪問郵件。他們也有特殊的技術來快速檢索電子郵件等文件。