Does an index improve the querying performance in just two ways? As far as I know, an index improves the querying performance in the following two ways:


The index only contains the values of the column that it was created for and pointers to the rows in the original table that each value points to (so this means there are fewer data to read from the disk when reading from the index compared to reading directly from the original table which could contain a lot of columns).
The values in the index are sorted.


But does an index improve the querying performance in other ways also? For example if we have an index for a name column, does the index contain pointers to the rows in the original table of each name, for example does an index contains something like this:

John (row4, row10, row12)
Robert (row9, row20)
Steve (row2, row6)
There's a step in query processing called optimization. This is when the SQL's logical operations (inner join, say) is translated into a physical operation (merge join, or hash join etc.). Each of these physical operations has a different fixed cost and per-row cost (by "cost" I mean time-to-get-results). So one physical operator will have a lower total cost for a few rows and a different one will have a lower total cost for many rows.

How does the optimizer know how many rows to expect and, hence, which physical operator to choose? With each index there will be a histogram summarizing the distribution of data referenced by that index.

John: three rows
Robert: two rows
Steve: two rows
Zach: seventy thousand rows


So we would expect a different query plan when listing Johns than when list Zachs. Choosing the wrong operator will result in a slower query. So indexes improve query performance because statistics are collected for each which allows better choice of physical operators.

Note, even if the associated index is not use in the final execution plan the statistics can still inform the optimizer's choices.



There are a great many index data structures and algorithms. The cannonical one for relatoinal databases is the B-Tree. This has one entry in the leaf nodes per row, with a pointer to the corresponding data row. Your example index on Name would look a bit like this on disk*

John(row4), John(row10), John(row12), Robert(row9), Robert(row20), Steve(row2), Steve(row6)


In a B+-Tree it's the level above the leaves that have the pointers and the leaf nodes are the data rows. So it could be something like:

Non-leaf node:
    John(Page 11 from row 4),
    Robert(Page 11 from row 7),
    Steve(Page 12 from row 1)

Leaf node page 11:
    &lt; three other rows &gt;,
    (John, Blue, Africa, 7),
    (John, Pink, Europe, 12),
    (John, Yellow, Asia, -3),
    (Robert, Red, NULL, 11), ...

Leaf node page 12:
    (Steve, Cyan, Antarctica, 42),
    (Steve, ...


For a hash index the name will be hashed to an offset which will have a pointer to an array of row locations. This is the most like your question, but is still a little different.

There are a great many other index structures. It is a field of active research.


* Except it's a lot more complicated, of course.