Lucene-7.5.0 SkipList

lucene里面使用SkipList来加速查找速度,使用有序数组进行两分查找是否比SkipList快是因为SkipList对于增删的效率比有序数组更快吗?

Mar 14 '22 11:03 IcanDoItL

lucene里面使用SkipList来加速查找速度,使用有序数组进行两分查找是否比SkipList快是因为SkipList对于增删的效率比有序数组更快吗?

https://www.amazingkoala.com.cn/Lucene/Index/2020/0106/124.html

Mar 16 '22 07:03 LuXugang

同问，在生成segment的时候，doc链已经是有序的了，写到文件里面也是顺序写的，感觉可以直接用二分查找也可以？不知道用跳表的好处还有啥呢？

Apr 05 '22 05:04 wrkaiser

@IcanDoItL 大概原因可能是这个：Block大小是不固定的，需要把所有block都加载到内存，用二分查找成本太高

Apr 07 '22 10:04 wrkaiser

@wrkaiser 多谢我再仔细研究一下

Apr 12 '22 02:04 IcanDoItL

@IcanDoItL 大概原因可能是这个：Block大小是不固定的，需要把所有block都加载到内存，用二分查找成本太高

这个解释太妙了

Aug 05 '22 08:08 xiaoli233

同问，在生成segment的时候，doc链已经是有序的了，写到文件里面也是顺序写的，感觉可以直接用二分查找也可以？不知道用跳表的好处还有啥呢？

可以方便数据插入，跳表即可以快速查找数据(O(logn))，数据插入(O(1))和删除(O(1))也很友好。数组只对查找(O(logn))友好，插入(O(n))和删除(O(n))都会影响性能

Aug 22 '22 08:08 xiaoli233

Lucene-7.5.0 Lucene-7.5.0 copied to clipboard