HashCrack程序數據及索引設計2
上個月寫了《HashCrack程序數據及索引設計》里面已經提到早期設計的幾種存儲方法，最后達到了每條記錄15個字節左右的水平，但這個存儲效果還是很差的，而且是單體文件，受制于內存限制，后來又設計了幾種復合索引格式，支持1萬億記錄一個復合索引，下面簡單講講之后的研究成果。
6、將內容區和索引區合并，索引位置不再提供指向內容區的size_t，內容區不再需要，直接在索引區，這樣索引區indexnode
Struct indexnode
{
Size_t nextoffset;
Char str[0];
};
經過此修改之后稍微不好的地方就是如果一個文件里面要管理不同長度的字符串那么只能取最長的字符串長度，以便indexnode保持相同大小容易索引。
這種方法雖然效果不錯，但平均下來一個字符串還是要占用11個左右的字節，而且不同長度的字符串有一些浪費的地方。
7、以上的存儲方法雖然已經比較緊湊，但還不是最緊湊的方法，如果不保存字符串只是保存字符串在序列中的位置，那么不同字符串也沒有長度不同，也可以用同樣的大小去保存，如果一個db保存42億以下的字符串，那么只要4個字節就可以了，如果一個db保存1萬億以下的數據，那么只要5個字節就可以，這真是個非常有創意的想法，其實我當初想到這個想法的時候很擔心計算效率，遲遲沒有動手代碼，但思考了幾天之后打消了我對效率的擔心，相反，只保存一個position比復制N個字符串可能還要快一點，這樣我們就只要9個字節描述indexnode了，看定義：
Struct indexnode
{
Size_t lpos;
Byte hpos;
Size_t nextoffset;
};
精確到9個字節表示一條記錄，很不錯，也沒有更多的限制。事實上9字節版本的速度比方法6的確是要快一點，還沒優化的時候就比6方法要快一些了，當然查詢的時候由于要多計算一些信息，理論上是要慢一點的，但由于都是內存計算，其實影響不是很大。
8、上述9個字節的方法雖然已經很緊湊，但如果給nextoffset做一點限制，讓一個區段的數據為1667w以下，那么描述nextoffset 只需要3個字節即可，這樣indexnode總的長度就只需要8個字節，這真是很好的想法，我為這個想法驕傲，看下indexnode的8字節版本
Struct indexnode
{
Size_t lpos;
Size_t hpos:8;
Size_t nextoffset:24;
};
精確的8字節indexnode，如此我們最終實現了最緊湊的md5數據庫，每條記錄8個字節，幾乎無法再減少了，期待哪天突然靈光閃現再創造出更緊湊的存儲方法吧，呵呵，這個實現其實已經超越了我最初的估計了，我以為能減少到12個字節已經到頂了，沒想到還能減少到8個字節。
8字節的版本最初寫出來的時候效率下降得很厲害，因為以前nextoffset當指針用，現在3個字節無法當指針，只能轉換，多一個轉換函數效率下降了一些，其他地方剛寫的時候也是非優化算法，所以第一個8字節版本效率比9字節降低了一半以上，但花了一個早上優化之后效率又上去了，現在制造復合索引只需要82秒就可完成1億條記錄，速度比方法6快不少，方法6需要120秒左右。
或許我講得比較簡單，如果不是深入研究這一塊的人或許看不明白，但精華我基本上講出來了，實現上其實有很多技巧，如果要做到象我一樣的速度其實是需要很深功力的，我測試用的機器是朋友的入門級服務器E5504 2.0cpu，4G內存，普通7200轉硬盤。