实现了一个基于哈希的二进制数据文件索引结构及数据读取接口。
- 数据在文件中按照(key_size, key, value_size, value)无序排列;
- key_size,value_size字段均为两字节;
- 目标机器CPU按照big endian方式存放数据;
- 文件slice大小为2GB,且每个文件slice均以一个完整的tuple开头,即不存在跨slice的数据。
- IndexBuilder类用于创建索引,采用hashlib库提供的black2b函数,将键值均匀分布在0到2^32之间;
- 每次从数据文件中读取大小为2GB的slice进入内存进行索引的构建;
- 对于可能出现的hash冲突采用链地址的方式解决,冲突链以追加的方式写入文件末尾;
- 待索引构建完成后,对冲突链进行紧缩,去除冲突链之间的的碎片空间。
- 通过IndexBuilder构建的hash索引进行数据的读取;
- 如果重复插入相同的key,返回最后插入的数据。
- 由于文件中每一条数据的key长度可变且key最大可为64kB,哈希表项采用(count,address)的方式保存数据,其中count大小为1字节,用于记录该地址对应的hash冲突的个数。address大小为5字节,用于记录一个字节地址:
- 当count=0时,address记录了对应数据在文件中的位置;
- 当count≠0时,address记录了该hash值对应冲突链在索引文件中的地址;
- 出现哈希冲突时,将原有冲突链数据复制一份并与新数据一起追加到索引文件末尾,使得同一hash值的所有表项在空间上连续存放;
- 在文件末尾追加新冲突链后,将原有冲突链中所有的表项count值做标记,便于在索引建立完成后进行文件碎片空间回收;
- 性能分析
- Good:哈希表项不保存key显著降低了索引文件的大小;
- Good:通过冲突链的连续存放,减少了查询时地址跳转次数(只需一次地址跳转),提高了性能;
- Bad:由于哈希表项中没有存放key的值,当查询出现冲突时,每一条冲突数据都需要去文件中进行查找,增加了磁盘IO次数(在DataReader类中通过对文件地址排序的方式进行了简单的优化);
- 当哈希冲突较少时,索引文件中不保存key带来的优势大于劣势;
- 当slice大小取2GB时,其对应产生的索引数据不超过2GB,因此在理想情况下,每个slice的索引构建都可以在内存中进行且不需要进行磁盘I/O(IndexBuilder类对此进行了优化,在一个slice的索引构建完成后才进行索引文件的写入)。