How do we handle wildcard queries?


Using B-Tree (BBST) for postings allows us to find words in range word <= w < wore


If we want to find *word will be a bit harder, need to maintain another B-tree with inverse ordering. (right-to-left characterwise)


word* AND *word

In order to be more efficient, since we have to perform intersection merge, in the above example,

Other efficient ways

We can use a permuterm index.

We can use a Bigram for wildcard queries