Elasticsearch has a reverse indexing structure. If I send select(Get) query, the time complexity will be 1. because of reverse indexing structure. Then hat is the time complexity of Elasticsearch insert(Post) query ?

CodePudding user response：

The complexity of indexing depends on a lot of factors in Elasticsearch:

1. Data structure
2. Schema complexity (Nested objects and relations)
3. Ingest pipeline (You can have an expensive ingest pipeline that increase complexity of indexing)
4. Analyzers (Analyzers do text operation and some of them can be really time consuming)

But something important to keep in mind is that Elasticsearch use Lucene under the hood and Lucene use Skip list data structure for storing.

In computer science, a skip list is a probabilistic data structure that allows O(log n) search complexity as well as O(log n) insertion complexity within an ordered sequence of n elements.

For more information check Wiki page for SkipList.