Каково время поиска Flann knn в OPENCV?

Каково время работы Flann knn искать в OpenCV?
Я знаю, что для построения индекса,
Построение линейного индекса займет O(N*M)если найду q указывает на M точки, где M очки принадлежат N точки.
Но мне интересно, разница между index building а также knn_search,
Кроме того, зачем нам строить индекс ???