前文已經講述，字母全排列是個驚人的數字，即使只遍歷小寫字母和數字6個全排列也有36^6 = 2176782336，21億多個，7個排列36^7 = 78364164096，783億多，8個排列36^8 = 2821109907456，2.8萬億多個，數字非常驚人。Md5反查是個string-string的映射，16-N個字符的映射，如果考慮hex模式的md5那就是32-N的映射，考慮映射人們最先想到的可能都是數據庫存儲方式，我也首先想到了用數據庫存儲，分別考察了一下sqlite和berkeleydb，但測試下來制造數據的速度很慢，sqlite加索引大概只能到5w條記錄/s，不加索引為10w條/s，berkeleydb用單條模式大概只能到4.5w條/s，這個速度已經很慢了，更難于接受的是如果寫1000w對sqlite加索引來說不是耗時200s，而是2000s了，也就是說耗時隨單個數據文件記錄的條數增多幾乎成平方模式遞增，而不是簡單的線性遞增，這是很要命的，就算制造1億條數據耗時也是驚人，我的實測中沒有測試過用sqlite制造1000w條以上的數據，在我心目中已經否定了那種模式。雖然我知道很多號稱有多少億條數據的網站其實都是用的數據庫，我不知道他們花了多少時間制造數據，或者幾天，或者幾個月，或者更長時間，反正我對采用普通數據庫模式制造數據完全持否定態度，嵌入式速度太慢，其他數據庫則不光速度慢而且也不適合分布式應用，難道用戶每裝個點還要裝個mysql之類的數據庫，幾乎不可能啊。
下面說說我的方法，我本來第一版本是計劃先不做文件式數據庫的，第一版本來只規劃了做內存數據，充分榨取每一個字節，關于內存數據庫我實現了好幾個版本，下面分別介紹一下：
版本1：hash模式
用char key[16];做鍵，char pass[n];做內容，由于hash桶占用了一些字節：
DWORD h, nKeyLen; //hash鍵值, 字符串長度
DWORD tag; //私有值，默認為0提供給外部使用
bucket *pListNext; //hash表雙鏈的下一個節點
bucket *pListPrev; //hash表雙鏈的上一個節點
bucket *pNext; //拉鏈的下一個節點
VALUE second; //具體數據
_Elem first[0]; //first鍵
用這個hash模式大概存儲一個6個字符的串的md5信息花了50個字節，花費太多，結果自然存不了多少數據，該方案作為第一驗證方案，除了花費內存太多還是個能通過的方案。
版本2：hash簡化方案
在上述版本基礎上簡化桶設計，拋棄作為標準桶的一些字段，精簡之后如下:
DWORD h; //hash鍵值
bucket *pNext; //拉鏈的下一個節點
byte nKeyLen; //字符串長度
VALUE second; //具體數據
_Elem first[0]; //first鍵
該版本存儲一個6個字符的串的md5信息需要31個字節，比版本1少了很多，進步一些了。
方案1和方案2速度都很快。
版本3：vector方案
考慮到hash占用內存較多，采用vector方案，直接存儲
Char mm[16];
Char pass[n];
存儲一個6個字符的串的md5信息需要22個字節，該方案排序速度太慢，查找速度肯定也比不上版本1和版本2，之后還測試過將vector里面存儲指針，那種模式每個6個字符的串的md5信息占用內存26個，接近hash版本，排序速度比直接存儲數據的好一點，但也還是很慢，總之這個方案作為一個過度方案最終也被放棄了。
方案4：全文件Hash緊縮方案
以上這些方案的特點是都存儲了char mm[16]; 也就是說存儲部分都有計算出來的md5，經過思考之后覺得可以放棄存儲md5，不存儲md5是個很妙的想法，繼續發揮hash思想，也不保存根據md5計算出來的hash值本身，只將該md5和串的信息關聯到hash值的模所在的索引節點，這樣就將索引節點信息減少到極致：
size_t coffset; //content offset low
unsigned short a:12; //切分為12, 4
unsigned short b:4; //4，為下一個沖突值的索引序數，如果沒有就為0
size_t nextindex; //沖突條目的存儲序號，為0表示沒有沖突
使用該索引可讓單文件最多支持內容16T，最多687億記錄，具體實現的時候由于全使用文件所以速度比較慢，速度退化到sqlite之類同一級別了，不過這個設計思想為方案5提供了借鑒，如果跟方案5一樣用大塊內存輔助，速度大概可以上升一個級別，不過由于沒有具體實現，待研究之后再做評估。
方案5：hash緊縮內存方案
學習方案4的設計思想，考慮僅在內存里面實現一個緊湊型文件，由于只考慮內存可表示的32位范圍，所以簡化索引節點定義如下：
Size_t coffset; pass相對于內容區首的偏移
Size_t nindex; 沖突節點下一個序，如果為0則表示沒有沖突
內容區存儲更簡單，每個字符串直接保存，最后的0也保存，這樣每個字符串自然分開，對一個6個字符長的串來說，保存一個信息只需要15個字節，真的是省啊，1億個字符串也只要大約1.5g左右硬盤就夠了。此方案雖然很妙，但實現的時候卻費了一些周折，具體做的時候也做過好幾個版本，由于考慮該方案的內容和索引最后都可以直接保存到文件，所以該方案對位置的保存都用的是相對位置，也由于想讓索引節點信息簡單，最初是讓沖突索引采用線性步長跳躍方法，測試之后發現這個方法速度奇慢，而且還有個非常討厭的問題，隨著數據量的增多沖突擴散越來越厲害，耗時非線性的陡峭增長。放棄這個實現之后還是回到了經典的拉鏈法，拉鏈法速度就是快，但拉鏈法處理索引節點雖然容易，但要讓索引信息可直接保存卻要花一些腦子，最后采用先用內存擴展拉鏈，待全部索引構造好之后再把拉鏈出來的部分重新填到原始索引區中的空區，并修正對應索引相對位置。這個方法的精妙之處在于既省空間又有速度，最令人興奮的是采用該方法耗時隨著數據量的增大是線性增長，最后的實現在我的筆記本上大概100w/s，1億條記錄從字母組合到最終生成索引文件也只要不到2分鐘的時間，制造了一些數據之后統計了一下，沖突節點比例大概占26%-35%，也就是說有65%以上的數據只要一次hash就直接命中，平均拉鏈長度1.2左右，最長拉鏈10，總體還是很滿意的。
原本第一版沒有考慮這個可存儲的方案，但花了幾天就搞定了一個基本可用的存儲方案還是很令人興奮的，雖然該存儲方案還有一些問題沒有徹底解決，但已經有進一步處理的辦法，待下一個相對空閑時間段再仔細研究一下，定會有更簡潔的實現做出來，至于待解決的是什么問題以及如何解決那些問題還是等我代碼寫好了再寫出來吧。