big_file_index

实现了一个基于哈希的二进制数据文件索引结构及数据读取接口。

假设条件

1. 数据在文件中按照(key_size, key, value_size, value)无序排列；
2. key_size，value_size字段均为两字节；
3. 目标机器CPU按照big endian方式存放数据；
4. 文件slice大小为2GB，且每个文件slice均以一个完整的tuple开头，即不存在跨slice的数据。

主要功能介绍

IndexBuilder类

• IndexBuilder类用于创建索引，采用hashlib库提供的black2b函数，将键值均匀分布在0到2^32之间；
• 每次从数据文件中读取大小为2GB的slice进入内存进行索引的构建；
• 对于可能出现的hash冲突采用链地址的方式解决，冲突链以追加的方式写入文件末尾；
• 待索引构建完成后，对冲突链进行紧缩，去除冲突链之间的的碎片空间。

DataReader类

• 通过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的索引构建完成后才进行索引文件的写入）。