The phenomena called ‘inverted index’. An evaluation and explanation

Nowadays, indexes are essential in every database to support fast search to retrieve specific database rows. Not only databases but also applications could use data structures,  for example the System.Collections.Generic.Dictionary in C# and the java.util.HashMap in Java could be used for for fast searches using specific keys. In terms of the Big O notation, the retrieval time for items in a hashmap and dictionary based on a key is O(c) (constant). These data structures are very handy to support fast searches in specific items in applications. Database indexes are a bit slower compared to the map and dictionary, because most databases use a B-Tree on the background. The retrieval time of these indexes are O(log n) in a worst case scenario but still it is very fast. Last month, I got in touch with the phenomena called ‘inverted index’. I never heart of the inverted index before, but people told me positive stories about it and also the usual stories that this type of index is ‘tha bomb’ and should be used for everything related to search, so I decided to dive into this topic. Continue reading