Indexes, in most cases, are essentially variations of the B-tree data structure. Invented by Rudolf Bayer and Ed McCreight in 1971 while working at Boeing research labs, the B-tree data structure allows for search, sequential access, inserts, and deletes to be performed in logarithmic time. The logarithmic time property stands for both the average case and the worst possible performance, which is a great property when applications cannot tolerate unexpected variations in performance behavior.
To further understand how important the logarithmic time part is, we have included a diagram as follows:
In this diagram, we see logarithmic time performance as a flat line parallel to the x axis of the diagram. As the number of elements increases, constant time O(n) algorithms perform worse, whereas quadratic time algorithms O(n^2) go off...
