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转硬盘。