Does create index on a column always sort that column in background?

I used SQL a lot but I never cared about how it works on a deeper level. Recently I've been doing some research about keys and indexes. I have some questions about how exactly the index work.

As I understand, when I create an index on a column, the index stores a copy of the indexed column along with a reference to the corresponding table row in sorted order.

For example, if I have a table like below

Id Name
2  B
1  A
3  C

Then if I create an index on the "Name" column the index "table" will be something like

Name Pointer
A    Row2
B    Row1
C    Row3

With sorted order like this, it will be faster when searching for "Name" since you can apply an algorithm like binary search, which time-complexity can be O(logn) instead of O(n)

Does it mean that creating an index on a column always sorts that column in the background and it's the only way? Because if it's not sorted, then the time complexity when searching for a specific value is still like scanning the whole table, which makes no change.

You said "I mainly use Mysql" -- Even for that case, it depends.

• Older versions of MySQL and MariaDB would rebuild the table including the new index and any previous indexes.
• Newer versions do the CREATE INDEX in the background and eventually allow queries to use it.

The PRIMARY KEY in MySQL (and a "clustered" index in many other brands) will order the data by that key. A "secondary" index, itself, is sorted by the key in a "B+Tree", but has to reach over into the data's B+Tree to get the rest of the columns.

For a many-to-many-mapping table it is a good idea to build two indexes:

CREATE TABLE foo_bars (
    foo_id ...,
    bar_id ...,
    PRIMARY KEY(foo_id, bar_id),
    INDEX(bar_id, foo_id) )

That way, you get two fully sorted lookup BTrees.

"binary search" -- Read about BTrees; they are better than binary search when the data can be so big that it needs to be fetched from disk.

"reference to the corresponding table row" -- In InnoDB, the reference is a copy of the PRIMARY KEY, hence a second BTree lookup. In MyISAM it is an address into the .MYD file, a single file seek. In some other vendors, it is a "row number".

A "Columnstore" table is a radically different animal. It involves a 2-level lookup and uncompression.

A "Fulltext" index is essentially an inverted lookup of 'word' -> 'row.

A "Spatial" index is an "R-Tree". Ordinary indexes are 1-dimensional; Spatial gives you a 2-dimensional index.

• WHERE x = 2 -- A "point query" -- BTree lookup
• WHERE x BETWEEN 4 AND 44 -- First a Btree lookup, then use the + in B+Tree to do a "range scan"
• Otherwise, use a "table scan" (or "index scan") -- Look at every row.

Hope this helps; sorry that I don't have details for Postgres, etc.