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