mdrill存储的一个想法（改进思路）

[muyannian]

mdrill在计算过程中，实际上不会操作数据的真实值，而是值的代号。这个代号实际上是将一个列的每一个值进行排重后按照从小到大的顺序进行编号，通常来说我们标记为t1,t2,t3,t4…….tn。 每次查询mdrill会先根据用户的过滤条件，根据倒排索引筛选出符合条件的记录id列表，我们称为doclist，然后根据文档的id得到值的代号，进行后续的计算。 如何快速的根据文档的id得到值的代号，对mdrill的性能影响非常大。

现在是这样搞的

1. 在倒排索引里存储着值的编号对应的docid列表（我们称为doclist）,示例如下 t1=>d1,d2,d4 t2=>d3,d5,d6 t3=>d7,d8 tn=>dh,di,dj,dm,dn
2. 查询的时候，扫描这段存储，在内存中建立d与t的对应关系（数组）
3. 优缺点分析 优点，每个列的值多多少少都会有重复值，这样值的代号仅存储一份，另外doclist采用的是差值存储，可以采用很多种压缩算法。 缺点：扫描的IO依然给文档的数量成正比，也就是有多少个文档，就要读取多少个int的值，还是线性的关系，10台机器，扫描个10亿，大约需要20秒左右。 新的思路(近似扫描+少量的docid进行准确性校验)
4. 采用近似的bitset+校验的方式来节省存储 存储结构如下

t1,t2,t3,t4,t5=>bitset(crc) t6,t7,t8,t9,t10,t11=> bitset(crc) t12,t13,t14,t15,t16,t17=> bitset(crc) ……

2. bitset(crc)中存储的值为 对{ t&d }组合后取的crc32的值存储到bitset中，具体多少个t存储到一个bitset中跟根据bitset的误差碰撞而决定的，我们可以设定一个阈值，碰撞率达到一定的百分比后则认为应该更换bitset了。
3. bitset(doclist)中存储的值为这些t对应的d的列表，
4. 查询的时候，则扫描这些bitset然后根据给定的doclist与t进行匹配，从而匹配出d与t的对应关系。
5. 优缺点 优点：文件io大幅度的减少。 缺点：因为bitset存在值的碰撞，存在误差，所以需要进行二次校验。 因为存在碰撞，所以有可能得出一个d对应多个t的情况,所以如何准确的校验则为难点，但是由于可以利用多种粒度的bitset 比如说在来个doclist，来降低误差。 然后针对存在误差的docid在读取文件进行校验。

[muyannian]

测试了下 不靠谱