Are columns which are not indexes, sorted on disk together with index?

Question

Are columns which are not indexes, sorted on disk together with index, in MySQL, in MyISAM and InnoDB?

An incorrect thought that I started to write:

I think that probably not, since they are not indexed; if they were sorted that would mean that they are indexes.

This is not correct because every index column is sorted by its own content's order, but I am asking about being ordered of every row (or of only of some columns) with its corresponding index.

To explain, I say: this would be useful to make selecting ranges of rows, which stand side-by-side, together, by their indexes, faster. For example, if I want to select * where id >1000 and id<2000 (there may be mistakes in the MySQL syntax, I do not know it well), then, the id column itself can be read from disk quickly because probably its cells from 1000 to 2000 stay together on physical disk. But other column content corresponding to id 1000 to 2000 may be written on different places on physical disk. If they are also sorted, they would be read faster. I think, maybe MySQL automatically sorts that columns on physical disk, for performance of such operations.

Are they sorted in other types of databases (PostgreSQL, etc.)?

December 27: I see from the 2 answers, that in the case when there is clustered index/primary key, the simple rows themselves are not sorted on physical disk (as I thought it might/may be), and even the clustered index is not sorted, if it is b-tree, i have read about b-tree and see that its nodes, as i understand, stay at random places on disk.

Answer 1

They may be sorted in some cases. The sorting index is usually called the clustering key. If it is the case then the entire table is stored inside such index (usually in some sort of a B-tree structure).

In the other case the table structure is known as a heap, rows are stored as they come, deleting leaves "holes" in the data blocks and those holes are later filled with new rows, so not even the "insertion order" is preserved.

MyISAM uses the heap structure, with each row being identified by the offset(sort of array index) into the data file. Each index then contains the indexed column(s) for each row, sorted in the proper order and with the offset number to locate the real row. That means that accessing the row by any index means locating the right node(s) in the index (B-tree) and then reading the right offset(s) from the data file (random seek to a different part of the disk may happen).

InnoDB uses clustering by the primary key (or if none is defined, first non-null unique key is used, or an internal autoincrementing column is added - so the rows are always sorted somehow). In such case an access by the primary key is "direct", when the proper value is located, you have entire row at hand, no need to do a second read. The secondary indexes on the other hand cannot store an offset like in MyISAM (because the B-tree is dynamically rebalancing itself, so the offset of a specific row can change anytime) and they store the primary key values of the row instead - so an access by a secondary key means two B-tree searches in InnoDB.

MS SQL Server offers an option to make the primary key (or another index) either clustered or nonclustered, so you can choose between the heap (no index is clustered) and the tree structure (one index is clustered). All other non-clustered indexes store a special (RowID) values in the heap case or the clustered key values of the row in the case of the CI.

PostgreSQL uses only heap tables but lets you reorder them by some index on demand (you have to trigger it, so the rows are ordered after the action but further writes to the table can break that order again).

TokuDB (a 3rd-party MySQL/MariaDB engine) can use multiple clustering keys on one table - effectively it maintains multiple copies of the table, each sorted different way. It comes with a penalty on writes, but TokuDB claims to use somethink they call fractal indexes which should make that penalty quite small.

If you need to use that functionality for some queries, you can "emulate" it by creating a covering index - that way the colums your query needs are available in the right order anytime, but again it means maintaining an ordered copy of (parts of) the table in your indexes.

Answer 2

The short and simple answer for databases in general is: no, the physical order of rows in a table is generally not the same as in some index on that table.

In general (I say in general because there are special cases where that is not true) the table and the index are two different physical structures on disk. Conventional RDBMs store data so that values from one table row (not column) are located next to each other on disk; the rows themselves are not stored in any particular order. Index entries, on the other hand, are stored in order; a typical b-tree index contains sorted values of indexed columns (but not other columns!) and some sort of pointer to the location of the entire row in the table which is, as I stated before, a separate physical structure on disk.

That being said, there are special cases. For example, MySQL's InnoDB stores actual data rows in an index-like structure. Index by which rows are placed in such "index-table" is typically the table's primary key; and such an index is called a clustered index. But of course, an InnoDB table may have other indexes and ordering of rows (that is, row columns that are included in the respective index) in those indexes has nothing to do with ordering of rows in the table itself.