faiss 索引(索引文件是什么)

背景

本文旨在明确PQ索引的具体文件格式，精确到每个字节，从而使定性甚至定量分析索引成为可能，也为大规模全英里索引优化提供分析依据。

在深入研究索引格式的细节之前，有必要对索引的整体架构有一个整体的了解。

准备测试

测试条件

总样本量为1,000,000。维度为256。PQ分为32段。每个编码的固定量化空间为256，即nbits=8。测试代码如下

整数d=256;size_tnt=1000000;//制作索引对象并训练它faiss:IndexFlatL2rough_quantizer(d);//合理的质心数量来索引nb个向量intncentroids=int(sqrt(nt));faiss:IndexIVFPQindex(coarse_quantizer,d,ncentroids,32,8);std:向量floattrainvecs(nt*d);for(size_ti=0;int*d;i++){trainvecs[i]=drand48();}index.verbose=true;index.train(nt,trainvecs.data());index.add(nt,trainvecs.data());constchar*outfilename='/tmp/faissindex';write_index（索引，输出文件名）；

死嗑文件格式

write_index整体代码如下

uint32_th=fourcc(ivfpqr?'IvQR':ivfpqc?'IvPC':'IvPQ');写1（h）；write_ivf_header(ivpq,f,ivfpqc);WRITE1（ivpq-by_residual）；WRITE1(ivpq-code_size);write_ProductQuantizer(ivpq-pq,f);if(!ivfpqc){for(inti=0;iivpq-codes.size();i++)WRITEVECTOR(ivpq-codes[i]);1)幻数

uint32_th=fourcc(ivfpqr?'IvQR':ivfpqc?'IvPC':'IvPQ');写1（h）；4字节，即IvPQ

49765051索引文件偏移量[0-3]

2）写入反转信息

write_ivf_header(ivpq,f,ivfpqc);具体实现如下

write_index_header(ivf,f);WRITE1（ivf-nlist）；写1（ivf-nprobe）；write_index(ivf-量化器，f);if(include_ids){for(size_ti=0;iivf-nlist;i++)WRITEVECTOR(ivf-ids[i]);}WRITE1(ivf-maintain_direct_map);WRITEVECTOR(ivf-direct_map);2.1）写入索引头

write_index_header(ivf,f);具体实现如下

写1（idx-d）；#类型：int值：256WRITE1（idx-ntotal）；#类型：int值：1000000Index:idx_tdummy=120;写1（虚拟）；写1（虚拟）；WRITE1（idx-is_trained）；#类型：布尔值：trueWRITE1(idx-metric_type);#Type：enumMetricType值：METRIC_L2，为1字节如下

00010000#256小端40420f0000000000#1000000小端0000100000000000000010000000000001#101000000#1小端-字节序索引文件偏移量[4-36]

2.2）编写nlist和npobe

WRITE1（ivf-nlist）；#类型：size_t值：1000WRITE1（ivf-nprobe）；#类型：size_tvalue:1字节如下

e803000000000000#1000小端序0100000000000000#1小端序索引文件偏移量[37-52]

2.3）编写粗聚类中心

write_index(ivf-量化器，f);具体实现如下

2.3.1)写出粗聚类的幻数

uint32_th=fourcc(idxf-metric_type==METRIC_INNER_PRODUCT?'IxFI':idxf-metric_type==METRIC_L2?'IxF2':nullptr);写1（h）；字节如下

49784632索引文件偏移量[53-56]

2.3.2）写入索引头（同2.1）

写1（idx-d）；#类型：int值：256WRITE1（idx-ntotal）；#类型：int值：1000Index:idx_tdummy=120;写1（虚拟）；写1（虚拟）；WRITE1（idx-is_trained）；#类型：布尔值：trueWRITE1(idx-metric_type);#Type：enumMetricType值：METRIC_L2，为1字节如下

00010000#256小端e803000000000000#1000小端0000100000000000000010000000000001#101000000#1小端索引文件偏移量[57-89]

2.3.3)写入粗聚类中心的中心向量

写入矢量（idxf-xb）；具体实现如下

