How do we handle wildcard queries?
word*
Using B-Tree (BBST) for postings allows us to find words in range word <= w < wore
*word
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*dorw
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