用了Elasticsearch,一口气上5T

Lucene索引倒排链数据结构为什么采用单链表,是基于什么考虑的?

Elasticsearch | 作者 kaiser1992 | 发布于2021年02月05日 | 阅读数:2063

我的理解是每个segment会先在内存中把数据都准备好,然后再写到磁盘,落盘后该段倒排链也不会做修改,那这样倒排链结构可以采用数组形式吗?在求交的过程中也可以基于二分查找来实现,而不用采用跳表这样消耗过多的磁盘空间。
已邀请:

JiangJibo - 喊我雷锋

赞同来自:

每个词的倒排索引是用单链表存储数据的,检索这个单链表都是从倒排索引的词为入口的,不会用二分法,词的倒排索引存储了他的数据在文件中的起始位置,用mmap快速定位后就是按顺序解析了

pzw9696

赞同来自:

事实上前面你说的没错,在没触发flush时候 数据是记录在dwpt里面的DefaultIndexingChain#perField 倒排表上面,累积到一定的量触发自动flush或者主动flush触发了,就开始写文件。  词在写.doc时候docid 和freq是用一个long类型的数组去记录,只不过docid是用的差值写入而freq存储的是原始值,最后会判定是否能生Block,block用 packedInt压缩存储,与此同时,block数量满足一定的条件后还会生成一个跳表,跳表上面会继续记录docid和指向 该term的position和payload offset docid freq 信息在.pos .pay .doc block的起始位置,跳表每一层有哨兵值。而查一个词会首先在tim上面定位到doc上面的跳表起始位置,从而再去获取这些值。当然文档数量不大的时候并不会生成跳表。存储性能损耗上,是没有影响,因为这个跳表只是逻辑意义上面定义,存的时候还是按照顺序一层层存储。只是查找的时候需要去跳转定位而已。

Ombres

赞同来自:

skiplist在lucene大部分用来进行有序递增的文档号的处理,用skiplist在查找时,可以依据哨兵值跳过已查找过的数据。

要回复问题请先登录注册