search

apache / lucene

Apache Lucene open-source search software
https://lucene.apache.org/
Apache License 2.0
2.45k stars 975 forks source link

Lucene index modeling - Why are skiplists used instead of B+ Tree? #13309

Closed IcanDoItL closed 2 months ago

IcanDoItL commented 2 months ago

Description

Lucene index modeling - Why are skiplists used instead of B+ Tree?

jpountz commented 2 months ago

This is actually not Lucene-specific, skip lists are the traditional approach for skipping in search engines. You can check out IR literature such as https://nlp.stanford.edu/IR-book/html/htmledition/faster-postings-list-intersection-via-skip-pointers-1.html.