#defineWRITEVECTOR(vec){\size_tsize=(vec).size();\WRITEANDCHECK（大小，1）；\WRITEANDCHECK((vec).data(),大小);\}首先写入向量的长度1000*256=256000floats

字节如下

00e8030000000000#256000小端索引文件偏移量[90-97]

写入内容为256,000个浮点，总共1,024,000字节

615efa3e#[0]0.489001304小端bca5cb3e#[1]0.397748828小端.ff64e83e#[255998]0.453895539小端8078f53e#[255999]0.479434967小端索引文件偏移量[98-1024097]

2.4)写入反转ID

if(include_ids){for(size_ti=0;iivf-nlist;i++)WRITEVECTOR(ivf-ids[i]);}实现同2.3.3),

总共有1,000条反向链，并附有1,000,000个向量ID。

倒排链占用的字节为1000*8（倒排链本身只占用一个长度字节，即8）

内容占用1000000*8字节（每个ID为long类型，占用8字节）

总计80008000字节

字节如下

###第一条反向链长度为902，前两个元素为26,263，后两个元素为996521,9997268603000000000000#902little-endian1a00000000000000#[0]26小端0701000000000000#[1]263小端.a9340f0000000000#[900]996521小端2e410f0000000000#[901]999726little-endian###第二条反向链，长度为937a903000000000000#937little-endian.###第三条反向链.###第1000条反向链的长度为1084，前两个元素为452、6635，后两个元素为998987,9998583c04000000000000#1084little-endianc401000000000000#[0]452小端eb19000000000000#[1]6635小端.4b3e0f0000000000#[1082]998987小端b2410f0000000000#[1083]999858小端索引文件偏移量[1024098-9032097]

2.5）编写maintain_direct_map和direct_map

WRITE1(ivf-maintain_direct_map);WRITEVECTOR(ivf-direct_map);keep_direct_map默认为false

direct_map默认为空集合

字节如下

000000000000000000索引文件偏移量[9032098-9032106]

3）写入by_residual和code_size

WRITE1（ivpq-by_residual）；#trueWRITE1(ivpq-code_size);#32字节如下

012000000000000000#32小端索引文件偏移量[9032107-9032115]

4）写入pq信息

write_ProductQuantizer(ivpq-pq,f);具体实现如下

写1（pq-d）；写1（pq-M）；写1（pq-nbits）；WRITEVECTOR（pq-质心）；4.1）写入PQ基本信息

写1（pq-d）；#256写1（pq-M）；#32WRITE1（pq-nbits）；#8字节如下

0001000000000000#256小端序2000000000000000#32小端序0800000000000000#8小端序索引文件偏移量[9032116-9032139]

4.2）编写PQ聚类中心

WRITEVECTOR（pq-质心）；和上面的WRITEVECTOR一样，先写长度，再写内容。

4.2.1)长度

总共M*ksub*dsub为32*256*8(65536)个浮点数

字节如下

0000010000000000#65536小端索引文件偏移量[9032140-9032147]

4.2.2)内容总计65536*4字节

index文件偏移量[9032148-9294291]

5）编写反码

for(inti=0;iivpq-codes.size();i++)WRITEVECTOR(ivpq-codes[i]);和倒排的id一样，一共有1000条倒排链，挂1000000*32字节（每个样本用32字节表示）

倒排链占用的字节为1000*8（倒排链本身只占用一个长度字节，即8）

内容占用1000000*32字节（每个示例代码占用32字节）

字节

###第一个反转链长度为28864（902个样本码*每个样本码用32个字节表示），####前两个元素分别为65和34，后两个元素分别为82、251c070000000000000#28864小尾数()41#[0]6522#[1]34.52#[28862]82fb#[28863]251###第二个反向链，长度为299842075000000000000#29984little-endian.###第三条反向链.###第1000条反向链长度为34688，前两个元素是74,155，后两个元素是8,1978087000000000000#34688little-endian4a#[0]749b#[1]155.08#[34686]18c5#[34687]197索引文件偏移量[9294292-41302291]

最后

看一下整体文件格式布局